递归方案允许递归调用之间的依赖关系（有序的变形？）

Question

我对编写递归代码的高阶方法（递归方案）感兴趣，其中递归调用之间可能存在依赖关系。

作为一个简化示例，考虑一个遍历整数树的函数，检查总和是否小于某个值。我们可以对整棵树求和并将其与最大值进行比较。或者，我们可以保持运行总和并在超过最大值后立即短路：

data Tree = Leaf Nat | Node Tree Tree

sumLT :: Nat -> Tree -> Bool
sumLT max t = sumLT' max t > 0

sumLT' :: Nat -> Tree -> Int
sumLT' max (Leaf n) = max - n
sumLT' max (Node l r) = 
  let max' = sumLT' max l
   in if max' > 0 then sumLT' max' r else 0

有没有办法用递归方案来表达这个想法——本质上是有序遍历？我对尽可能一般地编写这样的有序遍历很感兴趣。

理想情况下，我想要某种方式来编写遍历，其中在数据结构上折叠（或展开）的函数决定遍历的顺序。无论我最终得到什么抽象，我都希望能够编写上面 sumLT' 遍历的逆序版本，我们从右到左进行遍历：

sumLT'' :: Nat -> Tree -> Int
sumLT'' max (Leaf n) = max - n
sumLT'' max (Node l r) = 
  let max' = sumLT'' max r
   in if max' > 0 then sumLT'' max' l else 0

Answer 1

像往常一样，折叠成内函数给你一个处理顺序/状态传递的概念：

import Numeric.Natural

data Tree = Leaf Natural | Node Tree Tree

cata :: (Natural -> r) -> (r -> r -> r) -> Tree -> r
cata l n (Leaf a)     = l a
cata l n (Node lt rt) = n (cata l n lt) (cata l n rt)

sumLT :: Natural -> Tree -> Bool
sumLT max t = cata (\ a max -> max - a)     -- left-to-right
                   (\ l r max -> let max' = l max in
                        if max' > 0 then r max' else 0)
                   t max > 0

sumLT' :: Natural -> Tree -> Bool
sumLT' max t = cata (\ a max -> max - a)     -- right-to-left
                    (\ l r max -> let max' = r max in
                         if max' > 0 then l max' else 0)
                    t max > 0

尝试一下：

> sumLT 11 (Node (Leaf 10) (Leaf 0))
True

> sumLT 11 (Node (Leaf 10) (Leaf 1))
False

> sumLT 11 (Node (Leaf 10) (Leaf undefined))
*** Exception: Prelude.undefined

> sumLT 11 (Node (Leaf 11) (Leaf undefined))
False

> sumLT 11 (Node (Leaf 10) (Node (Leaf 1) (Leaf undefined)))
False

> sumLT' 11 (Node (Leaf undefined) (Leaf 11))
False

和往常一样，Haskell的懒惰提供了短路/提前退出的能力。从示例中可以看出，如果 cata's 第二个参数（节点折叠函数）不需要其参数之一的值，则实际上根本不会访问相应的分支。

Answer 2

我会利用 Haskell 的懒惰来发挥我的优势。将树转为列表（这是一个变形），创建部分和，并找到第一个大于限制的。

{-# language DeriveFoldable #-}

module ShortSum where
import Data.Foldable
  
data Tree a = Leaf a | Node (Tree a) (Tree a)
  deriving Foldable

type Nat   = Int
type TreeN = Tree Nat

sumLt :: Nat -> TreeN -> Bool
sumLt mx = any (> mx) . scanl1 (+) . toList

递归方案允许递归调用之间的依赖关系（有序的变形？）

Recursion scheme allowing dependencies between recursive calls (an ordered catamorphism?)

haskell

functional-programming

fold

category-theory

recursion-schemes