Composing Haskell tree structures

Question

I got a problem with thinking recursively in Haskell.

I am trying to build a survey application where questions conditionally lead to new questions based on the user's answers.

I got:
- Questions - a list of questions
- QuestionPaths - a list of question paths of questions which lead to new questions
- Answers a list of user's answers

You can think of QuestionPaths as a list of tuples where:

type QuestionPath = (QuestionId, AnswerChoice, NextQuestionId)

Basically this would read: If user answers a question QuestionId with an answer AnswerChoice, ask him NextQuestionId next.

I have attempted to model this problem domain with multiway trees (nodes can have multiple children):

data YesNo = Yes | No
data AnswerChoice =   Skip
                    | Boolean YesNo
                    | ChooseOne [Text]

type Condition = AnswerChoice

data QuestionTree = QuestionNode {
      question      :: Question
    , condition     :: Condition
    , userAnswer    :: Maybe AnswerChoice
    , children      :: QuestionForest
    }

type QuestionForest = [QuestionTree]

Unfortunately, I am clueless now on how to write algorithms that compose trees like this.

I basically need these kinds of functions for composition and traversal:

-- Constructs the tree from seed data
constructTree :: Questions -> QuestionPaths -> Answers -> QuestionTree

-- | Inserts answer to question in the tree
answerQuestion :: Question -> AnswerChoice

-- | Fetches the next unanswered question by traversing the tree.
getNextUnanswered :: QuestionTree -> Question

Can you please help me understand what would be the best way to construct and traverse a tree such as this?

Answer 1

What I'd do in such a case, is to store the answers in a separate data structure - not to insert them in the questions tree; put the answers in a separate list/Set, or in a file or database, and let the questions tree be immutable.

In order to keep track of which questions remain to be asked, you can "consume" the tree - keep your program state pointing to the next question, throwing away the questions already answered (letting the garbage collector reclaim them).

I'd design the tree like this:

data AllowedAnswers = YesOrNo {
                        ifUserAnsweredYes :: QuestionTree,
                        ifUserAnsweredNo :: QuestionTree
                      }
                      | Choices [(Text, QuestionTree)]

data QuestionTree = Question {
      description :: Text
    , allowedAnswers :: AllowedAnswers
    , ifUserSkipsThisQuestion :: QuestionTree
  }
  | EndOfQuestions

Notice several things:

• You don't have to worry about multiple possible paths leading to the same question - you can place the same QuestionTree node in multiple places, and it will be shared (Haskell won't create multiple copies of it)

• This design has no place to hold the user's answers - they are stored elsewhere (i.e. a list somewhere, or a file) - no need to mutate the question tree.

• As the user answers questions, just move your "pointer" to the next QuestionTree, depending on what the user answered.

As for "how to construct this tree from the (QuestionId, AnswerChoice, NextQuestionId) list" - I think I'd first convert it into a map: ```Map QuestionId [(AnswerChoice, Maybe QuestionId)], then I'd construct the tree by, starting with the ID of the first question, and fetching its immediate children from the Map, build the subtrees.

Example (for a very simplified case where the only possible answers are "yes" or "no", with no skipping allowed):

buildTree questionMap questionId = case Map.lookup questionId questionMap of
  Nothing -> EndOfQuestions
  Just (description, [("yes", nextQuestionIdIfYes), ("no", nextQuestionIdIfNo)]) ->
    Question { description = description
               , allowedAnswers = YesOrNo {
                   ifUserAnsweredYes = buildTree questionMap nextQuestionIdIfYes
                   , ifUserAnsweredNo = buildTree questionMap nextQuestionIdIfNo
                 }
               , ifUserSkipsThisQuestion = EndOfQuestions
             }

If you are wondering "why not just use the Map directly?" - yes, you could (and often it will be the right solution), but consider:

• The QuestionTree structure expresses the programmer's intention more idiomatically than a Map of Id -> Thing

• It is structurally guaranteed to have a child QuestionTree whenever pertinent - no need to do Map.lookup, which will return a Maybe, which you must verify that contains a Just (even when you know there is going to be a next question, even if it is EndOfQuestions)