Trying to exercise with the Cont monad. Syntax issue

Question

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

first: the gist is fine in itself but why don't you copy&paste the code in here - it's just convenient for us trying to help out here - next I don't think your types match up (or I guess wrong what you are trying to do) - have you tried to solve this problem just with continuation-passing-style (you don't exactly need the monad/Cont-wrapper to understand the technique)? — Random Dev
@carsten - This attempt of mine arises indeed from a perfectly working CPS implementation, definitely too trivial to mention. I believe it's clear that the whole point of this question is about using the monad, and especially its bind function. — Marco Faustinelli

chi chi · Accepted Answer · 2015-08-16T17:44:35

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)

Trying to exercise with the Cont monad. Syntax issue

1 Answers