Is this a meaningful generalization of `scan`s for arbitrary ADTs?

Question

I've been thinking how one could generalize scanl to arbitrary ADTs. The Prelude approach is just to treat everything as a list (i.e., Foldable) and apply the scanl on the flatened view of the structure. Instead, I tend to think of scanl as an operation that passes a state from each node of the tree to its children, while applying a monoidal op as it travels down from root to the leaves. So, for example, on Data.Tree, we have:

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

So that, for example:

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

Results in:

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

Which is the same as applying scanl through each path of the tree independently, preserving the original structure.

The question is rather simple: is this a meaningful generalization? I.e., is it commonly used, with a categorical explanation, and perhaps with a different name?

Answer 1

If you move to the fixpoint-of-functors "generic" representation of data, you can view a scan (or rather its slight generalization, a mapAccum) as a special type of generic fold.

Here's some code that sketches a pattern that you should be able to continue:

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 discusses this in passing in his article on Horners rule. He actually first described such things as "downward accumulations" in an article from 1992 on "Upwards and Downwards Accumulations on Trees".