Haskell n-ary tree traversal

Question

Я довольно новичок в Haskell, и я пытаюсь разобраться, как пройти n-арное дерево. Как выход я ищу, чтобы получить список значений листьев (как ветви не имеют значения), поэтому для 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 

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

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 для правой части этого определения, но я считаю, выше один, чтобы быть ясным.

Edit: реинтродукция версии списка постижения для полноты картины:

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

Answer 2

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

travTree (Branch xs) = concatMap travTree xs 

(Но будьте осторожны, я не проверял, что же я часто нахожу мой «бесконечный тип а = [а]» проблемы вызваны map где concatMap нужен!.)

Answer 3

Когда я был новичком в Haskell, я столкнулся с той же проблемой. Я, наконец, понял, как решить проблему, замедлив и посмотрев на типы. (Не, когда я писал много Scheme, я вместо этого замедлилось и посмотреть на очень простых входных/выходных пар. Я делаю это иногда в 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].

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