Haskell Tree foldt on Tree with variable members

Question

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

A tree can be defined as either a leaf (identified by the keyword "Leaf") containing a single piece of information (i.e. it is a node with no child), or a node (identified by the keyword "Node") with a single piece of the information, plus a list of trees – each element in the list represent a subtree rooted at the corresponding child. Note that under this definition, a tree can never be empty. That means a tree can either be:

Leaf data; or

Node data [data, data, …] -- there can be zero or more tree inside the list

这是我的代码：

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 ] 派生 (Show)

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

您可以通过打开警告从 GHC 获得一些帮助。 "big hammer" 是 -Wall:

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

噪音较小的方法也行得通：

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

其中任何一个都会在编译时为您提供您未能匹配的模式的明确列表。

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

Answer 2

我找到了答案。熬夜后，我灵光一闪。这是：

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

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

Haskell Tree foldt on Tree with variable members

Haskell Tree foldt on Tree with variable members

tree

recursion

haskell