これは、任意のADTに対する `scan`sの意味のある一般化ですか？

Question

私はscanlを任意のADTに一般化する方法を考えてきました。プレリュードのアプローチは、すべてをリスト（すなわち、Foldable）として扱い、構造の平坦なビューにscanlを適用することです。代わりに、私はscanlを、ツリーの各ノードからその子に状態を渡す操作として考える傾向がありますが、ルートから葉まで移動する際にはモノオプルのopを適用します。したがって、たとえば、Data.Treeに、我々は持っている：だから

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 

、例えば：

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

結果内：各を通じてscanlを適用すると同じです

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

元の構造を保持しながら独立してツリーのパスを作成します。

質問は簡単です：これは意味のある一般化ですか？つまり、それは一般的に使用されているのでしょうか？

Answer 1

ファンクショナル・ファンクショナの「一般的な」データ表現に移動すると、特別なタイプの一般的な折りたたみとしてスキャン（またはそのわずかな一般化、mapAccum）を表示できます。

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) 

ギボンズが彼article Horners上のルールに渡しでこれを説明します。

は、ここでは、継続することができるはずのパターンをスケッチいくつかのコードです。彼は実際には、「上向きと下向きの木の累積」の article from 1992に「下向きの累積」というものを最初に記述しました。