具有变量成员的树上的Haskell树折叠

debugcn 发表于 Dev

自己12794

我正在尝试创建一个自定义数据类型Tree。定义如下：

可以将树定义为包含单个信息（即，它是没有子节点的节点）的叶子（由关键字“ Leaf”标识）或具有单个信息的节点（由关键字“ Node”标识）信息，再加上一棵树–列表中的每个元素代表一个以相应子节点为根的子树。请注意，在此定义下，树永远不能为空。这意味着一棵树可以是：

叶数据；或者

节点数据[数据，数据，...]-列表内可以有零棵或更多棵树

这是我的代码：

data Tree a = Leaf a | Node a [ Tree a ] deriving (Show)

foldt :: (a -> a -> a) -> Tree a -> a
foldt f (Leaf a)     = a
foldt f (Node a [])  = a
foldt f (Node a [b]) = f a (foldt f b)

它可以编译，但是当我尝试运行时：

let myTree = Node 'A' [Node 'B' [Leaf 'E', Node 'F' [Leaf 'I', Leaf 'J', Leaf 'K']], Node 'C' [Leaf 'G', Leaf 'H'], Leaf 'D']
foldt min myTree

而不是预期的输出'A'，我得到以下错误：

CSC207a4.hs:(6,1)-(8,38): Non-exhaustive patterns in function foldt

我的函数的哪一部分不够详尽，或者我是否错误地定义了数据类型？

更新：

我可能已经解决了非穷举模式，但现在我有了这个，但它声称未定义Tree：

数据树a =叶a | 节点[树a]派生（显示）

foldt :: (a -> a -> a) -> Tree a -> a
foldt f (Leaf a)     = a
foldt f (Node a [])  = a
foldt f (Node a [(Tree x)])  = f a (foldt f x)
foldt f (Node a [(Tree x):xs]) = f a (foldt f (f x (foldt f xs)))

自己12794

我找到了答案。熬了一夜后，我有了灵感。这里是：

module CSC207a4 where

data Tree a = Leaf a | Node a [ Tree a ] deriving (Show)

foldt :: (a -> a -> a) -> Tree a -> a
foldt _ (Leaf a)    = a
foldt _ (Node a []) = a
foldt f (Node a b)  = f (foldt f x) (foldt f (Node a xs))
    where
        x:xs = b

这通过了所有测试用例，并回答了我的问题。

本文收集自互联网，转载请注明来源。

如有侵权，请联系[email protected] 删除。