haskell - 是否有不可折叠的东西的 map 累积？

Question

假设我有一个二叉树:

data BinTree a
  = Nil
  | Branch a (BinTree a) (BinTree a)

我想在这样的结构上做一个累积映射:

mapAccum ::
  (
  )
    => (a -> b -> (c, a)) -> a -> BinTree b -> BinTree c
mapAccum func x Nil =
  Nil
mapAccum func x (Branch y left right) =
  let
    (y', x') =
      func x y
  in
    Branch y' (mapAccum func x' left) (mapAccum func x' right) 

它在整个结构中执行带有累加器的映射。

然而，这是一个非常普遍的模式。我们可以在各种树状结构上执行此操作，如果有一个很好的、通用的抽象，我宁愿使用它而不是在这里滚动我自己的。

Traversable 上有一个函数:

mapAccumL :: Traversable t => (s -> a -> (s, b)) -> s -> t a -> (s, t b)

哪种在列表上做同样的事情。但它需要 Foldable，这意味着它不适用于二叉树。我正在寻找的是一个更基本的版本，它可以在没有 Foldable 的情况下工作。

我可以让它在使用 Cofree 制作的类型上工作:

mapAccum ::
  ( Functor f
  )
    => (a -> b -> (c, a)) -> a -> Cofree f b -> Cofree f c
mapAccum func x (y :< rest) =
  let
    (y', x') =
      func x y
  in
    y' :< fmap (mapAccum func x') rest

这表明它至少普遍适用于树状结构。

这个函数有通用的抽象吗？

Answer 1

这是您使用 bifunctors 和 recursion-schemes 包编写的内容的概括:

{-# LANGUAGE TemplateHaskell, TypeFamilies #-}

import Control.Monad.Trans.State.Lazy
import Data.Bifunctor.TH
import Data.Bitraversable
import Data.Functor.Foldable
import Data.Functor.Foldable.TH

data BinTree a = Nil | Branch a (BinTree a) (BinTree a)
makeBaseFunctor ''BinTree
deriveBifunctor ''BinTreeF
deriveBifoldable ''BinTreeF
deriveBitraversable ''BinTreeF

mapAccum :: (Base tc ~ f c, Base tb ~ f b, Bitraversable f, Recursive tb,
  Corecursive tc) => (a -> b -> (c, a)) -> a -> tb -> tc
mapAccum func x ys = embed ys' where
  (ys', x') = runState (bitraverse (state . flip func) (pure . mapAccum func x') (project ys)) x

-- a slightly less general version, but that's usually good enough,
-- and will fix most ambiguous type errors
mapAccum' :: (Base (t c) ~ f c, Base (t b) ~ f b, Bitraversable f, Recursive (t b),
  Corecursive (t c)) => (a -> b -> (c, a)) -> a -> t b -> t c
mapAccum' = mapAccum

它的工作方式是遍历树的当前元素中的所有值(特别是对于您的树，这始终只是一个元素)，转换它们并得出一个新的累加器值，然后使用该值递归地调用树的每个子元素。此外，由于它是惰性状态，它打结了所以它只需要遍历结构一次而不是两次。换句话说，请注意 x' 来自 runState 的输出，但它是作为参数的一部分传递给它的。在严格的语言中，这会导致无限循环，但由于 Haskell 是惰性的，x' 直到需要它时才会计算，此时生成它的代码部分已完成。