2015.08.07

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プログラミングを楽しみましょう！

Recruit Tech Blog

タグから見つける