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 を使うときは、必ず型を指定して下さい。
すごーい。すごーい。すごーい。