组成Haskell树结构

Question

我在Haskell中进行递归思考时遇到了问题。

我正在尝试构建一个调查应用程序，其中问题根据用户的答案有条件地引发新问题。

我：
- Questions-问题列表
- QuestionPaths-的这会导致新问题的问题，问题的路径列表
- Answers用户的回答列表

您可以将其QuestionPaths视为元组列表，其中：

type QuestionPath = (QuestionId, AnswerChoice, NextQuestionId)

基本上，这将是：如果用户回答一个问题 QuestionId 一个答案 AnswerChoice，问他 NextQuestionId 旁边。

我试图用多路树（节点可以有多个孩子）来为这个问题域建模：

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]

不幸的是，我现在对如何编写像这样组成树的算法一无所知。

我基本上需要以下类型的函数进行组合和遍历：

-- 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

您能否帮助我了解构造和遍历此类树木的最佳方法是什么？

Answer 1

在这种情况下，我要做的就是将答案存储在单独的数据结构中- 而不是将其插入问题树中；将答案放在单独的列表/集中，或文件或数据库中，并使问题树不可变。

为了跟踪剩下的问题，您可以“消耗”该树-保持程序状态指向下一个问题，丢弃已经回答的问题（让垃圾收集器回收它们）。

我会像这样设计树：

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

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

注意几件事：

• 您不必担心导致同一问题的多个路径-您可以将相同的QuestionTree节点放置在多个位置，并且它将被共享（Haskell不会为其创建多个副本）

• 这种设计无处保留用户的答案-它们​​存储在其他位置（例如，列表在某处或一个文件中）-无需更改问题树。

• 当用户回答问题时，只需将“指针”移动到下一个QuestionTree，具体取决于用户回答的内容。

至于“如何从（QuestionId，AnswerChoice，NextQuestionId）列表构造这棵树”-我想我首先将其转换为地图：```Map QuestionId [（AnswerChoice，Maybe QuestionId）]，然后我会通过从第一个问题的ID开始并从Map中获取其直接子级来构建子树，以构建子树。

示例（对于非常简单的情况，其中唯一可能的答案是“是”或“否”，不允许跳过）：

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
             }

如果您想知道“为什么不直接使用地图？” -是的，您可以（通常这将是正确的解决方案），但是请考虑：

• QuestionTree结构比Id Map-> Thing更惯用地表达了程序员的意图

• 从结构上保证每当相关时有一个子QuestionTree-无需执行Map.lookup，这将返回Maybe，您必须验证其中是否包含Just（即使您知道会有下一个问题，即使这是EndOfQuestions）