递归方案允许递归调用之间的依赖关系(有序的同构吗?) [英] Recursion scheme allowing dependencies between recursive calls (an ordered catamorphism?)

问题描述

我对以更高阶的方式(递归方案)编写递归代码感兴趣，其中递归调用之间可能存在依赖关系.

I'm interested in a higher-order way (recursion scheme) to write recursive code in which there might be dependencies between recursive calls.

作为一个简化的示例，考虑一个遍历整数树的函数，检查和是否小于某个值.我们可以对整个树求和并将其与最大值进行比较.另外，一旦超过最大值，我们就可以保持连续和短路:

As a simplified example, consider a function that traverses a tree of integers, checking if the sum is less than some value. We could sum the entire tree and compare it against the maximum. Alternatively, we could keep a running sum and short-circuit as soon as we've exceeded the maximum:

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

是否有一种方法可以通过递归方案表达这种想法-本质上是有序遍历?我对像这样的一般可能的有序遍历感兴趣.

Is there a way to express this idea -- essentially an ordered traversal -- with a recursion scheme? I'm interested in as-generically-as-possible composing ordered traversals like this.

理想情况下，我想以某种方式编写遍历，其中在数据结构上折叠(或展开)的函数确定遍历的顺序.无论我最终得到什么抽象，我都希望能够编写上面遍历的 sumLT'遍历的反序版本，而不是从右到左:

Ideally, I'd like some way to write traversals in which the function being folded (or unfolded) over the data structure determines the order of traversal. Whatever abstraction I end up with, I'd like to be able to also write the reverse-ordered version of the sumLT' traversal above, where we go right-to-left instead:

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

推荐答案

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

As usual, folding into endofunctions gives you a notion of processing order / state passing:

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的第二个参数(节点折叠功能)不要求其参数之一的值，则实际上根本不会访问相应的分支.

As is also usual, Haskell's laziness provides for the ability to short-circuit / exit early. As can be seen in the examples, if cata's second argument, the node-folding function, does not demand the value of one of its arguments, the corresponding branch is not actually visited at all.

这篇关于递归方案允许递归调用之间的依赖关系(有序的同构吗?)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！