具有可变成员的树上的Haskell树foldt

Question

我试图创建一个自定义数据类型树。定义如下：

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

• 叶片数据；或

这是我的代码：

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

我的函数的哪一部分不是详尽的，或者我定义的数据类型不正确？

更新：

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

数据树a=叶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)))

Answer 1

我已经找到了答案。熬夜一整夜后，我突然有了灵感。这里是：

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

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

Answer 2

通过打开警告，您可以从GHC获得一些帮助。“大锤”是-Wall：

-- At the very top of the file
{-# OPTIONS_GHC -Wall #-}

噪音较小的方法也适用：

{-# OPTIONS_GHC -fwarn-incomplete-patterns #-}

这两个选项中的任何一个都将为您提供编译时未能匹配的模式的显式列表。

将Tree放在模式中不起作用的原因是Tree是一个类型构造函数（通过将它们放在data或newtype声明的左侧进行排序）。只有数据构造函数（将它们放在data或newtype声明的右侧进行排序）才能在模式中匹配。