代码之家  ›  专栏  ›  技术社区  ›  trpnd

递归方案允许递归调用之间的依赖关系(有序的同态?)

  •  0
  • trpnd  · 技术社区  · 4 年前

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

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

    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
    
    0 回复  |  直到 4 年前
        1
  •  2
  •   Will Ness Derri Leahy    4 年前

    像往常一样,折叠到内函数中会给你一个处理顺序/状态传递的概念:

    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 第二个参数是节点折叠函数,它不要求其中一个参数的值,相应的分支实际上根本不会被访问。

        2
  •  0
  •   Bartosz Milewski    4 年前

    我会利用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