日々の流転

λ. Almost homomorphisms

横山さんの日記を読んでいて、Almost homomorphism が分からなかったので、ググってみた。Optimizing Compositions of Scans and Reductions in Parallel Program Derivation とかを見ると、どうやら h をhomomorphism、πを射影として、π∘h と書けるもののようだ。

[追記] 横山さんの日記に出てきたのは、モノイドに関する homomorphisms と almost-homomorphisms 。

[追記] 横山さんによると「やはり、homomorphism と合成するのは射影関数とは限らなそうです」とのこと。

λ. Mutumorphisms

almost homomorphisms と関係がありそうなので、ついでに mutumorphisms についてもググってみた。これは以下のような形で書ける関数族 { f_i : μF → A_i }_i∈I のことのようだ*1。

f_i: μF → A_i
f_i = φ_i ∘ Fh ∘ in_F^-1

φ_i: F(∏_j∈I A_j) → A_i
φ_i = ...

h: μF → ∏_i∈I A_i
h = <f_i>_i∈I

この定義から h = (| <φ_i>_i∈I |)_F かつ f_i = π_i ∘ h であることが直ちに言えるので、f_i はF代数に関する almost homomorphism であり、catamorphism の almost- なので、almost-cata とも呼ばれる。

almost-cata の典型的な例は paramorphisms とその一般化である zygomorphisms。

λ. almost-catamorphism

f を cata とするとき，

accept . f      -- accept は fst, snd, (\ (x,y) -> x + y) など

なるほど。解説ありがとうございます。しかし、そうなると今度は accept として許される関数のクラスが気になります。comcatamorphisms *1 は全て almost-catamorphism と呼べるのだろうか?