哈斯克尔n元树遍历 [英] Haskell n-ary tree traversal

问题描述

我对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 < -  branch，elem <-travTree 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,5

My 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 xs

testtree = 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 xs

I'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 xs

But 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: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

Any 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 to

travTree (Branch branches) = concat $ map travTree branches

Note 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元树遍历的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！