Czy jest to znaczące uogólnienie "skanów" dla arbitralnych ADT?

Question

Zastanawiam się, w jaki sposób można uogólnić scanl na arbitralne ADT. Podejście Prelude ma traktować wszystko jako listę (tj. Foldable) i zastosować scanl w płaskim widoku struktury. Zamiast tego, myślę o scanl jako operacji, która przechodzi stan z każdego węzła drzewa do jego dzieci, podczas stosowania operacji monoidal op, gdy przemieszcza się od korzenia do liści. Tak więc, na przykład, na Data.Tree, mamy:

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 

tak, że na przykład:

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

Wyniki w:

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

który jest taki sam jak stosowanie scanl przez każdy ścieżka drzewa niezależnie, zachowując oryginalną strukturę.

Pytanie jest raczej proste: czy jest to znaczące uogólnienie? Czy jest to powszechnie stosowane, z kategorycznym wyjaśnieniem, a może z inną nazwą?

Answer 1

Po przejściu do "ogólnej" reprezentacji danych "fixpoint-of-funktorów" można wyświetlić skan (a raczej jego niewielkie uogólnienie, mapAccum) jako specjalny typ ogólnego fałdu.

Oto niektóre kod, który kreśli wzór, który powinien być w stanie kontynuować:

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 omawia to mimochodem w swojej article na Horners reguły. Po raz pierwszy opisał takie rzeczy, jak "akumulacja w dół" w "Akumulacji w górę i w dół na drzewach" w article from 1992.