前回の記事の続き．

既に記事として書くのが面倒になってきた．
世間の関数型プログラミング言語を使っているプログラマは，Catamorphisms，Anamorphisms，Hylomorphisms，Paramorphisms くらい知っているのでは？（錯乱）

Anamorphism

今回は Anamorphism を見ていく．
Anamorphism の由来は，ギリシャ語の ἀνά（= 上方へ）から来ている．
Anamorphism では，A* 型のリストを B 型の値（種）から生成するということを考える．

定義

論文における定義は以下のようになっている．

述語 $p \in B \to \mathrm{bool}$ ，関数 $g \in B \to A || B$ が与えられたとき， list-anamorphism $h \in B \to A*$ は，以下のように定義される．

h b = Nil,                p b
    = Cons (a, h b'),     otherwise
      where (a, b') = g b

この Anamorphism は，多く関数型プログラミング言語で unfold と呼ばれている関数を一般化したものだ（ここではリストについてだけ見ているけど）．
論文では，Anamorphism $h$ は $g$ と $p$ が与えられたときに，上のように定めることができるため，

h = [( g,p )]

と書くこととしている．論文では，この [(・)] のことを 凹レンズ と読んでいる．
これは，記事のタイトルにあるレンズのことだ．

Scala におけるレンズ

さて，この list-anamorphism h を Scala に落とすと次にようになる．

object List {
  
  // 省略

  def ana[A, B](b: => B)(g: B => (A, B))(p: B => Boolean): List[A] = 
    p(b) match {
      case true  => nil
      case false =>
        val (a, bb) = g(b)
        cons(a, ana(bb)(g)(p))
    }
}

ここでは，List オブジェクトのメンバとして定義している．
g と p を明示的に引数として受けとるようにする以外は，先程見た定義をそのまま書き下しただけだ．

list-anamorphism で作ることができる関数

Anamorphism を実装することができたので，これを使って zip 関数と iterate 関数を実装してみる．
一応（？）論文の定義を載せておくと，

$\mathrm{zip} \in A* || B* \to (A || B)*$ は以下で定義される関数．

                          zip = [( g,p )]
                   p (as, bs) = (as = Nil) ∨  (bs = Nil)
g (Cons (a, as), Cons(b, bs)) = ((a,b), (as,bs))

となる．zip 関数を知っているならこれで zip 関数が定義できていることがわかると思う．

zip 関数の動作を Scala で簡単に説明すると，Scala だと GenIterableLike トレイトでメソッドとして定義されており， List(1, 2, 3) zip List(4, 5, 6, 7) を実行すると List((1, 4), (2, 5), (3, 6)) のように各コレクションの要素を先頭から組にしたリストが得られる．
このとき，リストの長さは短い方に合わされる．
この zip Scala で先程定義した ana 関数を使って実装すると次のようになる．

sealed trait List[A] { self =>

  // 省略

  def zip[B](bs: List[B]): List[(A, B)] = {
    def g(seed: (List[A], List[B])): ((A, B), (List[A], List[B])) = {
      val (Cons(a, as), Cons(b, bs)) = seed
      ((a, b), (eval(as), eval(bs)))
    }

    def p(seed: (List[A], List[B])): Boolean = {
      val (as, bs) = seed
      as == Nil() || bs == Nil()
    }

    List.ana((self, bs))(g)(p)
  }
}

上で見た定義をそのまま書き下しただけなわけだが…．

次に iterate 関数を見る．
論文における定義は，型とか書いてないので補足すると，

$\mathrm{iterate} \in (A \to A) \to A \to A*$ は以下で定義される関数．

iterate f = [( g, false* )] where g a = (a, f a)

iterate 関数は，ある値 a と関数 f を受け取って，[a, f(a), f(f(a)), f(f(f(a))), ...] という無限に続くリストを返す関数になっている．
今回，記事を書くにあたって遅延リストを使っていた理由はこのためだ．

さて，この iterate 関数を Scala に落とすと次のようになる．

object List {
  
  // 省略

  def iterate[A](f: A => A)(a :A): List[A] = {
    def g(seed: A): (A, A)  = (seed, f(seed))
    def p(seed: A): Boolean = false

    List.ana(a)(g)(p)
  }
}

ana 関数と同様に，List オブジェクトのメンバとして定義した．
これも上で見た定義をそのまま書き下しただけ．

さて，Anamorphism で定義できる関数を 2 つ見たが，この他に map 関数も ana 関数で定義することができる．
map 関数は Catamorphisms の一つとも見ることができるし，Anamorphisms の一つとも見ることができるようだ．

今回は，この辺で．ana 関数を使って map 関数を定義するのは，この記事を読んだ人がやるということで．
次回は，Hylomorphisms．

M-x tkhsh

Scalaプログラマのためのバナナ，レンズ，封筒，有刺鉄線による関数型プログラミング〜リストレンズ編〜

Anamorphism

定義

Scala におけるレンズ

list-anamorphism で作ることができる関数