Exercise 9.9 - IKB: 雑記帳

fix 関数の型はどんなものかってのと、 fix を使って remainder を再帰でない形に書き直しなさいって問題。 fix と remainder の定義はそれぞれ以下のとおり:

fix f = f (fix f)

remainder :: Integer -> Integer -> Integer
remainder a b = if a < b then a
                else remainder (a - b) b

こういう問題をみると、おら、わくわくしてくっぞ！

で、 fix についてうんうん考えて、右辺から f は最低でも 1 引数をとれないとダメだってことから (a->b) -> b って型を考えてみた…んだけれど、 GHCi 先生にお尋ねしたら間違いだったことがわかりました無念。

Prelude> let fix f = f (fix f)
Prelude> :t fix
fix :: (t -> t) -> t

なるほど、再帰式だから型がそろってないとダメなんだ。再帰でない形に remainder を書き直すほうは、これもうんうんうなって考えた。答えはきっとこれでいい:

remainder a b = fix (\ f a -> if a < b then a else f (a - b)) a

-- anonymous function のところの問題なんだから次のように定義した
-- ほうが、よりよい…のかもしれない。
-- remainder = \ a b -> fix (\ f a -> if a < b then a else f (a - b)) a