Ist das eine sinnvolle Verallgemeinerung von `scan`s für beliebige ADTs?

Question

Ich habe darüber nachgedacht, wie man scanl zu beliebigen ADTs verallgemeinern könnte. Der Prelude-Ansatz besteht darin, alles als eine Liste zu behandeln (d. H. Foldable) und die scanl auf die erweiterte Ansicht der Struktur anzuwenden. Stattdessen tendiere ich dazu, an scanl als eine Operation zu denken, die einen Zustand von jedem Knoten des Baums an seine Kinder weitergibt, während er eine monoidale Operation anwendet, wenn er von der Wurzel zu den Blättern hinwandert. So zum Beispiel auf Data.Tree, haben wir:

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 dass zum Beispiel:

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

Ergebnisse in:

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

, die die gleiche ist wie scanl durch jede Anwendung Pfad des Baumes unabhängig, Erhaltung der ursprünglichen Struktur.

Die Frage ist ziemlich einfach: Ist das eine sinnvolle Verallgemeinerung? Das heißt, wird es allgemein verwendet, mit einer kategorischen Erklärung und vielleicht mit einem anderen Namen?

Answer 1

Wenn Sie zu der "generischen" Darstellung der Daten des Fixpunkt-von-Funktoren übergehen, können Sie einen Scan (oder eher seine leichte Verallgemeinerung, eine mapAccum) als eine spezielle Art von generischer Faltung betrachten.

Hier ist ein Code, der ein Muster Skizzen, die Sie sollten weiterhin in der Lage sein: in seiner nebenbei article auf Horners Regel

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 bespricht dies. Er beschrieb zum ersten Mal solche Dinge als "Abwärtsanhäufungen" in einer article from 1992 über "Aufwärts- und Abwärtsanhäufungen auf Bäumen".