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

Question

I was thinking how can I generalize scanl to arbitrary scanl . Prelude's approach is to treat everything as a list (i.e., Foldable ) and apply scanl on a folded structure. Instead, I tend to think of scanl as an operation that passes state from each node of the tree to its children, using a monoidal op when it moves from root to 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 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 

The same as using scanl through each tree path independently, preserving the original structure.

The question is quite simple: is this a meaningful generalization? Ie, is it usually used with a categorical explanation and possibly with a different name?

Answer 1

If you go to the “generalized” data representation of “fixpoint-of-functors”, you can view the scan (more precisely, a small generalization of it, a mapAccum ) as a special type of common fold.

Here is the code that will outline the template that you must continue with:

 data Fix fa = Roll (fa (Fix fa)) cata :: Functor (fa) => (fab -> b) -> Fix fa -> b cata alg (Roll x) = alg $ fmap (cata alg) x scan :: Functor (fa) => (fa (acc, Fix fb) -> (acc, fb (Fix fb))) -> Fix fa -> Fix fb scan alg = snd . cata (fmap Roll . alg) data ListF ab = NilF | ConsF ab deriving Functor scanAlgList fz NilF = (z, NilF) scanAlgList fz (ConsF a (acc,b)) = let val = fa acc in (val, ConsF val b) data TreeF ab = LeafF a | BranchF abb deriving Functor scanAlgTree f (LeafF x) = (x, LeafF x) scanAlgTree f (BranchF v (accL,l) (accR,r)) = let val = fv accL accR in (val, BranchF vlr) 

Gibbons discusses this in passing in her article regarding the Horners rule. He actually first described things like “top-down accumulations” in a 1992 article “Up and down accumulations on trees”.