Scalaプログラミングスタイル集
ポニー村山
はじめに
人によって様々な書き方ができてしまうのがScala。
本記事では、階乗を求めるfac関数を例に、いくつかの興味深いプログラミングスタイルを紹介します。
以下のコードは、REPLで:pasteすることで、簡単に動作を確認できます。
手続きプログラミング
破壊的操作をためらわない男らしいプログラミングスタイル。
def fac(n: Int) = {
var result = 1
for (i <- 1 to n) {
result *= i
}
result
}
再帰で書くより速い（はず）です。
普通の再帰
初学者泣かせの再帰スタイル。
def fac(n: Int): Int =
if (n == 0)
1
else
n * fac(n - 1) // 再帰呼び出しの外側に * による演算がある
このように書くとスタックをどんどん消費するので、後述する末尾再帰を使ったほうがいいでしょう。
パターンマッチ
Haskellでは一般的なパターンマッチスタイル。
def fac: Int => Int = {
case 0 =>
1
case n =>
n * fac(n - 1)
}
mapの引数などに無名関数として使うと便利です。
末尾再帰
性能の良い末尾再帰スタイル。
def facAcc(acc: Int, n: Int): Int =
if (n == 0)
acc
else
facAcc(n * acc, n - 1) // 関数の終わりに、単に自身を呼び出すのが末尾再帰
def fac(n: Int) = facAcc(1, n)
コンパイラの最適化によりループに置き換えられるので、スタックを無駄に消費しません。
@tailrecアノテーションを使うことで、関数が末尾再帰かをコンパイル時にチェックできます。
ここまで理解できていれば、Scalaを実務で使うのに十分な実力があると思います。
継続渡し
ちょっと奇妙な継続渡しスタイル。
def facCps(k: Int => Int, n: Int): Int =
if (n == 0)
k(1)
else
facCps(k compose (n * _), n - 1)
def fac(n: Int) = facCps((x: Int) => x, n)
かなり難解になってきましたが、実務では恐らく使わないので安心してください。
composeは、2つの関数を合成するメソッドです。
(f compose g)(x) = f(g(x))
facCpsでは、n == 0になるまで計算を遅延しています。
Yコンビネータ
無名関数の再帰ができるYコンビネータ。
def Y[A, B](f: ((A => B), A) => B, x: A): B =
f((y: A) => Y(f, y), x)
def fac(n: Int) =
Y[Int, Int]((f, n) => if (n == 0) 1 else n * f(n - 1), n)
facの中では再帰呼び出しを行っていないように見えますが、fの呼び出しが実質的に再帰呼び出しとなっています（普通の再帰で書いたものと見比べてみてください）。
foldLeft
foldLeftによる再帰の隠蔽。
def fac(n: Int) =
(1 to n).foldLeft(1)(_ * _)
foldLeftは末尾再帰で定義できるので、ほとんどの場合foldRightより高速に動作します。
また、foldLeftは実務でもよく登場するので、使い方を覚えておいて損はないと思います。
foldRight
foldRightによる再帰の隠蔽。
def fac(n: Int) =
(1 to n).foldLeft(1)(_ * _)
foldLeftと挙動が似ているが、Streamのような遅延評価されるデータ構造で真価を発揮します。
例えば、
Stream.from(1).foldRight(Stream[Int]())((x: Int, xs: Stream[Int]) => (x * x) #:: xs).take(10).toList
のようにすることで、無限リストの各要素を2乗するような操作が可能・・・と言いたかったのですが、動かしてみるとうまくいきません。Scalaの標準ライブラリはイケていないのです。
def foldr[A, B](combine: (A, =>B) => B, base: B)(xs: Stream[A]): B =
if (xs.isEmpty)
base
else
combine(xs.head, foldr(combine, base)(xs.tail))
foldr[Int, Stream[Int]]((x, xs) => (x * x) #:: xs, Stream())(Stream.from(1)).take(10).toList
気を取り直して、このように正しいfoldrを定義することで、無限リストを直接操作できます（combineの第二引数を名前渡しにしていることで、余計な評価を防いでいます）。
foldLeftではすべての要素を必ず評価するため、同様の操作を行うとプログラムがエラー停止します。
ポイントフリー
引数を書かないポイントフリースタイル。
def fac =
((_: List[Int]).foldLeft(1)(_ * _)) compose ((x: Int) => (1 to x).toList)
無名関数などで便利なこともありますが、難解なため多用はおすすめしません。
unfold
foldRightの双対となるunfold。
def unfold[A, B](p: A => Boolean, h: A => B, t: A => A, a: A): List[B] =
if (p(a))
Nil
else
h(a) :: unfold(p, h, t, t(a))
def fac =
((_: List[Int]).foldRight(1)(_ * _)) compose ((n: Int) => unfold[Int, Int](_ == 0, x => x, _ - 1, n))
foldRightがリストを消費するのに対し、unfoldはリストを生産します。
foldRightとunfoldを一般化し、それぞれCatamorphism, Anamorphismと呼ぶことがあります。
Hylomorphism
生産と消費を同時に行うHylomorphism。
def hylo[A, B, C](c: C, f: (B, C) => C, g: A => (B, A), p: A => Boolean, a: A): C =
if (p(a))
c
else {
val (b, a_) = g(a)
f(b, hylo(c, f, g, p, a_))
}
def fac(n: Int) =
hylo[Int, Int, Int](1, _ * _, n => (n, n - 1), _ == 0, n)
HylomorphismはCatamorphismとAnamorphismを合成したものだと言えます。
unfoldを使ったものと比べ、余計な中間構造を生成していないことに注目してください。
Paramorphism
全部のデータを使うParamorphism。
def paraInt[A](a: A, f: (Int, A) => A, n: Int): A =
if (n == 0)
a
else
f(n, paraInt(a, f, n - 1))
def fac(n: Int) =
paraInt[Int](1, (n, m) => n * m, n)
facの本体はかなりシンプルになっていますね。
ここではIntに対するParamorphismを定義したが、Listに対するParamorphismは次のようになります。
def paraList[A, B](b: B, f: (A, (List[A], B)) => B, list: List[A]): B = list match {
case Nil =>
b
case x :: xs =>
f(x, (list, paraList(b, f, xs)))
}
def tails[A](list: List[A]): List[List[A]] =
paraList[A, List[List[A]]](List(Nil), {
case (x, (xs, tls)) => xs :: tls
}, list)
ここで定義したtailsは、Paramorphismを利用する代表的な関数です。
paraListの引数として渡している無名関数の中で、リストの先頭要素xだけでなく、残りのxsも利用していますね。
このように、Catamorphismでは利用しなかった要素を計算に利用することで、自然に関数を定義できることがあります。
始代数、終余代数
抽象化の闇に呑まれたプログラミングスタイル。
こんなものは実務では絶対に使わないですが、興味がある人はパズルだと思って眺めてみてください
def id[A]: A => A =
a => a
case class :*:[+A, +B](a: A, b: B)
def prod[A, B](a: A, b: B) = :*:(a, b)
implicit class ProdCons[A](b: A) {
def :*:[B](a: B): B :*: A = prod(a, b)
}
implicit class ProdOps[A, B](f: A => B) {
def *|*[C, D]: (C => D) => A :*: C => B :*: D =
g => {
case a :*: b => f(a) :*: g(b)
}
}
trait :+:[+A, +B]
case class Inl[A](a: A) extends :+:[A, Nothing]
case class Inr[B](b: B) extends :+:[Nothing, B]
def inl[A, B](a: A) = Inl(a)
def inr[A, B](b: B) = Inr(b)
implicit class CoProdOps[A, C](f: A => C) {
def +|+[B, D]: (B => D) => A :+: B => C :+: D =
g => {
case Inl(a) => inl[C, D](f(a))
case Inr(b) => inr[C, D](g(b))
}
}
trait Functor[F[_]] {
def fmap[A, B]: (A => B) => F[A] => F[B]
def hylo[G[_], T, U](φ: G[U] => U)(η: F[U] => G[U])(ψ: T => F[T]): T => U =
a => φ(η(fmap(hylo(φ)(η)(ψ))(ψ(a))))
}
trait InitialAlgebra[F[_], T] extends Functor[F] {
def out: T => F[T]
def cata[A](φ: F[A] => A): T => A =
t => φ(fmap(cata(φ))(out(t)))
}
trait FinalCoalgebra[F[_], T] extends Functor[F] {
def inn: F[T] => T
def ana[A](ψ: A => F[A]): A => T =
a => inn(fmap(ana(ψ))(ψ(a)))
}
def cata[F[_], T, A](φ: F[A] => A)(implicit ia: InitialAlgebra[F, T]): T => A =
ia.cata(φ)
def ana[F[_], A, T](ψ: A => F[A])(implicit fc: FinalCoalgebra[F, T]): A => T =
fc.ana(ψ)
def hylo[F[_], G[_], T, U](φ: G[U] => U)(η: F[U] => G[U])(ψ: T => F[T])(implicit fa: Functor[F]): T => U =
fa.hylo(φ)(η)(ψ)
type FList[+A, +B] = Unit :+: A :*: B
// FLisは型引数を2つ取るため、部分適用した型をλに束縛する
implicit def ListAlgebras[X]: InitialAlgebra[({type λ[α] = FList[X, α]})#λ, List[X]] with FinalCoalgebra[({type λ[α] = FList[X, α]})#λ, List[X]] =
new InitialAlgebra[({type λ[α] = FList[X, α]})#λ, List[X]] with FinalCoalgebra[({type λ[α] = FList[X, α]})#λ, List[X]] {
def fmap[A, B]: (A => B) => FList[X, A] => FList[X, B] =
f => id[Unit] +|+ id[X] *|* f
def out: List[X] => FList[X, List[X]] = {
case Nil => Inl()
case x :: xs => Inr(x :*: xs)
}
def inn: FList[X, List[X]] => List[X] = {
case Inl(_) => Nil
case Inr(x :*: xs) => x :: xs
}
}
// 両者の挙動はほぼ同じだが、hyloバージョンは余計な中間構造を作らない
def fac = cata[({type λ[α] = FList[Int, α]})#λ, List[Int], Int]({
case Inl(_) => 1
case Inr(n :*: m) => n * m
}) compose ana[({type λ[α] = FList[Int, α]})#λ, Int, List[Int]]({
case 0 => Inl()
case n => Inr(n :*: n - 1)
})
def fac_ = hylo[({type λ[α] = FList[Int, α]})#λ, ({type λ[α] = FList[Int, α]})#λ, Int, Int]({
case Inl(_) => 1
case Inr(n :*: m) => n * m
}) (id) ({
case 0 => Inl()
case n => Inr(n :*: n - 1)
})
ものすごく難解ですが、これでちゃんと動きます。
これまで紹介してきたCatamorphism, Anamorphism, Hylomorphism。これらの背景には始代数と終余代数という概念があります。詳しい説明は省略しますが、一般的な再帰的データ型のほとんどは、始代数、終余代数とみなし、インスタンスを定義できます。
HylomorphismとCatamorphism, Anamorphismには、
hylo(φ)(id)(ψ) = cata(φ) compose ana(ψ)
という関係があります。また、
hylo(τ(φ compose η1))(η2)(ψ) = hylo(φ)(η1)(out) compose hylo(τ(inn))(η2)(ψ)
hylo(φ)(η1)(σ(η2 compose ψ)) = hylo(φ)(η1)(σ(out)) compose hylo(inn)(η2)(ψ)
として2つのHylomorphismを1つに融合可能なことが知られています（酸性雨定理）。
おわりに
Scalaの様々なプログラミングスタイルを紹介してきましたが、いかがでしたでしょうか。
自分の好きなスタイルを見つけて、Scalaプログラミングを楽しみましょう！