CODEWITHSUNDEEP
haskellmonadsfunction-composition
Roscode
Roscode

Reputation: 123

Haskell Function composition of two binary functions?

I'm working my way through 20 Intermediate Haskell exercises and I got stuck on exercise 13:

-- Exercise 13
-- Relative Difficulty: 6
apple :: (Misty m) => m a -> m (a -> b) -> m b
apple = error "todo"

where the Misty Typeclass is essentially the Monad Typeclass and is implemented like this:

class Misty m where
    banana :: (a -> m b) -> m a -> m b
    unicorn :: a -> m a

I gave in to my curiosity and found the solution to this exercise online as

apple = banana . flip furry'

where furry' is a version of liftM implemented as

furry' f mi = banana (\x -> unicorn (f x)) mi

What I don't understand is the use of function composition (.) on two binary functions (namely banana and the flipped furry'), if someone could walk through the evaluation of this I think that would help me a lot.

Upvotes: 2

Views: 299

Answers (1)

Sibi
Sibi

Reputation: 48644

Let's start step by step. Misty typeclass is given:

class Misty m where 
  banana :: (a -> m b) -> m a -> m b 
  unicorn :: a -> m a

Also furry' is already solved in an earlier problem in those exercises:

furry' :: Misty m => (a -> b) -> m a -> m b
furry' f mi = banana (\x -> unicorn (f x)) mi

Now you have apple function which you have to define:

apple :: (Misty m) => m a -> m (a -> b) -> m b
apple = error "todo"

Now just try to follow the type signature. Assume you are defining apple like this:

apple xs ys

xs will have type of m a

ys will have type of m (a -> b)

Now can you see the relation between the above types and furry' ? So you have to somehow apply xs and ys to furry' Now since it's second parameter is m a which you already have in xs, you can use flip to obtain it:

flip furry' :: m a -> (a -> b) -> m b

So you can apply xs to the first parameter of it and you will have the following type signature:

(flip furry') xs :: (a -> b) -> m b ------- Equation 1

Any guess on how to apply it ys? Try to unify the above type signature with the first parameter of banana :

That will give you:

a ~ (a -> b)
m b ~ (m b)

So, the type signature of banana gets transformed from

banana :: (a -> m b) -> m a -> m b

to

banana :: ((a -> b) -> m b) -> m (a -> b) -> m b

Now from Equation (1) we know that (flip furry') xs type signature matches the first parameter of banana and ys matches the second parameter of banana. And that gives you the definition of apple:

apple :: (Misty m) => m a -> m (a -> b) -> m b
apple xs ys = banana ((flip furry') xs ) ys

which can be expressed in pointfree manner as:

apple :: (Misty m) => m a -> m (a -> b) -> m b
apple = banana . flip furry'

Upvotes: 4

Related Questions