Home Articles

树上的Haskell Tree foldt与可变成员

Asked
Viewed 349 times
0

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

树可以定义为包含单条信息的叶子(由关键字“叶子”标识)(即,它是没有孩子的节点),或者是由节点(由关键字“节点”标识)的树 . 单个信息,加上一个树列表 - 列表中的每个元素代表一个以相应子节点为根的子树 . 请注意,在此定义下,树永远不能为空 . 这意味着一棵树可以是:叶子数据;或节点数据[data,data,...] - 列表中可以有零个或多个树

这是我的代码:

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

我的功能的哪一部分是非详尽的,或者我是否错误地定义了数据类型?

Update:

我可能已经解决了非详尽的模式,我现在已经解决了这个问题,但它声称树没有定义:

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

2 Answers

  • 2

    你可以通过打开警告来获得GHC的帮助 . "big hammer"是 -Wall

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

    嘈杂的方法也会起作用:

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

    在编译时,这些中的任何一个都将为您提供未能匹配的模式的明确列表 .

    Tree 放在您的模式中的原因是不行的是 Tree 是一个类型构造函数(通过将它们放在 datanewtype 声明的左侧来进行排序) . 只有数据构造函数(通过将它们放在 datanewtype 声明的右侧进行排序)才能在模式中匹配 .

  • 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
    

    这传递了所有测试用例,并回答了我的问题 .

Related