Trying to exercise with the Cont monad. Syntax issue

Question 1

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 1Cont ($ (fact n)) = Cont ($ (fact (n-1))) >>= (\x -> Cont ($ (n*x)))

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

HoweverI am unable to have it digested by GHC. Of course I renamed thefact function, but still no joy.

My latest attempt ishttps://gist.github.com/Muzietto/595bef1815ddf375129dand gives as always aparse 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

Question 2

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)?

Question 3

@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.

Question 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 thatf 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 1fact 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 monadsfactorial :: Int -> Intfactorial n = runCont (fact n) id

Note thatreturn (n*x) above is indeedCont ($ (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 inany monad once written as above.

Alternatively, usedo notation.

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

Or use a functor operator:

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

Question 5

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.

Question 6

@Muzietto Monads are required to be "compatible" with their functor instance in the sense that they must satisfy the lawfmap f x = x >>= (return . f). Basically and informally, if you get something out of the monad (>>=), apply somef and then put it back in the monad withreturn, the result should be the same offmap f.

Question 7

yes I am aware of the relationship between functors and monads, but I've always consideredbind to be on a higher level of abstraction (and capabilities) thanfmap. Seeingfmap here do more or less the same job in an even terser syntax is quite surprising.

chi 117k4 gold badges144 silver badges230 bronze badges · Accepted Answer · 2015-08-16 17:52:39Z

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 thatf 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 1fact 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 monadsfactorial :: Int -> Intfactorial n = runCont (fact n) id

Note thatreturn (n*x) above is indeedCont ($ (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 inany monad once written as above.

Alternatively, usedo notation.

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

Or use a functor operator:

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

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.
@Muzietto Monads are required to be "compatible" with their functor instance in the sense that they must satisfy the lawfmap f x = x >>= (return . f). Basically and informally, if you get something out of the monad (>>=), apply somef and then put it back in the monad withreturn, the result should be the same offmap f.
yes I am aware of the relationship between functors and monads, but I've always consideredbind to be on a higher level of abstraction (and capabilities) thanfmap. Seeingfmap here do more or less the same job in an even terser syntax is quite surprising.

Movatterモバイル変換

Collectives™ on Stack Overflow

Trying to exercise with the Cont monad. Syntax issue

1 Answer1

3 Comments

Your Answer

Sign up orlog in

Post as a guest

Linked

Related

Hot Network Questions

Subscribe to RSS