Scalaz で Codensity モナド

Scalaz の Codensity を試してみました。

Codensity モナドは継続モナドと基本的に同じですが、処理の型が以下のように異なっています。

継続モナドの場合 Codensityモナドの場合
(A => R) => R (A => F[B]) => F[B]

つまり、Codensity は何らかのコンテナ(List・Option 等)で包んだ値(上記の F[B] に該当)を返します。

処理結果をモナド化する用途等に使えそうですが、効果的なサンプルを思いつかなかったので、
とりあえずは id:fits:20121125 の継続モナドのサンプルと同等のものを実装してみました。


サンプルソースは http://github.com/fits/try_samples/tree/master/blog/20121222/


今回使用した sbt 用のビルドファイルは以下の通りです。

build.sbt
scalaVersion := "2.10.0-RC5"

libraryDependencies += "org.scalaz" % "scalaz-core" % "7.0.0-M6" cross CrossVersion.full

Codensity の単純なサンプル

まずは、Codensity のメソッドをいくつか試してみます。

Codensity はトレイトとコンパニオンオブジェクトからなるシンプルな構成で、id:fits:20121125 で作成した継続モナドの runCont に該当するのが apply メソッドです。

また、以下のようなメソッドが Codensity コンパニオンオブジェクトに用意されています。

メソッド名 処理内容
pureCodensity 普通の値から Codensity を作成
rep 値を格納したコンテナから Codensity を作成

下記サンプルの (1) 〜 (3) では apply の結果として Function0[Unit] ・ List[Int] ・ Option[Int] をそれぞれ返すようにしてみました。 println(x)" の部分が Function0[Unit] に該当">*1

以降のサンプルでは Codensity の apply を省略せずに使うようにしています。

CodensitySample.scala
package fits.sample

import scalaz._
import Scalaz._

object CodensitySample extends App {
    // (1) Codensity[Function0, Int] で apply の結果は Function0[Unit]
    Codensity.pureCodensity(1).apply { (x) => () => println(x) }()

    // (2) Codensity[List, Int] で apply の結果は List[Int]
    Codensity.pureCodensity(2).apply { (x) => List(x) } |> println

    // (3) Codensity[Option, Int] で apply の結果は Option[Int]
    Codensity.pureCodensity(3).apply { Option(_) } |> println

    // (4) rep を使って List[Int] から Codensity[List, Int] を作成
    Codensity.rep(List(1, 2)).apply { (x) => List(x, x * 10, x * 100) } |> println

    /* (5) バインド >>= を使うには improve を使う
     *   'Codensity.pureCodensity(5) >>= ・・・' とするとコンパイルエラー
     */
    (Codensity.pureCodensity(5).improve >>= { (x) => Codensity.pureCodensity[Option, Int](x + 3) }) apply { (x) => Option(x * 10) } foreach(println)
}

なお、pureCodensity を使う際にコンテナの型 (型パラメータ F) が自明でなければ (5) の "Codensity.pureCodensity[Option, Int](x + 3)" のように型を明示します。

実行結果
> sbt console
・・・
scala> fits.sample.CodensitySample.main(null)
1
List(2)
Some(3)
List(1, 10, 100, 2, 20, 200)
80

flatMap の処理

前回ののバインド処理サンプルと同様のものを Codensity で実装してみました。
ここではバインド >>= の代わりに flatMap で処理を繋げ、apply には値を Option に格納する関数を渡しています。

CodensitySample2.scala
・・・
object CodensitySample2 extends App {

    def cont[F[+_]](a: Int) = Codensity.pureCodensity[F, Int](a)

    def calc1[F[+_]](x: Int) = cont[F](x + 3)

    def calc2[F[+_]](x: Int) = cont[F](x * 10)

    def calc3[F[+_]](x: Int) = cont[F](x + 4)

    def calcAll[F[+_]](x: Int) = cont[F](x).flatMap(calc1).flatMap(calc2).flatMap(calc3)

    // a. 2 + 3 = 5
    calc1(2).apply { Option(_) } foreach(println)

    // b. ((2 + 3) * 10) + 4 = 54
    calcAll(2).apply { Option(_) } foreach(println) 

    // c. 54 - 9 = 45
    calcAll(2).apply { (x) => Option(x - 9) } foreach(println)
}
実行結果
scala> fits.sample.CodensitySample2.main(null)
5
54
45

callCC の実装

実用性はともかく、次は callCC を Codensity で実装してみました。

継続モナドにおける callCC の肝は以下の処理ですが。

  • 入れ子になった継続モナドにおいて、自分に渡された継続(関数)を無視して親の継続を呼び出す

Scalaz の Codensity では apply メソッドを実装しなければならない関係上、本来無視するはずの関数の戻り値の型に依存してしまい工夫が必要となります。

Codensity トレイトの apply メソッド
def apply[B](f: A => F[B]): F[B]

例えば、以下のように実装すると (1) の型パラメータ C と (2) の型パラメータ C は別物なのでコンパイル時に type mismatch エラーが発生します。

コンパイルエラー(type mismatch)が発生する callCC の実装例
def callCC[F[+_], A, B](f: (A => Codensity[F, B]) => Codensity[F, A]): Codensity[F, A] = {
    new Codensity[F, A] { 
        // (1)
        def apply[C](k: A => F[C]) = {
            f { a: A =>
                new Codensity[F, B] {
                    // (2) ここでの C は (1) の C とは別の型
                    override def apply[C](f: B => F[C]) = {
                        // この結果の型は (1) の C で
                        // (2) の C とは型が異なり type mismatch となる
                        k(a)
                    }
                }
            }.apply(k)
        }
    }
}

また、(2) で override def apply(f: B => F[C]) のように型パラメータを省略する事もできません。 *2


試行錯誤してみましたが、この問題に対する良い解決策を思いつかなかったので、とりあえず下記 (1) のように asInstanceOf でキャストして回避しました。

CodensityFunc.scala (callCC の実装)
・・・
object CodensityFunc {
    def callCC[F[+_], A, B](f: (A => Codensity[F, B]) => Codensity[F, A]): Codensity[F, A] = {
        new Codensity[F, A] { 
            def apply[C](k: A => F[C]) = {
                f { a: A =>
                    new Codensity[F, B] {
                        override def apply[D](f: B => F[D]) = {
                            // (1)
                            k(a).asInstanceOf[F[D]]
                        }
                    }
                }.apply(k)
            }
        }
    }
}

なお、以前の Codensity トレイトには sealed が付いていたので、このように apply メソッドを自前で実装する事はできなかったのですが、最近のバージョンでは sealed が外れて実装できるようになっています。

callCC の処理1

それでは、callCC を使った単純なサンプルを実装してみます。

CallCCSample.scala
・・・
object CallCCSample extends App {

    def sample[F[+_]](n: Int): Codensity[F, Int] = CodensityFunc.callCC { cc1: (Int => Codensity[F, Int]) =>
        if (n % 2 == 1) {
            cc1(n) // (1)
        }
        else {
            Codensity.pureCodensity(n * 10) // (2)
        }
    }

    sample(1).apply { Option(_) } foreach(println)
    sample(2).apply { Option(_) } foreach(println)
    sample(3).apply { Option(_) } foreach(println)
    sample(4).apply { Option(_) } foreach(println)
}

sample の処理内容は以下のようになっており、apply には値を Option に格納する関数を渡しています。

  • 引数 n が奇数なら n の値を適用する Codensity を返す (1)
  • 引数 n が偶数なら n * 10 の値を適用する Codensity を返す (2)

実行結果は以下の通りです。
奇数ならそのままの値、偶数なら 10 倍した値が出力されます。

実行結果
scala> fits.sample.CallCCSample.main(null)
1
20
3
40

callCC の処理2

最後に callCC をネストさせたサンプルです。

CallCCSample2.scala
・・・
object CallCCSample2 extends App {

    def sample[F[+_]](n: Int): Codensity[F, Int] = CodensityFunc.callCC { cc1: (Int => Codensity[F, Int]) =>
        if (n % 2 == 1) {
            cc1(n) // (1)
        }
        else {
            for {
                x <- CodensityFunc.callCC { cc2: (Int => Codensity[F, Int]) =>
                    n match {
                        case x if (x < 4) => cc2(n * 1000) // (2)
                        case 4 => cc1(n * 100) // (3)
                        case _ => Codensity.pureCodensity[F, Int](n * 10) // (4)
                    }
                }
            } yield (x + 1) // (5)
        }
    }

    sample(1).apply { Option(_) } foreach(println) // (1)
    sample(2).apply { Option(_) } foreach(println) // (2) (5)
    sample(3).apply { Option(_) } foreach(println) // (1)
    sample(4).apply { Option(_) } foreach(println) // (3)
    sample(5).apply { Option(_) } foreach(println) // (1)
    sample(6).apply { Option(_) } foreach(println) // (4) (5)
}

sample の処理内容は以下のようになります。

  • 引数 n が奇数なら n の値を適用する Codensity を返す (1)
  • 引数 n が偶数の場合
    • 4 より小さいと 1000 倍した値に +1 した値を適用する Codensity を返す (2) (5)
    • 4 なら 100 倍した値を適用する Codensity を返す (3)
    • それ以外は 10 倍した値に +1 した値を適用する Codensity を返す (4) (5)

(3) のように 2つ目の callCC 内で cc1 を呼び出すと (5) は実行されず、(2) のように cc2 を呼び出した場合は (5) が適用される事になります。

実行結果
scala> fits.sample.CallCCSample2.main(null)
1
2001
3
400
5
61

*1:"() => println(x)" の部分が Function0[Unit] に該当

*2:method apply overrides nothing エラーとなる