memoizeと不動点

プログラミング

[id:lethevert:20050903:p2]
できた！！

fix g = f
where
    f = g f

whereを使えば書けたんだ。
ということで、memoizeも含めたConcurrent Clean版は↓です。（リストの選択に必要な計算量はこの際無視で）

module memo

import StdEnv

Start
    = map fib [1,2,3,4,5]

//fib = fix fib_maker
fib = fix_memo fib_maker
where
    fib_maker :: (Int -> Int) Int -> Int
    fib_maker f 0 = 0
    fib_maker f 1 = 1
    fib_maker f n = f (n-1) + f (n-2)

fix :: ( (Int -> Int) -> (Int -> Int) ) -> (Int -> Int)
fix maker = f
where
    f = maker f

fix_memo :: ( (Int -> Int) -> (Int -> Int) ) -> (Int -> Int)
fix_memo maker = f
where
    f = (!!) tbl
    tbl = map (maker f) [0..]

参考）
http://d.hatena.ne.jp/tanakh/20041126#p2
http://sky.zero.ad.jp/~zaa54437/programming/clean/CleanBook/part1/Chap6.html#sc6
http://www.kmonos.net/wlog/52.php#_0308050827

      • -

括弧のネストが、注釈になってしまった。HatenaでLispやSchemeのソースをコピペのは、かなりめんどくさい予感

      • -

上のソースを使って、いろいろ遊んでいたら、変な数字が出てきた。よく考えたら、CleanのIntは32ビット整数値なのだった。HaskellのIntegerのような任意精度の整数ってないのかな？