CODEWITHSUNDEEP
haskellmonadscontinuations
Marco Faustinelli
Marco Faustinelli

Reputation: 4206

Trying to exercise with the Cont monad. Syntax issue

After some study ([1], [2], [3] among others) I am trying to make work of the continuation monad by attempting some examples on my own.

The second answer to [1] suggests to express the factorial using continuations. My solution is the following:

Cont ($ (fact 0)) = return 1
Cont ($ (fact n)) = Cont ($ (fact (n-1))) >>= (\x -> Cont ($ (n*x)))

I've done some simulations on paper and the solution should be correct.

However I am unable to have it digested by GHC. Of course I renamed the fact function, but still no joy.

My latest attempt is https://gist.github.com/Muzietto/595bef1815ddf375129d and gives as always a parse error in pattern \c -> .....

Can anyone suggest a running implementation for these definitions?

[1] How and why does the Haskell Cont monad work?

[2] http://hackage.haskell.org/package/mtl-1.1.0.2/docs/Control-Monad-Cont.html

[3] https://wiki.haskell.org/MonadCont_under_the_hood

Upvotes: 0

Views: 164

Answers (1)

chi
chi

Reputation: 116139

First, you can not define a function in the way you posted for the same reason you can not implement a predecessor function as follows:

1 + (predecessor x) = x

Functions can only be defined through equations of the form

f pattern1 .. patternK = expression

Note that f must be found at the top-level.

For your factorial function using the continuation monad, you can simplify your attempt as follows:

fact :: Int -> Cont r Int
-- Your own code:
-- Cont ($ (fact 0)) = return 1
fact 0 = return 1
-- Cont ($ (fact n)) = Cont ($ (fact (n-1))) >>= (\x -> Cont ($ (n*x)))
fact n = fact (n-1) >>= \x -> return (n*x)

-- the "real" factorial function, without monads
factorial :: Int -> Int
factorial n = runCont (fact n) id

Note that return (n*x) above is indeed Cont ($ (n*x)), but I think it's more readable in the former way, also because it does not break the abstraction. Indeed, it would work in any monad once written as above.

Alternatively, use do notation.

fact :: Int -> Cont r Int
fact 0 = return 1
fact n = do
   x <- fact (n-1)
   return (n*x)

Or use a functor operator:

fact :: Int -> Cont r Int
fact 0 = return 1
fact n = (n*) <$> fact (n-1)

Upvotes: 4

Related Questions