圏論勉強会@ワークスアプリケーションズ #8 練習問題

圏論

第8回は実装の練習問題があったのでSMLで書いてみました。
https://gist.github.com/eldesh/5970931
fact' の実装に自信ないけど他はだいたい合ってるんじゃないでしょうか…。

練習問題
自然数型,リスト型,二分木などのhylomorphismを導出して下さい。

http://nineties.github.io/category-seminar/8.html#/54

こっちへの回答は以下。 (h o u) がそれぞれの型の hylomorphism になります。

    X --- f ---> F(X)
  u ↓            ↓ F(u)
    T <--------> T(X)
  h ↓            ↓ F(h)
    X <-- p ---- F(X)

(* 自然数( F(X) = 1 + X ) のhylomorphism *)
h(u(0)) = p(0)
h(u(1+n)) = p(1+h(u(n)))

(* リスト( F(X) = 1 + A * X ) のhylomorphism *)
h(u(nil)) = p(nil)
h(u(cons(a,as))) = p(a,h(u(as)))

(* 二分木( F(X) = A + X * X ) のhylomorphism *)
h(u(Leaf x)) = p (x)
h(u(Node(l,r)) = p (hl(ul(l)), hr(ur(r)))

f がF余代数の射なのでそれぞれ上の定義が場合分けされ、p がF代数なので実装では二つの関数を持っていることになる(場合分け毎に使い分ける)。

こんな感じでいいのかな


さて今日は第9回です。そろそろ人数が少なくなって来ましたね…。