使用指定foldTree实现二叉树最小值minTree的报错修复求助

错误原因 #

• 函数定义和签名不匹配：你声明minTree仅接收1个Tree a类型参数，但是第一行实现错误定义了minTree f e Leaf = e，多出来的f、e两个参数和声明的签名冲突，这行是无效冗余代码，直接删除即可。
• 折叠函数类型不匹配：你使用的foldTree要求传入的折叠函数必须接收3个参数，分别对应左子树折叠结果、当前节点值、右子树折叠结果，你定义的f仅接收2个参数，完全不符合类型要求，所以会抛出类型错误。

修复后实现 #

-- 匹配你场景的Tree类型定义
data Tree a = Leaf | Node (Tree a) a (Tree a) deriving (Show)

foldTree :: (b -> a -> b -> b) -> b -> Tree a -> b
foldTree f e Leaf         = e
foldTree f e (Node left x right) = f (foldTree f e left) x (foldTree f e right)

-- 修复后的minTree实现，无需导入额外库
minTree :: (Ord a) => Tree a -> Maybe a
minTree = foldTree f Nothing
  where
    -- 三个参数依次为：左子树最小值、当前节点值、右子树最小值
    f Nothing  cur Nothing  = Just cur
    f (Just l) cur Nothing  = Just $ min l cur
    f Nothing  cur (Just r) = Just $ min cur r
    f (Just l) cur (Just r) = Just $ min (min l cur) r

如果希望代码更简洁，也可以使用Data.Maybe的工具函数简化写法：

import Data.Maybe (catMaybes)

minTree :: (Ord a) => Tree a -> Maybe a
minTree = foldTree f Nothing
  where
    f left cur right = case catMaybes [left, Just cur, right] of
        [] -> Nothing
        xs -> Just $ minimum xs

验证示例 #

-- 空树测试
> minTree Leaf
Nothing

-- 单节点树测试
> minTree (Node Leaf 3 Leaf)
Just 3

-- 普通二叉树测试
> minTree (Node (Node Leaf 5 Leaf) 2 (Node Leaf 1 Leaf))
Just 1

内容的提问来源于stack exchange，提问作者user17119037