Составление структур дерева Haskell

Question

У меня проблема с рекурсивным мышлением в Хаскеле.

Я пытаюсь создать приложение для опроса, в котором вопросы условно приводят к новым вопросам на основе ответов пользователя.

Я получил:
- 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)], затем Я построил бы дерево, начав с идентификатора первого вопроса и выбрав его непосредственных потомков с карты, построив поддеревья.

Пример (для очень упрощенного случая, когда единственно возможными ответами являются «да» или «нет», без пропуска):

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 выражает намерение программиста более идиоматически, чем Map of Id -> Thing

• Структурно гарантируется наличие дочернего QuestionTree, когда это уместно - нет необходимости делать Map.lookup, который будет возвращать значение Maybe, которое вы должны проверить, которое содержит Just (даже если вы знаете будет следующий вопрос, даже если это EndOfQuestions)