Обход дерева не Haskell
Я довольно плохо знаком с Haskell, и я пытаюсь разработать, как пересечь дерево не. Как произведено я надеюсь получать список Листовых значений (поскольку ответвления не имеют никакого значения), таким образом, для 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
Любая справка значительно ценилась бы, таким образом, заранее спасибо..!
3 ответа
Обход дерева означает обход всех поддеревьев и объединение полученных списков в один.
Это переводится в
travTree (Branch branches) = concat $ map travTree branches
. Обратите внимание, что для правой части этого определения есть еще более краткие обозначения, например branch >> = travTree или concatMap travTree branch , но Считайте приведенный выше наиболее ясным.
Изменить: Повторное введение версии со списком для полноты:
travTree (Branch branches) = [ elem | br <- branches, elem <- travTree br ]
Когда я был новичком в Haskell, я часто сталкивался с той же проблемой. Я наконец-то понял, как решить проблему, притормозив и посмотрев на типы. (Когда я писал много Scheme, я вместо этого замедлился и посмотрел на очень простые пары ввода / вывода. Иногда я делаю это в Haskell, но только после того, как посмотрю на типы.)
travTree :: Tree a -> [a]
travTree (Leaf x) = [x]
travTree (Branch (x:xs)) = travTree x : travTree xs
Ваш тип выглядит правильным. : Дерево a -> [a] для меня звучит как «все листья».
travTree (Leaf x) = [x]
Этот случай правильно преобразует Дерево a в [a] .
travTree (Branch (x:xs)) = travTree x : travTree xs
Хорошо, вход определенно представляет собой Дерево 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] .
Другие ответы правы, когда говорят, что деструктуризация здесь бессмысленна, но я надеюсь, что видение описанных типов поможет вам понять, как имитировать вывод типов в своей голове. Таким образом вы сможете понять, что не так с другими похожими проблемами.
Вы находитесь на правильном пути с map, но после обхода каждого поддерева вы хотите concat результирующие списки вместе. Также нет смысла отрывать первый элемент списка с помощью шаблона (x:xs) при использовании map. Я бы записал это как:
travTree (Branch xs) = concatMap travTree xs
(Но учтите, я это не проверял! Однако я часто обнаруживаю, что проблемы с "бесконечным типом a = [a]" вызваны map там, где нужен concatMap)