[Haskell-beginners] Monadic fixed-point combinator.

[Lyndon Maydwell]

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?