haskell - 这是对任意 ADT 的 `scan` 的有意义的概括吗？

Question

我一直在想如何概括scanl到任意 ADT。 Prelude 方法只是将所有内容视为一个列表(即 Foldable )并应用 scanl在结构的平面 View 上。相反，我倾向于想到 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

如果您转向仿函数的固定点“通用”数据表示，您可以将扫描(或者更确切地说是它的轻微概括，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)

Gibbons 在他的 article 中顺便讨论了这个问题。关于霍纳斯的统治。他实际上首先在 article from 1992 中描述了诸如“向下积累”之类的东西。关于“树上的向上和向下的堆积”。