Yコンビネータ

Program Haskell

フィボナッチと階乗やってみる。

> let y f = f $ y f
> :i y
y :: (b -> b) -> b      -- Defined at <interactive>:1:4
> y (\f n -> if n < 2 then n else f (n-1) + f (n-2)) 7
13
> y (\f n -> if n < 2 then n else f (n-1) + f (n-2)) 100
Interrupted.　← (´・ω・｀)ｼｮﾎﾞｰﾝ

> y (\f (a,b) m -> if m < 2 then a else f (b, a + b) (m - 1)) (1,1) $ 7
13
> y (\f (a,b) m -> if m < 2 then a else f (b, a + b) (m - 1)) (1,1) $ 100
354224848179261915075

フィボナッチ。

> y (\f n -> if n < 2 then n else n * f (n-1)) 10
3628800
> y (\f n -> if n < 2 then n else n * f (n-1)) 100
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000
> y (\f a b -> if b < 2 then a else f (a*b) (b-1)) 1 $ 10
3628800
> y (\f a b -> if b < 2 then a else f (a*b) (b-1)) 1 $ 100
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

階乗。