Хаскелл n-арный обход дерева

Question

Я довольно новичок в Хаскеле и пытаюсь понять, как пройти через n-арное дерево. В качестве вывода я хочу получить список значений Leaf (поскольку ветви не имеют значения), поэтому для testtree это будет: 4,5

Мое определение до сих пор:

data Tree a = Leaf a | Branch [Tree a] deriving (Show)

travTree                    :: Tree a -> [a]
travTree (Leaf x)           = [x]
travTree (Branch (x:xs))    = travTree x : travTree xs

testtree = Branch [(Leaf "4"), (Leaf "5")]

Но выдает ошибку:

Couldn't match expected type `Tree a'
  against inferred type `[Tree a]'
In the first argument of `travTree', namely `xs'
In the second argument of `(:)', namely `travTree xs'
In the expression: travTree x : travTree xs

Я предполагаю, что это связано с тем, что xs - это список деревьев, и он ожидает единственное дерево. Есть ли способ сделать это? Я пробовал функцию карты, в соответствии с:

travTree (Branch (x:xs))    = travTree x : map travTree xs

Но тогда он жалуется на:

Occurs check: cannot construct the infinite type: a = [a]
When generalising the type(s) for `travTree'

Я также пытался изменить сигнатуру функции на:

travTree                    :: Tree a -> [b]

Что выдает ошибку:

Couldn't match expected type `a' against inferred type `[b]'
  `a' is a rigid type variable bound by
      the type signature for `travTree' at Main.hs:149:36
In the first argument of `(:)', namely `travTree x'
In the expression: travTree x : map travTree xs
In the definition of `travTree':
    travTree (Branch (x : xs)) = travTree x : map travTree xs

Любая помощь будет принята с благодарностью, поэтому заранее спасибо ..!

Answer 1

Вы находитесь на правильных строках с map, но после обхода каждого поддерева вы хотите concat получившиеся списки вместе. Также нет смысла разрывать первый элемент списка с шаблоном (x:xs) при использовании map. Я бы написал это как:

travTree (Branch xs) = concatMap travTree xs

(Но будьте осторожны; я не проверял это! Однако я часто обнаруживаю, что мои проблемы "бесконечного типа a = [a]" вызваны map, где требуется concatMap.)

Answer 2

Обход дерева означает обход всех поддеревьев и объединение полученных списков в один.

Это переводится как

travTree (Branch branches) = concat $ map travTree branches

Обратите внимание, что для правой части этого определения есть еще более краткие обозначения, такие как branches >>= travTree или concatMap travTree branches, но я считаю, что приведенное выше является наиболее ясным.

Редактировать: Повторно представить версию со списком для полноты:

travTree (Branch branches) = [ elem | br <- branches, elem <- travTree br ]

Answer 3

Когда я был новичком в Haskell, я часто сталкивался с той же проблемой. В конце концов я понял, как решить проблему, замедляя и рассматривая типы. (Назад, когда я написал много Схем, я вместо этого замедлил и смотрю на очень простые пары ввода / вывода. Я делаю это иногда в Haskell, но не до тех пор, пока не посмотрю на типы.)

travTree                    :: Tree a -> [a]
travTree (Leaf x)           = [x]
travTree (Branch (x:xs))    = travTree x : travTree xs

Ваш тип выглядит правильно: Tree a -> [a] звучит как "все листья" для меня.

travTree (Leaf x) = [x]

Этот случай правильно конвертирует Tree a в [a].

travTree (Branch (x:xs)) = travTree x : travTree xs

ОК, ввод определенно Tree a. Если выходные данные должны быть [a], а первый оператор - (:) :: a -> [a] -> [a], тогда нам нужны travTree x :: a и travTree xs :: [a]. Это работает?

Ну, это не работает по двум причинам: на самом деле, travTree x :: [a], и вы не можете добавить список в другой список (для этого вам нужно (++) :: [a] -> [a] -> [a]). И вы не можете передать [Tree a] на travTree :: Tree a -> [a] - вы даете ему список деревьев, когда он ожидает одно дерево.

Вы можете решить вторую проблему, используя map: map travTree xs. Это имеет тип [Tree a] -> [[a]]. К счастью, теперь это соответствует travTree x :, так что

(travTree x : map travTree xs) :: [[a]]

Теперь у вас есть проблема с [[a]] вместо [a]. concat решает эту проблему путем выравнивания один раз, поэтому

travTree (Branch (x:xs)) = concat (travTree x : map travTree xs) :: [a]

, что соответствует ожидаемому Tree a -> [a].

Другие ответы верны, когда говорят, что деструктурирование здесь бессмысленно, но я надеюсь, что видение прописанных типов поможет вам понять, как имитировать вывод типа в вашей голове. Таким образом, вы можете решить, что идет не так для других, подобных проблем.