Scalaの型推論って難しい

ラムダ計算とかの例によくある チャーチ数 をScalaで試してみる。

原点を表す Zero 、次を表す Succ を定義しておけば足し算とかできるってやつ。

まずは試し書き

import Conrtol.Applicative

zero f a = a
succ n f a = f $ n f a

one = succ zero
two = succ one

add a b = liftA2 (.) a b

toInt n = n (\a -> a + 1) 0
toAs n = n (\a -> 'a' : a) []

a = add (succ two) one

main = do
    putStrLn $ show $ toInt a // => 4
    pusStrLn $ show $ toAs a // => "aaaa"

わざと型は明記していない。haskellなどのきちんと型推論してくれる言語であればこれで動く。

もしくは動的型の言語でも。

def zero(f):
    def x(a):
        return a
    return x

def succ(n):
    def x(f):
        def y(a):
            return f(n(f)(a))
        return y
    return x

one = succ(zero)
two = succ(one)

def add(n):
    def x(m):
        def y(f):
            def z(a):
                return n(f)(m(f)(a))
            return z
        return y
    return x

def to_int(n):
    return n(lambda x: x + 1)(0)

def to_as(n):
    return n(lambda x: "a" + x)("")

a = add(succ(two))(one)

to_int(a) # => 4
to_as(a) # => 'aaaa'

Scalaの場合

これがScalaだとまあ大変で。。。

def zero[A](f: A => A)(a: A) = a

この時点で上記の例ではなんでもよかった(使ってない) f の型を固定。
固定しない場合型指定が大変になる(後述)。

なお、戻り値の型は書くべきだと思うけれども、今回は型推論具合を知りたいから書かなくても動作する限り省略。

def succ[A](n: (A => A) => A => A)(f: A => A)(a: A) = f(n(f)(a))

def one[A]: (A => A) => A => A = succ(zero)
def two[A]: (A => A) => A => A = succ(one)

import scalaz._
import Scalaz._  // Applicativeの導入(必須ではないけど・・・)
def add[A](x: (A => A) => A => A)(y: (A => A) => A => A) = (x |@| y) { case (a, b) => a compose b }

def toInt(n: (Int => Int) => Int => Int) = n(a => a + 1)(0)
def toAs(n: (List[Char] => List[Char]) => List[Char] => List[Char]) = n(a => 'a' :: a)(List.empty)

// def a[A]: (A => A) => A => A = add(succ(two))(one) // => 型エラー！！
def a[A]= add[A](succ(two))(one)

println(toInt(a)) // => 4
println(toAs(a)) // => List(a, a, a, a)

型が必須な上に、 val が型引数を受け付けてくれないからギリギリまで def じゃないといけない。

できる限りHaskellでやった時の型に近づけると以下のような感じ？

def zero[F, A](f: F)(a: A) = a
def succ[A, B, C](n: (B => C) => A => B)(f: B => C)(a: A) = f(n(f)(a))

def one[A, B]: (A => B) => A => B = succ(zero)
def two[A]: (A => A) => A => A = succ(one)

def add[A, B, C, D](x: A => B => C)(y: A => D => B) = (x |@| y) { case (a, b) => a compose b }

def toInt(n: (Int => Int) => Int => Int) = n(a => a + 1)(0)
def toAs(n: (List[Char] => List[Char]) => List[Char] => List[Char]) = n(a => 'a' :: a)(List.empty)

// def a[A]: (A => A) => A => A = add(succ(two))(one) // => 型エラー！！
def a[A] = add[(A => A), A, A, A](succ(two))(one)

println(toInt(a)) // => 4
println(toAs(a)) // => List(a, a, a, a)

途中から A => A =>... みたいなのを書くことを考えれば、最初の方が綺麗な気がする。。。

最後に蛇足だけど引数の順序をScalaっぽくしてみる。

def zero[A, F](a: A)(f: F) = a
def succ[A, B, C](n: A => (B => C) => B)(a: A)(f: B => C) = f(n(a)(f))

def one[A, B]: A => (A => B) => B = succ(zero)
// def one[A, B] = succ[A, A, B](zero) _  // <- これでも通るのは通るみたい
def two[A]: A => (A => A) => A = succ(one)
// def two[A] = succ[A, A, A](one) _

def flip[A, B, C](f: A => B => C) = (b: B) => ((a: A) => f(a)(b)) // これどっかにないのかな？？？
// scalaz.Function2Optsならあるけど・・・ uncurriedみたいなのが必要だよなぁ。
def add[A, B, C, D](x: A => B => C)(y: C => B => D) = flip((flip(x) |@| flip(y)) { case (a, b) => a andThen b })

def toInt(n: Int => (Int => Int) => Int) = n(0)(a => a + 1)
def toAs(n: List[Char] => (List[Char] => List[Char]) => List[Char]) = n(List.empty[Char])(a => 'a' :: a)

// def a[A]: A => (A => A) => A = add(succ(two))(one) // => 型エラー！！
def a[A] = add[A, (A => A), A, A](succ(two))(one)

println(toInt(a)) // => 4
println(toAs(a)) // => List(a, a, a, a)

何度 A => と書いただろう・・・？？？