[L03 Moonads] [SPOILERS] Answers and questions

[Riaan Rottier]

Here's my attempt at L03 Moonads: 

https://github.com/rrottier/course/blob/master/src/L03/Moonad.hs

And here's Tony's answers: 

https://github.com/tonymorris/course/blob/answers/src/L03/Moonad.hs

Can anyone explain the following to me:

• How do you solve lift3 using apply and lift2?
• How do you get seequence to match Tony's solution? -> I think this is the same question that David asked for L02 seqf but even thought I read the explanation for that I still don't get it.
• How do you get from where I am with filtering to the foldr solution?

[Tony Morris]

On 01/02/13 16:59, Riaan Rottier wrote:

Here's my attempt at L03 Moonads: 

https://github.com/rrottier/course/blob/master/src/L03/Moonad.hs

And here's Tony's answers: 

https://github.com/tonymorris/course/blob/answers/src/L03/Moonad.hs

Can anyone explain the following to me:

• How do you solve lift3 using apply and lift2?

This is a good question. As an aside, I suggest making the following realisations:

* fmaap is lift1 just with a different name.
* reeturn is lift0 just with a different name.
* lift for arity N can be written with lift for arity N-1 and one call to apply.

Taking these insights, let us consider lift2. We should be able to write this using lift1 (fmaap) and one call to apply. To step through it some:

lift2 :: Monad m => (a -> b -> c) -> m a -> m b -> m c

Let's first alias fmaap to be clearer:
lift1 :: Monad m => (a -> b) -> m a -> m b
lift1 = fmaap

Let us call our arguments to lift2: f, a, b

-- f :: a -> b -> c
-- ma :: m a
-- mb :: m b
lift2 f a b = ...

Now if we lift1 the function f on the value ma:

let r = lift1 f ma

We have an expression of the type :: m (b -> c)

Now if we take that and use apply with mb:
let s = apply r mb

Then we have a value of the type m c, which we return. In full:
lift2 f ma m b = apply (lift1 f ma) mb

Now follow the same reasoning for lift3 using (lift2 + apply) and so on for further N.

Here are the signatures to all the lift functions. The pattern should be obvious.

* lift0 :: a -> m a
* lift1 :: (a -> b) -> m a -> m b
* lift2 :: (a -> b -> c) -> m a -> m b -> m c
* lift3 :: (a -> b -> c -> d) -> m a -> m b -> m c -> m d

Then recognise that apply and lift[N] takes you to lift[N+1].

• How do you get seequence to match Tony's solution? -> I think this is the same question that David asked for L02 seqf but even thought I read the explanation for that I still don't get it.

The seequence that I have provided was originally inspired by providing the solution to work for any Moonad and not just ((->) t). Obviously, the specificity of this monad allows a much easier solution. I think this exercise is a bit of a red-herring because of that.

• How do you get from where I am with filtering to the foldr solution?

Equational reasoning! Or what I like to call a game of Spot The Difference. You remember that game right? All you do is take your existing code and spot the difference with your solution and since the "image" has structure, you can work out possibilities to replace one image with another. For example, any time you see in your code the expression bind (reeturn . f) you can confidently replace with fmaap f because that is precisely the definition of fmaap. Just keep playing this game until you have no more substitutions.

Taking a section of your code:

* bind (\as -> if b then reeturn (a:as) else reeturn as)

This can be rewritten:

* bind (\as -> reeturn (if b then (a:as) else as))
[   since the expression (if p then f a else f b) can be replaced with f(if p then a else b)   ]

Which can in turn be rewritten:
* bind (\as -> reeturn (if b then (a:) as else id as))
[   since the expression (x) can be replaced with (id x)   ]

Which can in turn be rewritten:
* bind (\as -> reeturn ((if b then (a:) else id) as))
[   since the expression (\x -> if p then f x else g x) can be replaced with (\x -> (if p then f else g) x)   ]

Which can in turn be rewritten:
* bind (reeturn . (if b then (a:) else id))
[   since the expression (\x -> f (g x)) can be replaced with (f . g)   ]

Which can in turn be rewritten:
* fmaap (if b then (a:) else id)
[   since the expression (bind (return . f)) can be rewritten (fmaap f)

So now you have:
filtering _ [] = reeturn []
filtering p (a:as) = bind (\b -> (fmaap (if b then (a:) else id) (filtering p as))) (p a)

and you also have available:

foldRight _ b Nil = b
foldRight f b (h :| t) = f h (foldRight f b t)

So now it is a matter of playing spot the difference here, reader's exercise :)

Note: equational reasoning falls apart in the presence of side-effects. Thankfully, Haskell does not have side-effects!

--
You received this message because you are subscribed to the Google Groups "haskell-exercises" group.
To unsubscribe from this group and stop receiving emails from it, send an email to haskell-exerci...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
 
 

-- 
Tony Morris
http://tmorris.net/

[Riaan Rottier]

Thanks Tony

More clear now, except for:

"The seequence that I have provided was originally inspired by providing the solution to work for any Moonad and not just ((->) t). Obviously, the specificity of this monad allows a much easier solution. I think this exercise is a bit of a red-herring because of that."

I am a bit confused.  I don't see the ((->) t) in Exercise 15...  It does seem like it should work for any monad.  Can you please elaborate?

[Tony Morris]

Oh wait I was thinking of L02.List#seqf not seequence.

[Tony Morris]

To be clear, seqf is a specialisation of seequence, but that specialisation permits an easier solution than the one that works in general.

On 02/02/13 20:12, Riaan Rottier wrote: