0

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

Community
  • 1
  • 1
Marco Faustinelli
  • 3,734
  • 5
  • 30
  • 49
  • 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 Aug 16 '15 at 16:20
  • @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 Aug 16 '15 at 21:00

1 Answers1

4

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)
duplode
  • 33,731
  • 7
  • 79
  • 150
chi
  • 111,837
  • 3
  • 133
  • 218
  • Thank you! I suspected I was doing something not-haskellian in my code :-) I am keen in getting a feel for 'bind', hoping to bring abstraction to a higher level. I appreciated the thoroughness and completeness of your answer. The functor version is mind-blowing. Gotta spend some time thinking about this fmap. – Marco Faustinelli Aug 16 '15 at 21:19
  • 1
    @Muzietto Monads are required to be "compatible" with their functor instance in the sense that they must satisfy the law `fmap f x = x >>= (return . f)`. Basically and informally, if you get something out of the monad (`>>=`), apply some `f` and then put it back in the monad with `return`, the result should be the same of `fmap f`. – chi Aug 16 '15 at 21:23
  • yes I am aware of the relationship between functors and monads, but I've always considered `bind` to be on a higher level of abstraction (and capabilities) than `fmap`. Seeing `fmap` here do more or less the same job in an even terser syntax is quite surprising. – Marco Faustinelli Aug 17 '15 at 15:46