Making continuation monad wrapper instance of Monad class

Question

I have type Foo which is simple wrapper around Cont a a. I would like to make Foo type an instance of Monad class. I try this:

import Control.Monad.Cont newtype Foo a = Foo {unFoo :: Cont a a} instance Monad Foo where return = Foo . return Foo inner >>= func = Foo (inner >>= newFunc) where newFunc x = (unFoo $ func x)

But I got this error:

Couldn't match type `a' with `b' `a' is a rigid type variable bound by the type signature for >>= :: Foo a -> (a -> Foo b) -> Foo b at Classes.hs:7:5 `b' is a rigid type variable bound by the type signature for >>= :: Foo a -> (a -> Foo b) -> Foo b at Classes.hs:7:5 Expected type: ContT b Data.Functor.Identity.Identity a Actual type: Cont a a In the first argument of `(>>=)', namely `inner' In the first argument of `Foo', namely `(inner >>= newFunc)' In the expression: Foo (inner >>= newFunc)

How to add Monad instance for Foo correctly?

Cirdec · Accepted Answer · 2015-01-16 01:32:51Z

You can't make Foo into a Monad.

First, let's point out that Foo a is an elaborate way of writing (a -> a) -> a.

runFoo :: Foo a -> ((a -> a) -> a) runFoo = runCont . unFoo foo :: ((a -> a) -> a) -> Foo a foo = Foo . cont

There's only one way we can define (>>=) :: Foo a -> (a -> Foo b) -> Foo b. We need an a to pass to the arrow a -> Foo b. The only thing we have that has any as is a Foo a, which is equivalent to (a -> a) -> a. It will give us an a if we can provide a function of type a -> a, which there's only one of, id. So our only choice for how to get an a is to pass id.

instance Monad Foo where return = Foo . return ma >>= f = f (runFoo ma id)

This will fail one of the Monad laws, m >>= return ≡ m. We will write a counter example that lives in Foo.

counterExample :: Foo Int counterExample = foo (\f -> if f 0 == 1 then 7 else 13)

The counter example results in 13 when passed the identity function id, but only 7 when passed the successor function (+1).

print $ runFoo counterExample id print $ runFoo counterExample (+1) 13 7

Due to the Monad laws, counterExample' = counterExample >>= return should be exactly the same as counterExample, but it can't be. >>= already passed id to the function and only returned the result, 13. counterExample' doesn't do the same thing as counterExample.

let counterExample' = counterExample >>= return print $ runFoo counterExample' id print $ runFoo counterExample' (+1) 13 14

Since there was only one possible implementation of >>= and it isn't correct there is no correct Monad instance for Foo.

Collectives™ on Stack Overflow

Making continuation monad wrapper instance of Monad class

1 Answer 1

Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Related