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?