Benjamin Smith

[Recent Entries][Archive][Friends][User Info]

Below are the 2 most recent journal entries recorded in the "Benjamin Smith" journal:

December 19th, 2006

08:14 pm

I’ve been thinking a bit about using a monad to hide general recursion. By hide, I mean that you cannot construct a function fix with type (∀a. (a -> a) -> a). The first monad I tried was basically a reader monad with a run function that just used fix. Needless to say this doesn’t hide the recursion. My next attempt is more successful and has the interface below:

data Rec a b
instance Monad (Rec a)
instance MonadReader a (Rec a)
recurse :: a -> Rec a a
runRec :: a -> Rec a a -> a

And here’s an example of using it to write a fibonacci function.

-- Fibonacci sequence
fib :: Integer -> Integer
fib n = runRec n $ do
  n <- ask
  case n of
    0 -> return 0
    1 -> return 1
    _ -> do
      x <- recurse (n-2)
      y <- recurse (n-1)
      return (x + y)

The next thing I want to try is to prove that you can’t construct fix. I guess my argument would start need to start off with looking at runRec and where I’m going to get something for its first argument.

Tags: computer science, haskell, monads