Si tratta di una generalizzazione significativa di `scan`s per ADT arbitrari?

Question

Ho pensato a come generalizzare scanl in ADT arbitrari. L'approccio Prelude consiste nel trattare tutto come un elenco (ad esempio, Foldable) e applicare lo scanl sulla vista piatta della struttura. Invece, tendo a pensare a scanl come a un'operazione che passa uno stato da ciascun nodo dell'albero ai suoi figli, mentre applica un op monoidale mentre scende dalla radice alle foglie. Così, per esempio, su Data.Tree, abbiamo:

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 

In modo che, ad esempio:

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

Risultati in:

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

Che è lo stesso che si applica scanl attraverso ogni percorso dell'albero in modo indipendente, preservando la struttura originale.

La domanda è piuttosto semplice: si tratta di una generalizzazione significativa? Ad esempio, è comunemente usato, con una spiegazione categorica e forse con un nome diverso?

Answer 1

Se si passa alla rappresentazione "generica" ​​dei dati del fixpoint-of-functors, è possibile visualizzare una scansione (o piuttosto la sua leggera generalizzazione, a mapAccum) come un tipo speciale di piega generica.

Ecco alcuni codice che disegna un modello che si dovrebbe essere in grado di continuare:

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 discute questo di passaggio nel suo article su Horners regola. In realtà ha descritto per la prima volta cose come "accumulazioni verso il basso" in un article from 1992 su "Accumuli verso l'alto e verso il basso sugli alberi".