Хаскелл 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

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

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

travTree (Branch branches) = concat $ map travTree branches

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

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

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

Answer 2

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

travTree (Branch xs) = concatMap travTree xs

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

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

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