Functional Programming with Banas, Lenses, Envelopes and Barbed Wire という論文を読んだので，そこで書かれている内容を Scala で実装してみる．

論文の PDF は reddit に落ちているっぽい．この論文は有名で，いくつかの Scala に関する記事でも紹介されているし，もちろん Haskell に関する記事でも触れられている．
ScalaMatsuri でこの論文に関するセッションがあったようだが，自分は参加していないので，そこでどのような内容が話されたのかわからない．
もしかしたら，この記事で書こうとしている内容と被っているのかもしれない．
その辺は気にしないでいこうと思う．
この記事は，論文を読んだときの個人的なメモであることを心にとめて読んでもらえると幸い．

件の論文が執筆されたのは，1991 年なので今となっては当然のこととして考えられていることを多く含むと思われるが，自分を含めた関数型プログラミングの初学者にとっては，有益な情報を多く含んでいる．
また，関数型プログラミング言語を普段から使っている人であっても，プログラミングに関してこの論文で述べられているような視点から関数を見たことがない人は，新たな視点を得ることができると思う．

論文中で書かれていること全てについて触れるつもりは無いため，この記事で件の論文に興味を持ったならば直接そちらを読むことをおすすめする．

また，この記事内で触れる内容は，Scala による関数型プログラミングの入門（？）的なサイトとして知られている独習 Scalaz や猫番で書かれている内容と被るところがあるかもしれない．

対象読者

Scala の基本的な文法を理解しており，関数型プログラミングに興味がある人．

リストデータ型

まず始めにリストを定義しよう．
もちろん汎用的なリストだ．

論文では，次のように定義されている．

A* = Nil | Cons (A || A*)

ここでは $A*$ がリストで $|$ が直和， $||$ が直積を表している．
これを Scala に落とすと次のようになる．

// A* ::= Nil | Cons (A||A*)
sealed trait List[A]
case class Nil[A]() extends List[A]
case class Cons[A](a: A, as: () => List[A]) extends List[A]

Scala でいうところの普通の List とは異なることに注意して欲しい．
恐らく，普通にリストを定義しろと言われたら次のようになると思う．

sealed trait List[A]
case class Nil[A]() extends List[A]
case class Cons[A](a: A, as: List[A]) extends List[A]

もしくは，

sealed trait List[+A]
case object Nil extends List[Nothing]
case class Cons[+A](a: A, as: List[A]) extends List[A]

ここでは，遅延リストを扱いたいので，最初に示したリストを使っていく．
実際にこの実装は，Scala の標準ライブラリの Stream に近いものになっている．
型変数の違いについては，今回の話では特に関わってこないと思うので気にしなくてもよい．

さて，List を遅延リストとして実装しているため，このままだと使い難い．
そこで，次のようなユーティリティメソッドとエイリアスを定義しておく．

package object Lazy {

  type Thunk[A] = () => A

  def thunk[A](a: => A): () => A =
    () => a

  def eval[A](a: () => A): A =
    a()
}

ここで thunk は評価を遅延し，eval で遅延された評価を行うようなものだと思ってもらえればよい．
何故このような面倒な定義をしているのかと言えば，無限リストでなければ扱えないような例が出てくるからだ．

これらを使い改めてリストを定義しておく．() => List[A] の代わりに Thunk[List[A]] を使うようにするだけだ．

sealed trait List[A]
case class Nil[A]() extends List[A]
case class Cons[A](a: A, as: Thunk[List[A]]) extends List[A]

序盤は，ここで定義したリストを用いて Catamorphisms, Anamoriphisms, Hylomorphisms, Paramorphisms について見ていく．
あまり，一つの記事が長くなると読むのが大変なので，今回は Catamorphisms を見ていく．

Catamorphisms

Catamorphisms の由来は，ギリシャ語の κατά (= 下方へ) から来ているようだ．
Catamorphisms は Scala を含む多くの関数型言語で使われている fold 関数を一般化したものだ（ここではリストに限定して見ていくが）．

定義

論文における定義は次のようになっている．
$b \in B$ ， $\oplus \in A || B \to B$ とすると，list-catamorphism $h \in A* \to B$ は次のような形の関数

           h Nil = b
h (Cons (a, as)) = a ⊕ (h as)

のことである．
この関数は $b$ と $\oplus$ によって定まるので

h = (| b,⊕ |)

と書くことにする．論文ではこの (|・|) のことを バナナ括弧 と呼んでいる．
記事のタイトルのバナナはこれのこと．

Scala におけるバナナ

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

sealed trait List[A] { self =>
  def cata[B](b: => B)(f: (A, B) => B): B = self match {
    case Nil()       => b
    case Cons(a, as) => f(a, eval(as).cata(b)(f))
  }
}

ここでは，List トレイトのメソッドとして実装している．
これは Scala の Stream における as.foldRight(b)(f) と同じような動きをする．
ちなみに scala.collection.immutable.List の場合，foldRight は reverse してから foldLeft するようになっている．

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

さて，この cata 関数を使うとリストの長さを返す関数 length とリストの要素からある条件を満す要素だけからなるリストを返す関数 filter を実装することができる．

length = (| 0,⊕ |) where a ⊕ n = 1 + n
filter p = (| Nil,⊕ |)
           where a ⊕ as = Cons (a,as),  p a
                         = as,           ¬p a

これを Scala に落とすと，

import Lazy._

sealed trait List[A] { self =>

  // 省略

  def length: Int =
    self.cata(0) { (a, n) => 1 + n }

  def filter(p: A => Boolean): List[A] =
    self.cata(Nil[A](): List[A]) { (a, as) =>
      p(a) match {
        case true  => Cons(a, thunk(as))
        case false => as
      }
    }
}

この例からわかるように cata 関数からさまざまな関数を作ることができる．
map 関数も cata 関数により定義できるので，興味を持った人は試みてみるといいと思う．

論文では，この後に Fusion に対する言及があるが，この記事では触れないでおこうと思う．
後々，必要になったら書くかもしれない．

1 つ目の記事としては，この辺で．
次の記事では Anamoriphism について見る．

M-x tkhsh

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

対象読者

リストデータ型

Catamorphisms

定義

Scala におけるバナナ

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