如何使用foldr实现查找二叉树最小值的minTree函数

1. 为Tree类型实现Foldable类型类实例 #

要使用foldr首先需要自定义Tree类型属于Foldable类型类，有两种实现方案：

• 方案1：开启扩展自动推导
  加编译指示开启DeriveFoldable扩展，直接在派生声明中增加Foldable即可：

  {-# LANGUAGE DeriveFoldable #-}
  data Tree a 
      = Leaf
      | Node (Tree a) a (Tree a)
      deriving (Show, Eq, Foldable)
  

• 方案2：手动实现Foldable实例
  不需要开启扩展，手动实现foldr遍历逻辑：

  instance Foldable Tree where
      foldr _ z Leaf = z
      foldr f z (Node left val right) = 
          let rightRes = foldr f z right
              curRes = f val rightRes
          in foldr f curRes left
  

2. 基于foldr重写minTree #

你之前写的多分支minTree逻辑只遍历了左子树，完全没有处理右子树和当前节点的比较，全部删除替换为如下实现：

import Data.Maybe (maybe)

minTree :: (Ord a) => Tree a -> Maybe a
minTree = foldr (\curVal minAcc -> Just $ maybe curVal (min curVal) minAcc) Nothing

逻辑说明 #

• 初始累加值minAcc设为Nothing，对应空树的返回结果
• 遍历每个节点值curVal时：
  • 如果当前minAcc是Nothing（还未遍历到任何节点），直接把curVal包进Just作为当前最小值
  • 如果minAcc已经存储了最小值，取curVal和现有最小值的较小值作为新的累加结果
• foldr会自动遍历整棵树的所有节点，不需要手动写递归分支处理左右子树

测试验证 #

可以用如下测试用例验证功能正确性：

-- 测试树结构：根节点1，左子节点3，右子节点2
testTree :: Tree Int
testTree = Node (Node Leaf 3 Leaf) 1 (Node Leaf 2 Leaf)

main = print $ minTree testTree -- 预期输出 Just 1

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