lambda.groovy

//Zコンビネータ
//再帰する関数を定義するのに使う
ZCONB = { f -> ({ x -> f({ y -> x(x)(y) }) })({ x -> f({ y -> x(x)(y) }) }) }

//数の定義
ZERO  = { f -> { x -> x }}
ONE   = { f -> { x -> f(x) }}
THREE = { f -> { x -> f(f(f(x))) }}
FIVE  = { f -> { x -> f(f(f(f(f(x))))) }}
NINE  = { f -> { x -> f(f(f(f(f(f(f(f(f(x))))))))) }}
TEN   = { f -> { x -> f(f(f(f(f(f(f(f(f(f(x)))))))))) }}

//ZEROならTRUEを、それ以外ならFALSEを返す
IS_ZERO = { n -> n({ x -> FALSE })(TRUE) }

//インクリメント
INC = { n -> { f -> { x -> f(n(f)(x)) }}}
//デクリメント
DEC = { n -> LEFT(n({ p -> PAIR(RIGHT(p))(INC(RIGHT(p))) })(PAIR(ZERO)(ZERO))) }
//加算
ADD = { m -> { n -> { f -> { x -> n(f)(m(f)(x)) }}}}
//減算
SUB = { m -> { n -> n(DEC)(m) }}
//乗算
MUL = { m -> { n -> n(ADD(m))(ZERO) }}
//除算
DIV = ZCONB({ f -> { m -> { n -> IF(IS_LESS_OR_EQUAL(n)(m))({ x -> INC(f(SUB(m)(n))(n))(x) })(ZERO) }}})
//余剰算
MOD = ZCONB({ f -> { m -> { n -> IF(IS_LESS_OR_EQUAL(n)(m))({ x -> f(SUB(m)(n))(n)(x) })(m) }}})

//m <= n
IS_LESS_OR_EQUAL = { m -> { n -> IS_ZERO(SUB(m)(n)) }}

//数の定義再び
FIFTEEN = MUL(THREE)(FIVE)
HUNDRED = MUL(TEN)(TEN)

//真偽値とIF
TRUE  = { x -> { y -> x }}
FALSE = { x -> { y -> y }}
IF = { c -> { x -> { y -> c(x)(y) }}}

//ペアと各要素を取り出す関数
PAIR  = { x -> { y -> { f -> f(x)(y) }}}
LEFT  = { p -> p(TRUE) }
RIGHT = { p -> p(FALSE) }

//リスト関連
//リストは真偽値と値のペアをひとつの要素として表現する
//要素をペアで連結したのがリストとする

//空のリスト
NIL  = PAIR(PAIR(TRUE)(TRUE))(TRUE)
//要素とリストを結合して新しいリストを作る
CONS = { h -> { t -> PAIR(PAIR(FALSE)(h))(t) }}
//先頭の要素を取り出す
HEAD = { l -> RIGHT(LEFT(l)) }
//先頭の要素を除いたリストを返す
TAIL = { l -> RIGHT(l) }
//空のリストならTRUE、それ以外ならFALSEを返す関数
IS_NIL = { l -> LEFT(LEFT(l)) }
//末尾に要素を追加してリストを作る関数
PUSH = ZCONB({ f -> { l -> { x -> IF(IS_NIL(l))(CONS(x)(l))({ y -> CONS(HEAD(l))(f(TAIL(l))(x))(y) }) }}})
//xからyまでのリストを作る関数
RANGE = ZCONB({ f -> { x -> { y -> IF(IS_ZERO(SUB(y)(x)))(CONS(x)(NIL))(CONS(x)({ z -> f(INC(x))(y)(z) })) }}})
//map関数
MAP = ZCONB({f -> { g -> { l -> IF(IS_NIL(l))(NIL)({ x -> CONS(g(HEAD(l)))(f(g)(TAIL(l)))(x) }) }}})

//文字関連
//ZEROからNINEをそれぞれ0から9、10から14をFBiuzとするcharsetを想定
F = TEN
B = INC(F)
I = INC(B)
U = INC(I)
Z = INC(U)
FIZZ = CONS(F)(CONS(I)(CONS(Z)(CONS(Z)(NIL))))
BUZZ = CONS(B)(CONS(U)(CONS(Z)(CONS(Z)(NIL))))
FIZZBUZZ = CONS(F)(CONS(I)(CONS(Z)(CONS(Z)(CONS(B)(CONS(U)(CONS(Z)(CONS(Z)(NIL))))))))
//数値を文字列に変換する
TO_STR = ZCONB({ f -> { n -> IF(IS_LESS_OR_EQUAL(n)(NINE))(CONS(n)(NIL))({ x -> PUSH(f(DIV(n)(TEN)))(MOD(n)(TEN))(x) }) }})

//ラムダ計算でFizzBuzz
//それなりの計算量なので実行に時間を要するっぽい！
RET = MAP({ a -> IF(IS_ZERO(MOD(a)(FIFTEEN)))(FIZZBUZZ)(
                 IF(IS_ZERO(MOD(a)(THREE)))(FIZZ)(
                 IF(IS_ZERO(MOD(a)(FIVE)))(BUZZ)(
                 TO_STR(a))))
          })(RANGE(ONE)(HUNDRED)) 

//ラムダ計算の世界からGroovyの世界に翻訳するための補助関数
toInt = { n -> n({ it + 1})(0) }
toBool = { b -> b(true)(false) }
toChar = { '0123456789FBiuz'[toInt(it)] }
toStr = { toList(it).collect(toChar).join() }
toList = { xs ->
        def ret = []
        while(toBool(IS_NIL(xs)) == false) {
            ret.add(HEAD(xs))
            xs = TAIL(xs)
        }
        ret
    }

//FizzBuzzの結果を表示
println(toList(RET).collect(toStr))

アンダースタンディングコンピュテーションの6章をGroovyで写経したけど上手く動かなかったりRubyっぽさに馴染めなかったので一旦すべて忘れて改めて書き直した。

次のコマンドで試せる、はず。

git clone https://gist.github.com/backpaper0/62e0d1caca72fb0c07ca backpaper0_lambda
cd backpaper0_lambda
groovy lambda.groovy

そこそこ実行に時間かかるのでそれだけご了承ください的な！

これでも実行できる。

groovy https://gist.githubusercontent.com/backpaper0/62e0d1caca72fb0c07ca/raw/a504609844e1801e0301dc32549527ab5dae22d5/lambda.groovy