title: Composing Haskell tree structures
body: <p>I got a problem with thinking recursively in Haskell.</p>
  
  <p>I am trying to build a survey application where questions conditionally lead to new questions based on the user's answers.</p>
  
  <p>I got:<br>
  - <code>Questions</code> - a list of questions<br>
  - <code>QuestionPaths</code> - a list of question paths of questions which lead to new questions<br>
  - <code>Answers</code> a list of user's answers  </p>
  
  <p>You can think of <code>QuestionPaths</code> as a list of tuples where:</p>
  
  <pre class="lang-hs prettyprint-override"><code>type QuestionPath = (QuestionId, AnswerChoice, NextQuestionId)
  </code></pre>
  
  <p>Basically this would read: <em>If user answers a question</em> <code>QuestionId</code> <em>with an answer</em> <code>AnswerChoice</code>, <em>ask him</em> <code>NextQuestionId</code> <em>next.</em></p>
  
  <p>I have attempted to model this problem domain with <a href="http://%20I%20got%20problem%20with%20thinking%20recursively%20in%20Haskell.%20%20I&#39;m%20trying%20to%20build%20a%20survey%20application%20where%20questions%20conditionally%20lead%20to%20new%20questions%20based%20the%20user&#39;s%20on%20answers.%20%20I%20got:%20-%20%60Questions%60%20-%20a%20list%20of%20questions%20%20%20%20%60QuestionPaths%60%20-%20a%20list%20of%20question%20paths%20which%20lead%20to%20new%20questions%20%20-%20%60Answers%60%20a%20list%20of%20user&#39;s%20answers%20%20You%20can%20think%20of%20%60QuestionPaths%60%20as%20a%20list%20of%20tuples%20where:%20%60%60%60haskell%20(QuestionId,%20AnswerChoice,%20NextQuestionId)%20%60%60%60.%20Basically%20this%20would%20read:%20_If%20user%20answers%20a%20question_%20%60QuestionId%60%20_with%20an%20answer_%20%60AnswerChoice%60,%20_ask%20him_%20%60NextQuestionId%60%20_next._%20%20I&#39;ve%20attempted%20to%20model%20this%20problem%20domain%20with%20multiway%20trees%20(nodes%20can%20have%20multiple%20children):%20%60%60%60haskell%20data%20YesNo%20=%20Yes%20%7C%20No%20data%20AnswerChoice%20=%20%20%20Skip%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7C%20Boolean%20YesNo%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7C%20ChooseOne%20[Text]%20%20type%20Condition%20=%20AnswerChoice%20%20data%20QuestionTree%20=%20QuestionNode%20%7B%20%20%20%20%20%20%20question%20%20%20%20%20%20::%20Question%20%20%20%20%20,%20userAnswer%20%20%20%20::%20Maybe%20AnswerChoice%20%20%20%20%20,%20children%20%20%20%20%20%20::%20QuestionForest%20%20%20%20%20%7D%20%20type%20QuestionForest%20=%20[QuestionTree]%20%60%60%60%20Unfortunately,%20I&#39;m%20clueless%20now%20on%20how%20to%20write%20algorithms%20that%20compose%20trees%20like%20this.%20%20%20I%20basically%20need%20these%20kinds%20of%20functions%20for%20composition%20and%20traversal:%20%60%60%60haskell%20--%20Constructs%20the%20tree%20from%20seed%20data%20constructTree%20::%20Questions%20-%3E%20QuestionPaths%20-%3E%20Answers%20-%3E%20QuestionTree%20%20--%20%7C%20Inserts%20answer%20to%20question%20in%20the%20tree%20answerQuestion%20::%20Question%20-%3E%20AnswerChoice%20%20--%20%7C%20Fetches%20the%20next%20unanswered%20question%20by%20traversing%20the%20tree.%20getNextUnanswered%20::%20QuestionTree%20-%3E%20Question%20%60%60%60%20%20**Can%20you%20please%20help%20me%20understand%20what%20would%20be%20the%20best%20ways%20to%20construct%20and%20traverse%20a%20tree%20such%20as%20this?**" rel="nofollow noreferrer">multiway trees</a> (nodes can have multiple children):</p>
  
  <pre class="lang-hs prettyprint-override"><code>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]
  </code></pre>
  
  <p>Unfortunately, I am clueless now on how to write algorithms that compose trees like this. </p>
  
  <p>I basically need these kinds of functions for composition and traversal:</p>
  
  <pre class="lang-hs prettyprint-override"><code>-- Constructs the tree from seed data
  constructTree :: Questions -&gt; QuestionPaths -&gt; Answers -&gt; QuestionTree
  
  -- | Inserts answer to question in the tree
  answerQuestion :: Question -&gt; AnswerChoice
  
  -- | Fetches the next unanswered question by traversing the tree.
  getNextUnanswered :: QuestionTree -&gt; Question
  </code></pre>
  
  <p><strong>Can you please help me understand what would be the best way to construct and traverse a tree such as this?</strong></p>