对于任意ADT,这是一个有意义的`scan`s'概括吗？

Question

我一直在想如何能够推广scanl到任意的ADT.Prelude方法只是将所有内容视为列表(即Foldable),并应用于scanl结构的flatened视图.相反,我倾向于scanl将一个状态从树的每个节点传递给它的子节点的操作,同时当它从根向下传播到叶子时应用一个单一操作.所以,例如Data.Tree,我们有:

scan :: (b -> a -> b) -> b -> Tree a -> Tree b
scan fn init (Node element children) 
    = Node (fn init element) 
        $ map (treeScan fn (fn init element)) children

所以,例如:

main = do
    prettyPrint $ scan (+) 0 $
        Node 1 [
            Node 1 [
                Node 1 [], 
                Node 1 []],
            Node 1 [
                Node 1 [], 
                Node 1 []]]

结果是:

1
|
+- 2
|  |
|  +- 3
|  |
|  `- 3
|
`- 2
   |
   +- 3
   |
   `- 3

这与scanl通过树的每个路径独立应用相同,保留原始结构.

问题很简单:这是一个有意义的概括吗？即,它是常用的,带有明确的解释,也许有不同的名称？

Answer 1

如果您转向数据的定点函子“通用”表示，您可以将扫描（或者更确切地说，它的轻微概括， a mapAccum）视为特殊类型的通用折叠。

下面是一些代码，勾勒出一个您应该能够继续的模式：

data Fix f a = Roll (f a (Fix f a))

cata :: Functor (f a) => (f a b -> b) -> Fix f a -> b
cata alg (Roll x) = alg $ fmap (cata alg) x

scan :: Functor (f a) => (f a (acc, Fix f b) -> (acc, f b (Fix f b))) -> Fix f a -> Fix f b
scan alg = snd . cata (fmap Roll . alg)

data ListF a b = NilF | ConsF a b deriving Functor

scanAlgList f z NilF = (z, NilF)
scanAlgList f z (ConsF a (acc,b)) =
            let val = f a acc
            in (val, ConsF val b)

data TreeF a b = LeafF a | BranchF a b b deriving Functor

scanAlgTree f (LeafF x) = (x, LeafF x)
scanAlgTree f (BranchF v (accL,l) (accR,r)) =
            let val = f v accL accR
            in (val, BranchF v l r)

吉本斯在他关于霍纳斯规则的文章中顺便讨论了这一点。实际上，他在1992 年的一篇文章“树上的向上和向下积累”中首次描述了“向下积累”这样的东西。