[Haskell-beginners] Monadic fixed-point combinator.
Lyndon Maydwell
maydwell at gmail.com
Wed Aug 11 17:33:14 EDT 2010
Hi beginners.
I've been looking at fixed-point combinators for the purpose of
memoization for a few days recently and was wondering if there is a
nice way to add monadic actions to an implicitly recursive[1]
function. For example: If I have fib defined like so:
> fib :: (Integer -> Integer) -> Integer -> Integer
> fib f 0 = 0
> fib f 1 = 1
> fib f n = f (n-1) + f (n-2)
I can create an inefficient fib' using fix:
> fix :: (a -> a) -> a
> fix f = f (fix f)
>
> fib' :: Integer -> Integer
> fib' = fix fib
Or a memoized fib'' using memoFix and a memoization scheme:
> type MFB a b = (a -> b) -> a -> b
> memoFix :: MFB a b -> MFB a b -> a -> b
> memoFix mem f = let mf = mem (f mf) in mf
>
> integer :: (Int -> b) -> Int -> b
> integer f = (A.listArray (0,200) (L.map f [0..200]) A.!)
>
> fib'' = memoFix integer fib
But would there be a way to add, say, execution tracing using an IO combinator?
> ioFix :: (a -> IO a) -> IO a
> fix f = print "step" >> f (fix f)
I've had a play around with these functions, attempting to lift them
into monadic actions, but I really have no idea how to approach this.
Thanks for your help!
[1] - What do you call the form of a function where recursion is
implemented by a fixed point combinator?
More information about the Beginners
mailing list