今日のスカンクワーク(Yコンビネータ)

Haskellで階乗を求める関数をYコンビネータで実装することができる。っていうのは「The Evolution of Haskell Programmer」(via オレンジニュース)で知ってたので、自分でどこまでできるか、トライしてみた(実はちょっと覚えてもいた)。で、やっぱりムリでした。Kコンビネータ、Sコンビネータを使うのは気づいたんだけど...。

--The Evolution of Haskell Programmerより

s f g x = f x (g x)

k x y   = x

b f g x = f (g x)

c f g x = f x g

y f     = f (y f)

cond p f g x = if p x then f x else g x

fac  = y (b (cond ((==) 0) (k 1)) (b (s (*)) (c b pred)))

Haskellの場合、Yコンビネータを最初に"y f = f (y f)"と書けちゃうところがCOOLだ、と思う。しかしそれにしても道は長くて嶮しい。