禁断の不動点コンビネータ

フィボナッチ数列を汎関数で書く。

fib :: (Integer -> Integer) -> Integer -> Integer
fib _ 0 = 0
fib _ 1 = 1
fib f n = f (n-1) + f (n-2)

そして、不動点コンビネータを遅延評価を活かして以下のように定義する。(Control.Monad.Fix を import しても OK)

fix :: ((a -> a) -> a -> a) -> a -> a
fix f x = f (fix f) x

動かしてみる。

fix fib 10
→ 55

さらに、不動点コンビネータにメモ化の機能を入れる。まじめに State モナドを使うと、たくさん頑張らないといけない。そこで、禁断の unsafePerformIO を使う。

import Data.IORef
import System.IO.Unsafe
import Data.Map (Map)
import qualified Data.Map as M hiding (Map)

memo :: Ord a => IORef (Map a a)
memo = unsafePerformIO (newIORef M.empty)

mfix :: (Show a, Ord a) => ((a -> a) -> a -> a) -> a -> a
mfix f x = unsafePerformIO $ do 
    m <- readIORef memo
    case M.lookup x m of
        Just v -> return v
        Nothing -> do
            let v = f (mfix f) x
            modifyIORef memo (M.insert x v)
            return v

動かしてみる。

mfix fib 10
→ 55

やはり、こういうのは副作用があるコードの方がシンプルで書きやすい。