トップ > Monad

Arrow (Kleisli) で List モナド - Haskell, Frege, Scalaz

Haskell Java Frege Scala Scalaz Monad

「Scalaz でリストモナド - Kleisli による関数合成 」等で試してきた List モナドを使ったチェスのナイト移動の処理を Arrow （Kleisli） を使って実装し直してみました。

Arrow は計算のための汎用的なインターフェースで、モナドを扱うための Arrow として Kleisli があります。

ソースは http://github.com/fits/try_samples/tree/master/blog/20140810/

Haskell の場合

Haskell の Arrow は >>> や <<< で合成できるようになっています。

Kleisli はモナドを扱うための Arrow なので、下記では List モナドを返す関数 moveKnight を Kleisli へ包んで合成しています。

Kleisli から包んだ関数を取り出すには runKleisli を使います。

3手版

まずは 3手版です。

以前の List モナド版との違いは in3 と canReachIn3 関数を Arrow で実装し直した点です。

Kleisli を使えば、モナド値が無くてもモナドを返す関数 （通常の値を取ってモナドを返す関数） を簡単に合成できるので in3 はポイントフリースタイルで定義しました。 （このため canReachIn3 関数の引数の順序が 以前のもの と異なっています）

また、通常の関数は Arrow のインスタンスなので、canReachIn3 関数の部分は単純に canReachIn3 end = runKleisli in3 >>> elem end とする事も可能です。

move_knight.hs
import Control.Arrow

type KnightPos = (Int, Int)

moveKnight :: KnightPos -> [KnightPos]
moveKnight (c, r) = filter onBoard
    [
        (c + 2, r - 1), (c + 2, r + 1),
        (c - 2, r - 1), (c - 2, r + 1),
        (c + 1, r - 2), (c + 1, r + 2),
        (c - 1, r - 2), (c - 1, r + 2)
    ]
    where onBoard (c', r') = c' `elem` [1..8] && r' `elem` [1..8]

-- 3手先の移動位置を列挙
in3 :: Kleisli [] KnightPos KnightPos
in3 = Kleisli moveKnight >>> Kleisli moveKnight >>> Kleisli moveKnight

-- 指定位置に3手で到達できるか否かを判定
canReachIn3 :: Arrow a => KnightPos -> a KnightPos Bool
canReachIn3 end = arr (runKleisli in3) >>> arr (elem end)
-- 以下でも可
-- canReachIn3 :: KnightPos -> KnightPos -> Bool
-- canReachIn3 end = runKleisli in3 >>> elem end

main = do
    print $ runKleisli in3 $ (6, 2)

    print $ canReachIn3 (6, 1) $ (6, 2)
    print $ canReachIn3 (7, 3) $ (6, 2)
実行結果
> runghc move_knight.hs

[(8,1),(8,3),・・・
・・・
,(3,4),(3,8)]
True
False

N手版

3手版と同様に inMany と canReachInMany 関数を Arrow で実装し直してみました。

move_knight_many.hs
・・・
-- N手先の移動位置を列挙
inMany :: Int -> Kleisli [] KnightPos KnightPos
inMany x = foldr (>>>) returnA (replicate x (Kleisli moveKnight))

-- 指定位置にN手で到達できるか否かを判定
canReachInMany :: Arrow a => Int -> KnightPos -> a KnightPos Bool
canReachInMany x end = arr (runKleisli (inMany x)) >>> arr (elem end)
-- 以下でも可
-- canReachInMany :: Int -> KnightPos -> KnightPos -> Bool
-- canReachInMany x end = runKleisli (inMany x) >>> elem end

main = do
    print $ runKleisli (inMany 3) $ (6, 2)

    print $ canReachInMany 3 (6, 1) $ (6, 2)
    print $ canReachInMany 3 (7, 3) $ (6, 2)
実行結果
> runghc move_knight_many.hs

[(8,1),(8,3),・・・
・・・
,(3,4),(3,8)]
True
False

Frege の場合

Frege は Haskell とほとんど同じ実装になりますが、下記の点が異なります。

  • >>> の代わりに . で Arrow を合成
  • runKleisli の代わりに run を使用

なお、. は >>> と合成の向きが異なります。

3手版

3手版です。

move_knight.fr
package sample.MoveKnight where

import frege.control.Arrow
import frege.control.arrow.Kleisli

type KnightPos = (Int, Int)

moveKnight :: KnightPos -> [KnightPos]
moveKnight (c, r) = filter onBoard
    [
        (c + 2, r - 1), (c + 2, r + 1),
        (c - 2, r - 1), (c - 2, r + 1),
        (c + 1, r - 2), (c + 1, r + 2),
        (c - 1, r - 2), (c - 1, r + 2)
    ]
    where onBoard (c', r') = c' `elem` [1..8] && r' `elem` [1..8]

-- 3手先の移動位置を列挙
in3 :: Kleisli [] KnightPos KnightPos
in3 = Kleisli moveKnight . Kleisli moveKnight . Kleisli moveKnight

-- 指定位置に3手で到達できるか否かを判定
canReachIn3 :: Arrow a => KnightPos -> a KnightPos Bool
canReachIn3 end = arr (elem end) . arr in3.run
-- 以下でも可
-- canReachIn3 :: KnightPos -> KnightPos -> Bool
-- canReachIn3 end = elem end . in3.run

main args = do
    println $ in3.run $ (6, 2)

    println $ canReachIn3 (6, 1) $ (6, 2)
    println $ canReachIn3 (7, 3) $ (6, 2)
実行結果
> java -jar frege3.21.586-g026e8d7.jar move_knight.fr
・・・
> java -cp .;frege3.21.586-g026e8d7.jar sample.MoveKnight

[(8, 1), (8, 3), ・・・
・・・
 (3, 4), (3, 8)]
true
false

N手版

N手版です。

move_knight_many.fr
package sample.MoveKnightMany where

・・・
-- N手先の移動位置を列挙
inMany :: Int -> Kleisli [] KnightPos KnightPos
inMany x = foldr (.) id (replicate x (Kleisli moveKnight))

-- 指定位置にN手で到達できるか否かを判定
canReachInMany :: Arrow a => Int -> KnightPos -> a KnightPos Bool
canReachInMany x end = arr (elem end) . arr (inMany x).run
-- 以下でも可
-- canReachInMany :: Int -> KnightPos -> KnightPos -> Bool
-- canReachInMany x end = elem end . (inMany x).run

main args = do
    println $ (inMany 3).run $ (6, 2)

    println $ canReachInMany 3 (6, 1) $ (6, 2)
    println $ canReachInMany 3 (7, 3) $ (6, 2)
実行結果
> java -jar frege3.21.586-g026e8d7.jar move_knight_many.fr
・・・
> java -cp .;frege3.21.586-g026e8d7.jar sample.MoveKnightMany

[(8, 1), (8, 3), ・・・
・・・
 (3, 4), (3, 8)]
true
false

Scalaz の場合

最後に Scalaz を使った Scala による実装です。
Haskell と同様に >>> で Arrow を合成できるようになっています。

3手版

3手版です。

MoveKnight.scala
package sample

import scalaz._
import Scalaz._

object MoveKnight extends App {

    type KnightPos = Tuple2[Int, Int]

    val inRange = (p: Int) => 1 to 8 contains p

    val moveKnight = (p: KnightPos) => List(
        (p._1 + 2, p._2 - 1), (p._1 + 2, p._2 + 1),
        (p._1 - 2, p._2 - 1), (p._1 - 2, p._2 + 1),
        (p._1 + 1, p._2 - 2), (p._1 + 1, p._2 + 2),
        (p._1 - 1, p._2 - 2), (p._1 - 1, p._2 + 2)
    ).filter { case (x, y) => inRange(x) && inRange(y) }

    // 3手先の移動位置を列挙
    val in3 = Kleisli(moveKnight) >>> Kleisli(moveKnight) >>> Kleisli(moveKnight)
    // 以下でも可
    // val in3 = Kleisli(moveKnight) >==> moveKnight >==> moveKnight

    // 指定位置に3手で到達できるか否かを判定
    val canReachIn3 = (end: KnightPos) => in3.run >>> { xs => xs.contains(end) }

    in3 (6, 2) |> println

    (6, 2) |> canReachIn3 (6, 1) |> println
    (6, 2) |> canReachIn3 (7, 3) |> println
}
実行結果
> gradle run

MoveKnight
:compileJava UP-TO-DATE
:compileScala UP-TO-DATE
:processResources UP-TO-DATE
:classes UP-TO-DATE
:run
List((8,1), (8,3), ・・・
・・・
・・・, (3,4), (3,8))
true
false

N手版

N手版です。

MoveKnightMany.scala
package sample

import scalaz._
import Scalaz._

object MoveKnightMany extends App {
    ・・・
    // N手先の移動位置を列挙
    val inMany = (x: Int) => List.fill(x) { Kleisli(moveKnight) }.reduce { (a, b) => a >>> b }
    // 以下でも可
    // val inMany = (x: Int) => List.fill(x) { Kleisli(moveKnight) }.reduce { (a, b) => a >=> b }

    // 指定位置にN手で到達できるか否かを判定
    val canReachInMany = (x: Int) => (end: KnightPos) => inMany(x).run >>> { xs => xs.contains(end) }

    (6, 2) |> inMany(3) |> println

    (6, 2) |> canReachInMany(3)(6, 1) |> println
    (6, 2) |> canReachInMany(3)(7, 3) |> println
}
実行結果
> gradle run -Pmany

MoveKnightMany
:compileJava UP-TO-DATE
:compileScala UP-TO-DATE
:processResources UP-TO-DATE
:classes UP-TO-DATE
:run
List((8,1), (8,3), ・・・
・・・
・・・, (3,4), (3,8))
true
false

なお、ビルドと実行には下記のような Gradle ビルド定義ファイルを使用しました。

build.gradle
apply plugin: 'application'
apply plugin: 'scala'

repositories {
    mavenCentral()
}

dependencies {
    compile 'org.scala-lang:scala-library:2.11.2'
    compile 'org.scalaz:scalaz-core_2.11:7.1.0'
}

if (!hasProperty('many')) {
    println 'MoveKnight'
    mainClassName = 'sample.MoveKnight'
}
else {
    println 'MoveKnightMany'
    mainClassName = 'sample.MoveKnightMany'
}

Roy で List モナド

JavaScript Node.js Monad

前回に続き、今回も Roy を試してみます。

Roy ではモナドを使った do 記法を使えるようなので、JavaScript で List モナド - Monadic 等で試したチェスのナイト移動の List モナド処理を同じように実装してみました。

ソースは http://github.com/fits/try_samples/tree/master/blog/20140724/

モナドの定義

Roy では下記のように return と bind を実装してモナドを定義します。

let <モナド> {
    return: \x -> ・・・
    bind: \x f -> ・・・
}

これで Monadic と同じように do <モナド> ・・・ のような記法が使えます。

それでは、List モナドを定義して do を簡単に使ってみました。
Underscore.js に Haskell の concat と同等の処理が無さそうだったので concat を自前で定義しています。

sample.roy
let _ = require 'underscore'

let concat xs = _.reduce xs (\a b -> a.concat b) []
// リストモナド
let listMonad = {
    return: \x -> [x]
    bind: \xs f -> concat (_.map xs (\y -> f y))
}
// do 記法
let res = do listMonad
    x <- [1, 3, 5]
    y <- ['a', 'b']
    return (x * 2, y)

console.log res

do でタプル (要素1, 要素2, ・・・) を return していますが、下記のようにタプルは配列として扱われるようです。

実行結果
> roy -r sample.roy

[ [ 2, 'a' ],
  [ 2, 'b' ],
  [ 6, 'a' ],
  [ 6, 'b' ],
  [ 10, 'a' ],
  [ 10, 'b' ] ]

3手版

それでは本題に入ります。

まずは、List モナドを使って下記の処理を実装してみます。

  • 3手先のナイトの移動位置を全て列挙する処理
  • 3手後に指定の終了位置に到達するか否かを判定する処理

Haskell と同様に type で型シノニムを定義できるので、ナイトの位置情報を表す KnightPos という型シノニムを定義しました。

関数の引数では (<引数>: <型>) のように型を指定する事も可能です。

また、複数の引数は Haskell と同様に半角スペースで区切る事になります。

move_knight.roy （3手移動版）
let _ = require 'underscore'

let concat xs = _.reduce xs (\a b -> a.concat b) []

let listMonad = {
    return: \x -> [x]
    bind: \xs f -> concat (_.map xs (\y -> f y))
}
// 型シノニムの定義
type KnightPos = {c: Number, r: Number}

let inRange (n: Number) = _.contains (_.range 1 9) n

// ナイトの次の移動先を列挙
let moveKnight (p: KnightPos) = _.filter [
    {c: p.c + 2, r: p.r - 1}, {c: p.c + 2, r: p.r + 1},
    {c: p.c - 2, r: p.r - 1}, {c: p.c - 2, r: p.r + 1},
    {c: p.c + 1, r: p.r - 2}, {c: p.c + 1, r: p.r + 2},
    {c: p.c - 1, r: p.r - 2}, {c: p.c - 1, r: p.r + 2}
] ( \t -> (inRange t.c) && (inRange t.r) )

// 3手先の移動位置を列挙（重複あり）
let in3 (start: KnightPos) = do listMonad
    fst <- moveKnight start
    snd <- moveKnight fst
    moveKnight snd

console.log (in3 {c: 6, r: 2})

// 指定位置に3手で到達できるか否かを判定
let canReachIn3 (start: KnightPos) (end: KnightPos) = _.any (in3 start) (\p -> p.c == end.c && p.r == end.r)

console.log (canReachIn3 {c: 6, r: 2} {c: 6, r: 1})
console.log (canReachIn3 {c: 6, r: 2} {c: 7, r: 3})
実行結果
> roy -r move_knight.roy

[ { c: 8, r: 1 },
  { c: 8, r: 3 },
  { c: 4, r: 1 },
  { c: 4, r: 3 },
  ・・・
  { c: 3, r: 4 },
  { c: 3, r: 8 } ]
true
false

N手版

先程は 3手で固定していましたが、任意の手数を指定できるようにしてみます。

こちらは do を使わず、直接 listMonad.bind を使って n 回のナイト移動処理を連結するようにしました。

move_knight_many.roy （N手移動版）
・・・
// n手先の移動位置を列挙（重複あり）
let inMany (n: Number) (start: KnightPos) = _.reduce (_.range n) (\a b -> listMonad.bind a moveKnight) [start]

console.log (inMany 3 {c: 6, r: 2})

// 指定位置に n手で到達できるか否かを判定
let canReachInMany (n: Number) (start: KnightPos) (end: KnightPos) = _.any (inMany 3 start) (\p -> p.c == end.c && p.r == end.r)

console.log (canReachInMany 3 {c: 6, r: 2} {c: 6, r: 1})
console.log (canReachInMany 3 {c: 6, r: 2} {c: 7, r: 3})
実行結果
> roy -r move_knight_many.roy

[ { c: 8, r: 1 },
  { c: 8, r: 3 },
  { c: 4, r: 1 },
  { c: 4, r: 3 },
  ・・・
  { c: 3, r: 4 },
  { c: 3, r: 8 } ]
true
false

Functional Java で Iteratee - take の実装

Java Groovy Monad

Functional Java の Iteratee を使って、以前試した Play2 の Iteratee （http://fits.hatenablog.com/entry/20130212/1360681996, http://fits.hatenablog.com/entry/20130216/1361027691） や RxJava （http://fits.hatenablog.com/entry/20130310/1362876374） と同等の処理を実装してみました。

ソースは http://github.com/fits/try_samples/tree/master/blog/20130518/

Functional Java の Iteratee に関して

Functional Java の Iteratee には、Iteratee への入力となる Iteratee.Input と Iteratee の処理を実装する Iteratee.IterV が用意されています。

Iteratee.Input は下記の 3タイプがあり、それぞれが匿名クラスとして実装されているのでファクトリメソッドを通して作成するようになっています。

apply メソッドに Empty・EOF・El の 3タイプそれぞれの処理内容を実装した P1 オブジェクトを渡す事で該当するタイプの処理を適用した結果を取得します。 *1

Iteratee.Input のタイプ
タイプ 内容 ファクトリメソッド
Empty 入力データが空 Input.empty()
EOF 終端に到達 Input.eof()
El 入力データ有り Input.el()

Iteratee.IterV の 2つのタイプ Cont・Done も Input と同様に匿名クラスで実装されており、ファクトリメソッドを通して作成します。

run メソッドで処理を実施し処理結果を取得します。

Iteratee.IterV のタイプ
タイプ 内容 ファクトリメソッド
Cont Iteratee の処理が継続中の状態。新しい Input を受け取って新しい IterV（Cont か Done）を返します IterV.cont()
Done Iteratee の処理が完了した状態。処理結果を格納しています IterV.done()

動作内容としては下記のような処理が入れ子になるような感じです。

  • Enumerator が Cont に Input を渡して、Done が返ってくれば処理終了、Cont なら Enumerator が次の Input を渡して・・・

IterV と Input の処理の流れは下記のようなイメージになると思います。

El で処理が完了となるか EOF が来れば Done で終了し、El で継続中となるか Empty が来れば Cont で処理が続く事になります。

ちなみに、ファイルの内容を読み込んで IterV に Input を渡す Enumerator 的な処理は IO クラスにメソッドが用意されており（enumFileLines 等）、drop や head 等の処理は IterV に用意されています。（ただし、take は用意されていないようです）

take 処理

Play2 の Enumeratee.take() や RxJava の Observable.take() のような take 処理は Functional Java 3.1 では用意されていないようなので、今回は自前で実装してみる事にしました。

take の処理内容は概ね下記のようになります。

  • take の引数に与えられた数量の El を処理するまで Cont を返す
  • 途中で EOF となるか、take が完了した際に Done （take した入力データを処理結果として格納） を返す

Groovy で実装

それでは Groovy で take を実装してみたいと思います。

まずは Cont を返さないと何も始まらないので take は Cont を返すようにします。

Cont には Input -> IterV という処理（与えられた Input の内容に応じて Cont / Done を返す）を実装した F オブジェクトを設定する事になります。

今回は Input を受け取って Cont / Done を返す処理をクロージャで実装し、"残りの take 数" と "take 結果のリスト" （今回は java.util.List を使いました）を引数として与えるようにしています。

ここで Empty・El・EOF それぞれの処理は以下のように実装しています。

Inputのタイプ takeの状態 戻り値となるIterVのタイプ 備考
Empty - Cont 残りの take 数そのままで step を実施するように設定
EOF - Done take 結果のリストを設定
El 完了（残りの take 数が 0 以下） Done take 結果のリストと未処理の入力データを設定
El 継続中 Cont 残りの take 数を -1、take 結果のリストに入力値を追加して step を実施するように設定

また、Input.apply の引数に渡す型は下記のようになっています。（下記の E は入力データの型です）

Inputのタイプ applyへの引数の型
Empty P1< IterV< E, List > >
EOF P1< IterV< E, List > >
El P1< F< E, IterV > > >

なお、クロージャ内で再帰的にクロージャを使っている関係上、def step を先に宣言して、後から実施を設定するようにしています。 *2

最後に take の動作確認として、drop と take を組み合わせた Iteratee にファイルの内容を処理させてみました。

今回はファイルを行単位で処理させるため IO.enumFileLines() を使っています。IO.enumFileLines() は IO オブジェクトを返すので、まずは IO オブジェクトの run メソッドで IterV オブジェクトを取得して、次に IterV オブジェクトの run メソッドで処理結果を取得します。

take_sample.groovy
@Grab('org.functionaljava:functionaljava:3.1')
import fj.F
import fj.P1
import fj.data.IO
import fj.data.Option
import static fj.data.Iteratee.*

import java.nio.charset.StandardCharsets

def take(int n) {
    def step
    step = { int count, List acc, Input s ->
        // Empty 時の処理内容（Input が空の場合）
        def empty = { IterV.cont( { step(count, acc, it) } as F) } as P1
        // EOF 時の処理内容（終端に達した場合）
        def eof = { IterV.done(acc, s) } as P1

        // El 時の処理内容（Input に値が設定されている場合）
        def el = {
            return { value ->
                if (count <= 0) {
                    // take 結果リスト acc と未処理の入力 s を設定して Done
                    IterV.done(acc, s)
                }
                else {
                    // take した値を take 結果リスト acc に追加して Cont
                    IterV.cont({ step(count - 1, acc << value, it) } as F)
                }
            } as F
        } as P1

        s.apply(empty, el, eof)
    }

    IterV.cont({ step(n, [], it) } as F)
}

// (1) 1つ目を捨てて 2つ目から 3つ取り出す Iteratee 処理の組み立て
def iter = IterV.drop(1).bind({ take(3) } as F)

// (2) ファイルを行単位で (1) の処理を実施する IO<IterV> の取得
def ioIter = IO.enumFileLines(new File(args[0]), Option.some(StandardCharsets.UTF_8), iter)

// (3) 処理の実行と結果の出力
ioIter.run().run().each {
    println "#${it}"
}

実行結果は下記のようになります。
処理内容としては 1行目を無視して 2行目から 3行を取り出し先頭に # をつけて出力しています。

実行結果
> groovy take_sample.groovy sample.txt
#サンプル2
#サンプル3
#サンプル4

使用したファイルの内容は以下の通りです。

sample.txt
サンプル1
サンプル2
サンプル3
サンプル4
サンプル5
サンプル6
サンプル7
サンプル8

Java で実装

同様の処理を Java SE 7 で実装してみました。（ただし、take 結果を溜めるリストの用途に java.util.List を使わず fj.data.List を使っています）

クロージャが使えない分、Groovy と比べると型まわりが相当ややこしくなっているので実用的とは言い難いかもしれません。

TakeSample.java
import fj.F;
import fj.F3;
import fj.Function;
import fj.P;
import fj.P1;
import fj.Unit;
import fj.data.IO;
import fj.data.Option;
import fj.data.List;
import static fj.data.Iteratee.*;

import java.io.File;
import java.nio.charset.StandardCharsets;

class TakeSample {
    public static void main(String... args) throws Exception {

        // (1) 1つ目を捨てて 2つ目から 3つ取り出す Iteratee 処理の組み立て
        IterV<String, List<String>> iter = IterV.<String>drop(1).bind(new F<Unit, IterV<String, List<String>>>() {
            @Override
            public IterV<String, List<String>> f(final Unit xe) {
                return take(3);
            }
        });

        // (2) ファイルを行単位で (1) の処理を実施する IO の取得
        IO<IterV<String, List<String>>> ioIter = IO.enumFileLines(new File(args[0]), Option.some(StandardCharsets.UTF_8), iter);

        // (3) 処理の実行と結果の出力
        ioIter.run().run().foreach(new F<String, Unit>() {
            @Override
            public Unit f(final String line) {
                System.out.println("#" + line);
                return Unit.unit();
            }
        });
    }

    public static final <E> IterV<E, List<E>> take(final int n) {
        final F3<Integer, List<E>, Input<E>, IterV<E, List<E>>> step = new F3<Integer, List<E>, Input<E>, IterV<E, List<E>>>() {

            final F3<Integer, List<E>, Input<E>, IterV<E, List<E>>> step = this;
            @Override
            public IterV<E, List<E>> f(final Integer count, final List<E> acc, final Input<E> s) {
                // Empty 時の処理内容（Input が空の場合）
                final P1<IterV<E, List<E>>> empty = new P1<IterV<E, List<E>>>() {
                    @Override
                    public IterV<E, List<E>> _1() {
                        return IterV.cont(new F<Input<E>, IterV<E, List<E>>>() {
                            @Override
                            public IterV<E, List<E>> f(Input<E> e) {
                                return step.f(count, acc, e);
                            }
                        });
                    }
                };

                // EOF 時の処理内容（終端に達した場合）
                final P1<IterV<E, List<E>>> eof = new P1<IterV<E, List<E>>>() {
                    @Override
                    public IterV<E, List<E>> _1() {
                        return IterV.done(acc, s);
                    }
                };

                // El 時の処理内容（Input に値が設定されている場合）
                final P1<F<E, IterV<E, List<E>>>> el = new P1<F<E, IterV<E, List<E>>>>() {
                    @Override
                    public F<E, IterV<E, List<E>>> _1() {
                        return new F<E, IterV<E, List<E>>>() {
                            @Override
                            public IterV<E, List<E>> f(final E value) {
                                if (count <= 0) {
                                    // take 結果リスト acc と未処理の入力 s を設定して Done
                                    return IterV.done(acc, s);
                                }
                                else {
                                    // take した値を take 結果リスト acc に追加して Cont
                                    return IterV.cont(new F<Input<E>, IterV<E, List<E>>>() {
                                        @Override
                                        public IterV<E, List<E>> f(Input<E> e) {
                                            return step.f(count - 1, acc.snoc(value), e);
                                        }
                                    });
                                }
                            }
                        };
                    }
                };

                return s.apply(empty, el, eof);
            }
        };

        return IterV.cont(new F<Input<E>, IterV<E, List<E>>>() {
            @Override
            public IterV<E, List<E>> f(Input<E> e) {
                return step.f(n, List.<E>nil(), e);
            }
        });
    }
}

*1:Play2 の Iteratee 等とは違ってパターンマッチを使わなくても良いようになっています

*2:def step = {・・・ step(・・・) ・・・} のようにするとエラーが発生します

Play2 の Iteratee を使った行単位のファイル処理2 - Enumerator.generateM, Enumerator.fromCallback1

Scala Monad Play

前回 id:fits:20130212 は Enumeratee.grouped() を使って行単位のファイル処理を実装しましたが、今回は Enumerator.generateM() と Enumerator.fromCallback1() をそれぞれ使って同様の処理を実装してみました。

sbt のビルド定義ファイルなどは前回と同様のものを使っています。

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

Enumerator.generateM による行分割

Enumerator.generateM は、引数として渡した処理 *1 を繰り返し実行する Enumerator を作成します。

繰り返しは None を返す事で終了するため、下記 (a) ではファイルを 1行読んで Some(<1行分の文字列>) を返し、ファイルの終端に達した場合に None を返すようにしています。
こうする事でファイルの内容を 1行ずつ返す Enumerator を実現できます。

(b) の処理でファイルの内容を全て消費してしまいますが、(c) で BufferedReader をリセットする事で *2、(d) では (a) で作成した enumerator をそのまま使って 1行目から処理できるようになっています。

さらに (e) でも enumerator を利用していますが、enumerator はファイルの終端に達していないため (d) からの続きの行を処理する事になります。

ファイルのクローズ処理 (f) は Iteratee の処理とは別に一番最後で実施するようにしました。

EnumeratorLineSample.scala （Enumerator.generateM を使ったサンプル）
package fits.sample

import play.api.libs.iteratee._

import scala.concurrent.{Await, Future}
import scala.concurrent.duration.Duration

import java.io.{BufferedReader, FileInputStream, InputStreamReader}
import java.nio.charset.StandardCharsets._

object EnumeratorLineSample extends App {
    import scala.concurrent.ExecutionContext.Implicits.global

    val reader = new BufferedReader(new InputStreamReader(new FileInputStream(args(0)), UTF_8))
    reader.mark(512)

    // (a) ファイルの内容を 1行ずつ返す Enumerator
    val enumerator = Enumerator.generateM( Future {
        reader.readLine match {
            case line: String => Some(line)
            case _            => None // ファイルの終端に達した場合
        }
    })

    // (b) 行毎に先頭へ # を付けて出力する処理の組み立て
    val future = enumerator |>>> Iteratee.foreach { s => 
        println(s"#${s}")
    }

    Await.ready(future, Duration.Inf)

    println("----------")
    // (c) ファイルの内容を先頭から返すようにリセット
    reader.reset

    // (d) 1行目を捨てて 2行目から 2行取り出し各行の先頭へ # を付けて出力する処理の組み立て
    val future2 = enumerator &> Enumeratee.drop(1) &> Enumeratee.take(2) |>>> Iteratee.foreach { s => 
        println(s"#${s}")
    }

    Await.ready(future2, Duration.Inf)

    println("----------")

    // (e) 1行出力。(d) からの続きとなるのでファイルの 4行目が出力される
    val future3 = enumerator &> Enumeratee.take(1) |>>> Iteratee.foreach { s => 
        println(s"#${s}")
    }

    Await.ready(future3, Duration.Inf)

    // (f) クローズ処理
    reader.close
}

実行結果は以下の通りです。

実行結果
> sbt "run sample.txt"
・・・
[info] Running fits.sample.EnumeratorLineSample sample.txt
#Play2のIterateeを使ったファイル処理の
#サンプル
#
#1行毎に処理するサンプルを
#実装してみました。
----------
#サンプル
#
----------
#1行毎に処理するサンプルを

Enumerator.fromCallback1 による行分割

次は、Enumerator.fromCallback1 *3 を使って同様の処理を実装してみます。

generateM に渡していた処理を fromCallback1 の第一引数の処理結果として返すようにすれば同じ処理内容となります。

ただし下記では、fromCallback1 の第二引数（onComplete）に BufferedReader を close する処理 (b) を渡し、Iteratee の処理が完了する度に入力ストリーム （今回はファイル） をクローズするようにしています。

(e) では (d) で使った enumerator2 を使っていますが、(d) でファイルはクローズされており Enumerator は何も生成しないため何も出力されません。

EnumeratorLineSample2.scala （Enumerator.fromCallback1 を使ったサンプル）
・・・
object EnumeratorLineSample2 extends App {
    import scala.concurrent.ExecutionContext.Implicits.global

    // (a) 1行ずつファイルの内容を返す Enumerator を作成
    def fromStreamLine(input: BufferedReader) = {
        Enumerator.fromCallback1(_ => Future {
            input.readLine match {
                case line: String => Some(line)
                case _            => None // ファイルの終端に達した場合
            }
        }, {
            println("*** close")
            // (b) ファイルのクローズ処理
            input.close
        })
    }

    val enumerator = fromStreamLine(new BufferedReader(new InputStreamReader(new FileInputStream(args(0)), UTF_8)))

    // (c) 行毎に先頭へ # を付けて出力する処理の組み立て
    val future = enumerator |>>> Iteratee.foreach { s => 
        println(s"#${s}")
    }

    Await.ready(future, Duration.Inf)

    println("----------")

    val enumerator2 = fromStreamLine(new BufferedReader(new InputStreamReader(new FileInputStream(args(0)), UTF_8)))

    // (d) 1行目を捨てて 2行目から 2行取り出し各行の先頭へ # を付けて出力する処理の組み立て
    val future2 = enumerator2 &> Enumeratee.drop(1) &> Enumeratee.take(2) |>>> Iteratee.foreach { s => 
        println(s"#${s}")
    }

    Await.ready(future2, Duration.Inf)

    println("----------")

    // (e) ファイルはクローズ済みのため何も出力されない
    val future3 = enumerator2 &> Enumeratee.take(1) |>>> Iteratee.foreach { s => 
        println(s"#${s}")
    }

    Await.ready(future3, Duration.Inf)
}

実行結果は以下の通りです。
Iteratee の処理を行う度に "*** close" が出力されている事を確認できます。

実行結果
・・・
[info] Running fits.sample.EnumeratorLineSample2 sample.txt
*** close
#Play2のIterateeを使ったファイル処理の
#サンプル
#
#1行毎に処理するサンプルを
#実装してみました。
----------
*** close
#サンプル
#
----------

*1:Future を返す処理

*2:BufferedReader の mark と reset で実現

*3:Enumerator.fromCallback もあるが、こちらは deprecated となっている

Play2 の Iteratee を使った行単位のファイル処理1 - Enumeratee.grouped() の利用

Scala Monad Play

id:fits:20130116 で使った Play2 の Iteratee を単体利用して行単位のファイル処理を実装してみました。

  • play-iteratees 2.1.0

Iteratee は Enumerator や Enumeratee と組み合わせて使用し、それぞれ以下のような役割を担います。

  • Enumerator : データを生産
  • Enumeratee : Enumerator から受け取ったデータを Iteratee へ渡す
  • Iteratee : データを消費

ちなみに、ファイルの内容を "改行" で分割するような仕組みは今のところ Play2 の API に用意されていないようなので、
1行分のデータを取り出す Enumeratee や Enumerator を自前で用意する事になります。

そこで今回は Enumeratee.grouped() を使って行毎にデータをグルーピングする Enumeratee を作成してみました。
次回は Enumerator.generateM() を使って同様の処理を実装してみるつもりです。


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

はじめに

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

build.sbt
scalaVersion := "2.10.0"

resolvers += "Typesafe Repository" at "http://repo.typesafe.com/typesafe/releases/"

libraryDependencies += "play" %% "play-iteratees" % "2.1.0"

mainClass in (Compile, run) := Some("fits.sample.EnumerateeLineSample")

なお、今回は下記ファイル（文字コードは UTF-8）を使って動作確認する事にします。

sample.txt
Play2のIterateeを使ったファイル処理の
サンプル

1行毎に処理するサンプルを
実装してみました。

Enumeratee.grouped による行分割

Enumeratee.grouped を使った行単位の処理は以下のようになりました。

  • (a) Enumerator.fromFile() で chunkSize のサイズ分だけ読み込んだファイルの内容を Array[Byte] として生成する Enumerator 作成
  • (e) Enumerator・Enumeratee・Iteratee を結合
    • Enumeratee.mapConcat で Enumerator と Enumeratee.grouped を結び付ける Enumeratee 作成
    • Enumeratee.grouped で行毎にグルーピングする Enumeratee 作成
    • Iteratee.foreach で各行の先頭に # を付けて出力する Iteratee 作成

さらに、Enumeratee.grouped には以下のようにして組み立てた takeLine *1 を渡しています。

  • (c) takeWhile で改行が来るまで入力を溜め、Iteratee.getChunks で溜めた分の入力 List[Byte] を line へ設定
  • (d) 改行文字を take(1) で取得し Iteratee.ignore で捨てる
  • new String() で line （改行までの部分）を文字列化

なお、Iteratee はモナドなので、takeLine は for 式を使って Iteratee を組み立てています。

EnumerateeLineSample.scala
package fits.sample

import play.api.libs.iteratee._

import scala.concurrent.Await
import scala.concurrent.duration.Duration

import java.io.File
import java.nio.charset.StandardCharsets._

object EnumerateeLineSample extends App {
    import scala.concurrent.ExecutionContext.Implicits.global

    // (a) ファイルの内容を取得する Enumerator
    val enumerator = Enumerator.fromFile(new File(args(0)))

    // (b) 1行分の String を生成する Iteratee
    val takeLine = for {
        line <- Enumeratee.takeWhile[Byte](_ != '\n'.toByte) &>> Iteratee.getChunks // (c) 改行文字までの入力を line へ設定
        _    <- Enumeratee.take(1) &>> Iteratee.ignore[Byte] // (d) 改行文字を捨てる
    } yield new String(line.toArray, UTF_8)

    // (e) 行毎に先頭へ # を付けて出力する処理の組み立て
    val future = enumerator &> Enumeratee.mapConcat( _.toSeq ) &> Enumeratee.grouped(takeLine) |>>> Iteratee.foreach { s => 
        println(s"#${s}")
    }

    // (f) future の処理完了待ち
    Await.ready(future, Duration.Inf)
}

それでは sbt run で実行してみます。
"run <引数> ・・・" のように run と引数をダブルクォーテーションで囲めば、sbt run で実行時引数を指定する事が可能です。

実行結果
> sbt "run sample.txt"
・・・
[info] Running fits.sample.EnumerateeLineSample sample.txt
#Play2のIterateeを使ったファイル処理の
#サンプル
#
#1行毎に処理するサンプルを
#実装してみました。
#

実はこの sbt run は処理が完了してもプロセスが終了しないので Ctrl + C する必要があります。

プロセスを終了するには play.api.libs.iteratee.internal.defaultExecutionContext 等で生成されている ExecutorService とかを shutdown する必要があると思うのですが、今回は上手く終了する方法を見つけられませんでした。

とりあえず、以下のようにスレッドを interrupt しまくれば強引にプロセスを終了させる事は可能です。

・・・
object EnumerateeLineSample extends App {
    ・・・
    // 強引にプロセスを終了する
    import scala.collection.convert.WrapAsScala._
    Thread.getAllStackTraces().keySet().foreach(_.interrupt)
}


最後に、Enumeratee.grouped(takeLine) と Iteratee.foreach の間に Enumeratee.drop(1) と Enumeratee.take(2) を追加すれば、2行目と 3行目の先頭へ # を付けて出力するような処理に変わります。

EnumerateeLineSample2.scala
・・・
object EnumerateeLineSample2 extends App {
    ・・・
    // 1行目を捨てて 2行目から 2行取り出し各行の先頭へ # を付けて出力する処理の組み立て
    val future = enumerator &> Enumeratee.mapConcat( _.toSeq ) &> Enumeratee.grouped(takeLine) &> 
          Enumeratee.drop(1) &> Enumeratee.take(2) |>>> Iteratee.foreach { s => 

        println(s"#${s}")
    }

    Await.ready(future, Duration.Inf)
}
実行結果
・・・
[info] Running fits.sample.EnumerateeLineSample2 sample.txt
#サンプル
#

*1:型は Iteratee[Byte, String]

JavaScript で List モナド - Monadic

JavaScript Node.js CoffeeScript Monad

Monadic は JavaScript 用のモナドライブラリです。

今回はこの Monadic を使って、以前 （id:fits:20120912, id:fits:20120930） に Scalaz や Functional Java で実装したナイト移動の List モナド処理 *1 を JavaScirpt で実装してみました。

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

Monadic のインストール

npm install monadic でインストールするか、以下のように package.json の dependencies に monadic の設定を追加して npm install しておきます。

package.json
{
  "name": "monadic-list-sample",
  "version": "0.0.0",
  "dependencies": {
    "monadic": "*"
  }
}
実行例
> npm install

3手版

3手先のナイトの移動位置を全て列挙する処理と3手後に指定の終了位置に到達するか否かを判定する処理を実装します。

Monadic でバインド処理 *2 を行うには mbind を使います。List モナドは require('monadic').list() で取得できます。

3手版 move_knight.js
var monadic = require('monadic');
var listM = monadic.list();

// ナイトの次の移動先を列挙
var moveKnight = function(p) {
    return [
        {c: p.c + 2, r: p.r - 1}, {c: p.c + 2, r: p.r + 1},
        {c: p.c - 2, r: p.r - 1}, {c: p.c - 2, r: p.r + 1},
        {c: p.c + 1, r: p.r - 2}, {c: p.c + 1, r: p.r + 2},
        {c: p.c - 1, r: p.r - 2}, {c: p.c - 1, r: p.r + 2}
    ].filter(function(t) {
        return (1 <= t.c && t.c <= 8 && 1 <= t.r && t.r <= 8);
    });
};

// 3手先の移動位置を列挙（重複あり）
var in3 = function(start) {
    return listM.mbind(
        listM.mbind(
            // 下記の listM.mbind(・・・) は moveKnight(start) でも可
            listM.mbind(
                [start], 
                moveKnight
            ),
            moveKnight
        ),
        moveKnight
    );
};

console.log(in3({c: 6, r: 2}));

// 指定位置に3手で到達できるか否かを判定
var canReachIn3 = function(start, end) {
    return in3(start).some(function(p) {
        return (p.c == end.c && p.r == end.r);
    });
};

console.log(canReachIn3({c: 6, r: 2}, {c: 6, r: 1}));
console.log(canReachIn3({c: 6, r: 2}, {c: 7, r: 3}));

実行結果は以下の通り。

3手版の実行結果
> node move_knight.js
[ { c: 8, r: 1 },
  { c: 8, r: 3 },
  { c: 4, r: 1 },
  { c: 4, r: 3 },
  ・・・
  { c: 3, r: 4 },
  { c: 3, r: 8 } ]
true
false

do 記法 3手版

上記サンプルの in3 の処理を Monadic の do 記法を使って実装し直したのが下記です。
Monadic の do 記法は以下のように実装します。（Haskell の do に近い記述が可能になっています）

  • do の後にモナドオブジェクト（下記の listM） *3 を指定する
  • 変数 <- 関数(・・・) で関数の結果を変数に束縛
  • return でモナド処理の結果を返す
do 記法 3手版 move_knight.mjs
var monadic = require('monadic');
var listM = monadic.list();

var moveKnight = function(p) {
    ・・・
};

var in3 = function(start) {
    // do 記法で実装
    return do listM {
        first  <- moveKnight(start)
        second <- moveKnight(first)
        third  <- moveKnight(second)

        return third
    };
};

console.log(in3({c: 6, r: 2}));

var canReachIn3 = function(start, end) {
    ・・・
};

console.log(canReachIn3({c: 6, r: 2}, {c: 6, r: 1}));
console.log(canReachIn3({c: 6, r: 2}, {c: 7, r: 3}));

do 記法を使った .mjs ファイルのオーソドックスな実行方法が分からなかったので、-e オプションを使って実行してみました。

require('monadic').transform() で 'move_knight.mjs' を純粋な JavaScript コードへ変換し eval 実行しています。

do 記法 3手版の実行結果
> node -e "eval(require('monadic').transform(process.argv[1]))" move_knight.mjs
[ { c: 8, r: 1 },
  { c: 8, r: 3 },
  { c: 4, r: 1 },
  { c: 4, r: 3 },
  ・・・
  { c: 3, r: 4 },
  { c: 3, r: 8 } ]
true
false

transform による変換結果は以下のようになります。

require('monadic').transform('move_knight.mjs') の変換結果（do の箇所）
・・・
var in3 = function (start) {
    return listM.mbind(moveKnight(start), function (first) {
        return listM.mbind(moveKnight(first), function (second) {
            return listM.mbind(moveKnight(second), function (third) {
                return function () {
                    return listM.mreturn(third);
                }.bind(this)();
            }.bind(this));
        }.bind(this));
    }.bind(this));
};
・・・

N手版

N手版は、moveKnight を使ったバインド処理 （listM.mbind） を入れ子に N個連結するため reduceRight を使いました。

N手版 move_knight_many.js
var monadic = require('monadic');
var listM = monadic.list();

var moveKnight = function(p) {
    ・・・
};

// N手 (num) 先の移動位置を列挙（重複あり）
var inMany = function(num, start) {
    // num 個の moveKnight から成る配列を作成
    var items = new Array(num);
    for (var i = 0; i < num; i++) {
        items.push(moveKnight);
    }
    // num 個の moveKnight を listM.mbind で連結
    return items.reduceRight(
        function(acc, elem) {
            return listM.mbind(acc, elem);
        }, 
        [start]
    );
};

console.log(inMany(3, {c: 6, r: 2}));

// 指定位置に N手(num) で到達できるか否かを判定
var canReachInMany = function(num, start, end) {
    return inMany(num, start).some(function(p) {
        return (p.c == end.c && p.r == end.r);
    });
};

console.log(canReachInMany(3, {c: 6, r: 2}, {c: 6, r: 1}));
console.log(canReachInMany(3, {c: 6, r: 2}, {c: 7, r: 3}));

実行結果は以下の通り。

N手版の実行結果
> node move_knight_many.js
[ { c: 8, r: 1 },
  { c: 8, r: 3 },
  { c: 4, r: 1 },
  { c: 4, r: 3 },
  ・・・
  { c: 3, r: 4 },
  { c: 3, r: 8 } ]
true
false

CoffeeScript 版

最後に、3手版とN手版のサンプルを CoffeeScript で実装し直してみました。

  • CoffeeScript 1.4.0

Monadic の do 記法に関しては、TameJS の時 （id:fits:20120415） と同様に Embedded JavaScript を使えばいけるかもしれませんが今回は調査していません。

CoffeeScript 3手版 move_knight.coffee
monadic = require 'monadic'
listM = monadic.list()

moveKnight = (p) ->
    [
        {c: p.c + 2, r: p.r - 1}, {c: p.c + 2, r: p.r + 1},
        {c: p.c - 2, r: p.r - 1}, {c: p.c - 2, r: p.r + 1},
        {c: p.c + 1, r: p.r - 2}, {c: p.c + 1, r: p.r + 2},
        {c: p.c - 1, r: p.r - 2}, {c: p.c - 1, r: p.r + 2}
    ].filter (t) -> t.c in [1..8] and t.r in [1..8]

in3 = (start) ->
    listM.mbind(
        listM.mbind(
            listM.mbind(
                [start], 
                moveKnight
            ),
            moveKnight
        ),
        moveKnight
    )

console.log in3 {c: 6, r: 2}

canReachIn3 = (start, end) ->
    in3(start).some (p) ->
        p.c == end.c and p.r == end.r

console.log canReachIn3 {c: 6, r: 2}, {c: 6, r: 1}
console.log canReachIn3 {c: 6, r: 2}, {c: 7, r: 3}
CoffeeScript 3手版の実行結果
> coffee move_knight.coffee
[ { c: 8, r: 1 },
  { c: 8, r: 3 },
  { c: 4, r: 1 },
  { c: 4, r: 3 },
  ・・・
  { c: 3, r: 4 },
  { c: 3, r: 8 } ]
true
false

N手版は以下の通りです。
[1..num].map( -> moveKnight ) で num 個の moveKnight から成る配列を作っています。

CoffeeScript N手版 move_knight_many.coffee
monadic = require 'monadic'
listM = monadic.list()

moveKnight = (p) ->
    [
        {c: p.c + 2, r: p.r - 1}, {c: p.c + 2, r: p.r + 1},
        {c: p.c - 2, r: p.r - 1}, {c: p.c - 2, r: p.r + 1},
        {c: p.c + 1, r: p.r - 2}, {c: p.c + 1, r: p.r + 2},
        {c: p.c - 1, r: p.r - 2}, {c: p.c - 1, r: p.r + 2}
    ].filter (t) -> t.c in [1..8] and t.r in [1..8]

inMany = (num, start) ->
    [1..num].map( -> moveKnight ).reduceRight (acc, elem) ->
        listM.mbind(acc, elem)
    , [start]

console.log inMany 3, {c: 6, r: 2}

canReachInMany = (num, start, end) ->
    inMany(num, start).some (p) ->
        p.c == end.c and p.r == end.r

console.log canReachInMany 3, {c: 6, r: 2}, {c: 6, r: 1}
console.log canReachInMany 3, {c: 6, r: 2}, {c: 7, r: 3}
CoffeeScript N手版の実行結果
> coffee move_knight_many.coffee
[ { c: 8, r: 1 },
  { c: 8, r: 3 },
  { c: 4, r: 1 },
  { c: 4, r: 3 },
  ・・・
  { c: 3, r: 4 },
  { c: 3, r: 8 } ]
true
false

*1:チェス盤のナイトの現在位置から次に移動可能な位置を列挙する

*2:Haskell や Scalaz の >>= に該当

*3:モナドオブジェクトには mreturn と mbind メソッドが必要

Scalaz で Codensity モナド

Scala Monad Scalaz

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 エラーとなる