我对编写递归代码的高阶方式(递归方案)感兴趣,其中递归调用之间可能存在依赖关系。
作为一个简化的示例,考虑一个遍历整数树的函数,检查总和是否小于某个值。我们可以对整个树求和并将其与最大值进行比较。或者,我们可以保持运行总和,并在超过最大值后立即短路:
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
最佳答案
像往常一样,折叠到内函数中可以为您提供处理顺序/状态传递的概念:
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 的第二个参数(节点折叠函数)不需要其参数之一的值,则根本不会实际访问相应的分支。
关于haskell - 递归方案允许递归调用之间的依赖关系(有序变形?),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/65959897/