Skip to content

Instantly share code, notes, and snippets.

@Gab-km Gab-km/hchobi_1.md
Last active Aug 29, 2015

Embed
What would you like to do?
この記事( http://d.hatena.ne.jp/kamekoopa/20141024/1414134734 )にインスピレーションされた。

List

  /\
a1 /\
  a2  /\
    a3   nil

foldr

   f
  /\
a1    f
    /\
   a2    f
        /\
      a3   zero

似ている*2。


foldrの最も汎用的な形がList*4。

foldrの始対象がList*5。

ListはF代数の圏におけるF始代数*6

List                             foldr f
  /\                               /\
a1  /\     <------ 抽象的 ------  a1   f
  a2  /\   - 関数(射)が作れそう->     /\
    a3   nil                          a2    f
                                           /\
                                         a3  zero

List

   cons
   /\
 a1  cons
      /\
    a2   cons
         /\
        a3  nil

foldr

   f
  /\
a1    f
    /\
   a2    f
        /\
      a3   zero

似ている*2。


foldrの最も汎用的な形がList*4。

foldrの始対象がList*5。

ListはF代数の圏におけるF始代数*6

List cons                          foldr f
     /\                               /\
   a1   cons    <------ 抽象的 ------  a1   f
        /\   - 関数(射)が作れそう->     /\
      a2   cons                         a2    f
           /\                              /\
          a3  nil                          a3  zero
f: A * Y -> Y     g: A * Z -> Z

                   ∮ = foldr f zero
X = List<A>   --------------------------->   F<X> = Y
     ex) cons(a1, cons(a2, cons(a3, nil)))    ex) f(a1, f(a2, f(a3, zero))) = y
 id ↓                                       ↓ τ: F<X> -> G<X> = Y -> Z
                   γ = foldr g zero
X = List<X>   --------------------------->   G<X> = Z
     ex) cons(a1, cons(a2, cons(a3, nil)))    ex) g(a1, g(a2, g(a3, zero))) = z

    ∮
X----->Y
 \     |
γ \   | τ
     \ ↓
        Z

τ・∮ = γ である τ を考えることができる…?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.