Haskellで賢人鳥(またの名をYコンビネーター)

賢人鳥で書いた内容の訂正です。unsafeCoerce を使えば、Haskell でも自己言及するコードが書けます。すなわち、ものまね鳥はこうです。

import Unsafe.Coerce

m x = x (unsafeCoerce x)

という訳で、チョウゲンボウとホシムクドリから賢人鳥を導出してみます。

import Unsafe.Coerce

k x y = x  -- aka const
s x y z = x z (y z)
i = s k k -- aka id
b = s (k s) k
w = s s (k i)
l = b w (unsafeCoerce b)
y = s l l

階乗だって動きます。

fact = \f x -> if x == 0 then 1 else x * f (x-1)

y fact 4 :: Int
→ 24

フィボナッチ数列だって動きます。

fib = \f n -> if n < 2 then n else (f (n-1)) + (f (n-2))

y fib 5 :: Int
→ 5

y を使うときは、必ず型を指定して下さい。

すごーい。すごーい。すごーい。