哈斯克尔n元树遍历

本文介绍了哈斯克尔n元树遍历的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述 我对Haskell很新，我正在努力研究如何遍历n-ary树。作为输出，我希望得到Leaf值的列表（因为分支没有值），所以对于testtree来说，这将是：4,5 我的定义如此远远是： 数据树a =叶子a |分支[Tree a]派生（显示） travTree :: Tree a - > [a] travTree（Leaf x）= [x] travTree（Branch（x：xs））= travTree x：travTree xs testtree = Branch [ 4），（Leaf5）] 但它给出错误： 无法与推断类型`[Tree a]'相匹配的预期类型`Tree a''在第一个``''的第二个参数，即`travTree xs'在表达式中：travTree x：travTree xs 我假设这是由于xs是一个树列表，并且期望一棵单数树。有没有办法做到这一点？我一直在尝试map函数，如下所示： travTree（Branch（x：xs））= travTree x ：地图travTree xs 但它会抱怨： 发生检查：无法构造无限类型：a = [a] 当概括'travTree'的类型时 我也尝试将函数签名更改为： travTree :: Tree a - > [b] 给出错误： 无法与推断类型'[b]'匹配预期类型'[b]''a'是一个刚性类型变量，由绑定， `：:)'的第一个参数，即`travTree x'在表达式中：travTree x：map travTree xs 在Main.hs中的`travTree'：149：36 'travTree'的定义： travTree（Branch（x：xs））= travTree x：map travTree xs 任何帮助都将不胜感激，所以在此先感谢！！ 遍历a树意味着遍历所有子树，并将结果列表展平成一个。 这意味着 travTree（Branch branches）= concat $ map travTree branches 注意还有更简洁的符号，例如分支>> = travTree 或 concatMap travTree branches 作为这个定义的右边，但我认为上面这个是最清晰的。 编辑： travTree（Branch branches）= [elem | br I'm pretty new to Haskell and I'm trying to work out how to traverse a n-ary tree. As output I'm looking to get a list of Leaf values (as the branches have no value), so for testtree this would be: 4,5My definition so far is: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 xstesttree = Branch [(Leaf "4"), (Leaf "5")]But it gives the error: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 xsI'm assuming this is due to xs being a list of trees and its expecting a singular tree. Is there a way to do this? I've been trying the map function, along the lines of:travTree (Branch (x:xs)) = travTree x : map travTree xsBut it then complains of:Occurs check: cannot construct the infinite type: a = [a]When generalising the type(s) for `travTree'I've also tried changing the function signature to:travTree :: Tree a -> [b]Which gives the error: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:36In the first argument of `(:)', namely `travTree x'In the expression: travTree x : map travTree xsIn the definition of `travTree': travTree (Branch (x : xs)) = travTree x : map travTree xsAny help would be greatly appreciated, so thanks in advance..! 解决方案 Traversing a tree means traversing all subtrees and flattening the resulting lists into one.This translates totravTree (Branch branches) = concat $ map travTree branchesNote that there are even more concise notations like branches >>= travTree or concatMap travTree branches for the right hand side of this definition, but I consider the above one to be the clearest.Edit: Reintroducing the list-comprehension version for the sake of completeness:travTree (Branch branches) = [ elem | br <- branches, elem <- travTree br ] 这篇关于哈斯克尔n元树遍历的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！