CODEWITHSUNDEEP
haskellbindmonads
LostMohican
LostMohican

Reputation: 3144

Haskell trouble writing bind function for a monad instance (function transformation?)

I need to write the following function: 

bind :: ((a -> Action) -> Action) -> (a -> ((b -> Action) -> Action)) -> ((b -> Action) -> Action)

Action is a type constructor that I defined. Trouble is when I try to implement it in the following way: 

bind f g =

I do not know how to pass a value of type "a" to the function g. I am clueless regarding to get the value.

As a matter of fact this looks like some kind of transforming one function to another, but I also don't know how to achieve that.

What should I do to make this transformation possible?

Upvotes: 1

Views: 163

Answers (2)

effectfully
effectfully

Reputation: 12715

This is the Cont monad bind. Without a newtype wrapper it looks like this:

bind :: ((a -> r) -> r) -> (a -> ((b -> r) -> r)) -> ((b -> r) -> r)

First, remove redundant brackets:

bind :: ((a -> r) -> r) -> (a -> (b -> r) -> r) -> (b -> r) -> r

Second, let b -> r = br:

bind :: ((a -> r) -> r) -> (a -> br -> r) -> br -> r

Now you have

bind s f k = ?

where s :: (a -> r) -> r, f :: a -> br -> r and k :: br.

And

flip f k     :: a -> r
s (flip f k) :: r

so

bind :: ((a -> r) -> r) -> (a -> ((b -> r) -> r)) -> ((b -> r) -> r)
bind s f k = s (flip f k)

Or simply

bind s f = s . flip f

Or in pointfree

bind = (. flip) . (.)

Upvotes: 5

chi
chi

Reputation: 116139

Your monad is called the continuation monad Cont r a = ((a->r)->r) (minus a newtype wrapper) where r = Action in your case. But let's adventure a bit without looking at how that monad is defined...

Let's boldly start with:

bind :: forall a b. ((a -> Action) -> Action) -> (a -> ((b -> Action) -> Action)) -> ((b -> Action) -> Action)
bind f g = (??? :: (b -> Action) -> Action)

So, let's start filling the ???. We need to produce a function, so let's exploit a lambda for that:

bind :: forall a b. ((a -> Action) -> Action) -> (a -> ((b -> Action) -> Action)) -> ((b -> Action) -> Action)
bind f g = \k :: (b -> Action) -> (??? :: Action)

Once having overcome that, we now need to craft an Action. We have several functions in our hands returning that: f,g,k, each requiring different args. This is a matter of trial-and-error. Let's guess... f.

bind :: forall a b. ((a -> Action) -> Action) -> (a -> ((b -> Action) -> Action)) -> ((b -> Action) -> Action)
bind f g = \k :: (b -> Action) -> f (??? :: a -> Action)

We again need a function: sprinkle more lambdas, more lambdas!

bind :: forall a b. ((a -> Action) -> Action) -> (a -> ((b -> Action) -> Action)) -> ((b -> Action) -> Action)
bind f g = \k :: (b -> Action) -> f (\x :: a -> (??? :: Action))

Groan..., we need again to produce an Action. Was what we did pointless? Are we looping in circles? No, we now have x :: a in scope, so we now grew in power. Let's use g now:

bind :: forall a b. ((a -> Action) -> Action) -> (a -> ((b -> Action) -> Action)) -> ((b -> Action) -> Action)
bind f g = \k :: (b -> Action) -> f (\x :: a -> g (???1 : a) (???2 :: b -> Action))

Well, the first argument of g is now trivial to find.

bind :: forall a b. ((a -> Action) -> Action) -> (a -> ((b -> Action) -> Action)) -> ((b -> Action) -> Action)
bind f g = \k :: (b -> Action) -> f (\x :: a -> g x (???2 :: b -> Action))

More lambdas, more lambdas!

bind :: forall a b. ((a -> Action) -> Action) -> (a -> ((b -> Action) -> Action)) -> ((b -> Action) -> Action)
bind f g = \k :: (b -> Action) -> f (\x :: a -> g x (\y :: b -> (??? :: Action)))

Argh! Not another Action to produce! But all is not lost, we grew in power: we now have both x::a and y::b at our call! We also never used k... uhm....

To do:

  1. Defeat the last ???.
  2. Provide a return/unit function for the monad.
  3. Prove the monad laws.
  4. Profit!

Upvotes: 3

Related Questions