Concurrent Clean : L.L.Ring : Collatz予想の収束問題

[id:lethevert:20060712:p2]コメント欄で指摘されました。
数学的には無限数列が収束するということにしておいて問題なさそうだけど、確かに問題文には従っていないです。
ただ、さすがに関数の呼び出し回数を何の仕掛けもなしに数えることは無理なので（Rubyでも、ブロックを引数にするなどの工夫が要りますよね）、Y Combinatorという仕掛けを使ってみます。（ちなみに、Y Combinatorとは、再帰的な定義を陽に書かずに再帰を書くためのトリックと言えば、分かりやすいでしょうか・・・）
まず、問題文にあるとおりの関数定義を普通に行うと、

f 1            = 1
f n | isEven n = f (n/2)
               = f (3*n+1)

ですが、これをY Combinatorを使って定義しなおすと、

g = y \f n = if (n==1)     1
             if (isEven n) (f (n/2))
                           (f (3*n+1))

というようになります。
で、この関数 y に上手く仕掛けをして、呼び出し回数を数えるようにします。

y p n = q 0 n
  where
    q c n | n == 1 = c
          = p (q (c+1)) n

で、最後は前と同じように、任意の調査区間に対して最大のステップ数になる数を求めます。

h n = fst $ maxListBy cmp [(x,g x) \\ x <- [1..n]]
  where
    cmp (_,a) (_,b) = a < b

Start = h 100

以上、お粗末様でした。