8

I am a rookie just start learning Haskell so please bear with me if I am asking stupid questions.

Recently I come across questions in SO demonstrating how to deriving type and implementation of functions & expression (questions such as

How can I understand "(.) . (.)"?

&

Haskell function composition, type of (.)(.) and how it's presented )

I find the answers very inspiring

I, then, try to come up some exercises for myself to make sure I know how to apply those techniques.

Then I come up with this expression myself: (<*>)(<*>) which I don't know how to solve.

In GHCi, it gives the type signature as:

(<*>)(<*>) :: Applicative f => (f (a -> b) -> f a) -> f (a -> b) -> f b

but my problem is how could I start from 

(<*>) :: Applicative f => f (a -> b) -> f a -> f b

and derive the type signature as given by GHCi?

Furthermore, based on the type signature, how the implementation of (<*>)(<*>) = ?? would be?

I am stuck and cannot resolve this by techniques such as re-arranging terms, etc. I don't even have a clue on where to start with.

Would somebody give me a help?

Thanks a lot

note** : the expression (<*>)(<*>) really does not bear special meanings, it's just an exercise I come up for myself randomly

Community
  • 1
  • 1
gatek
  • 103
  • 1
  • 5
  • 1
    I would like to thank all of you to contribute high quality answers in a timely manner, all answers are great and inspiring, they save my days It's really difficult for me to pick just one. I wish I could accept multiple answers. – gatek Dec 24 '14 at 05:14

4 Answers4

8

First of all, let's write out the type of (<*>) with two disjoint set of type variables:

(<*>) :: (Applicative f) => f (a -> b) -> f a -> f b
(<*>) :: (Applicative g) => g (c -> d) -> g c -> g d

If we want to use the second one with the first one as its argument, we need

g (c -> d) ~ f (a -> b) -> f a -> f b

yielding

g ~ (f (a -> b) ->)    or,   ((->) (f (a -> b)) )
c ~ f a
d ~ f b

and note that the choice of g is indeed an applicative functor: it's the un-newtyped Reader (f (a -> b)) applicative.

And so the application has type

g c -> g d

which we now know to be

(f (a -> b) -> f a) -> (f (a -> b) -> f b)

q.e.d.

Cactus
  • 27,075
  • 9
  • 69
  • 149
4

Furthermore, based on the type signature, how the implementation of (<*>)(<*>) = ?? would be?

It's easier to reverse the order (find the implementation first, and then derive its type).

Applicative instance for functions is

instance Applicative ((->) a) where
    pure = const
    (<*>) f g x = f x (g x)

So simply by substituting <*> for f in the above definition, (<*>) (<*>) is \g x -> x <*> g x. Or after alpha-conversion \g h -> h <*> g h.

Since the first argument of (<*>) is h, is must be of type h :: f (a -> b) for some a and b, where f is in Applicative.

Since g receives h as an argument, it must be of type g :: f (a -> b) -> c, for some c.

Since the first argument of (<*>), h, has type f (a -> b) and the second argument of (<*>) is g h, its type must be g h :: f a, due to the fact, that

(<*>) :: f (a -> b) -> f a -> f b

Since g :: f (a -> b) -> c and g h :: f a,

h :: f (a -> b)
g :: f (a -> b) -> c
g h :: f a               ,  c ~ f a   (!)

Since h has type f (a -> b), h <*> (whatever :: f a) has type f b.

And altogether:

h         :: f (a -> b)
g         :: f (a -> b) -> f a
h <*> g h :: f b

So we have

\g h -> h <*> g h :: (f (a -> b) -> f a) -> f (a -> b) -> f b
Will Ness
  • 70,110
  • 9
  • 98
  • 181
effectfully
  • 12,325
  • 2
  • 17
  • 40
  • Thanks for sharing another route to this question, it 's inspiring. Meanwhile, I want to clarify one point in your answer. You start by picking the instance ((->) a) for applicative class, I am not sure how you conclude and select that instance to start with. Could you enlighten me on that? Thanks – gatek Dec 23 '14 at 10:21
  • @gatek, shortly, `(<*>)` is applied to `(<*>)`, and the latter is a function, so you can choose an instance, that corresponds to functions, without any minding. Or you can read `f (a -> b) -> f a -> f b` as `(->) (f (a -> b)) (f a -> f b)`. – effectfully Dec 23 '14 at 11:14
  • thanks for your quick reply. I appreciate that. I wish I could accept multiple answers here as I think you have demonstrate an interesting alternative to solve my problem. Merry Christmas – gatek Dec 24 '14 at 05:20
4

As an exercise, narrowing it to functions, where <*> is just an S-combinator,

Prelude> let s f g x = f x (g x)

Prelude> :t s s
s s :: ((t -> t1 -> t2) -> t -> t1) -> (t -> t1 -> t2) -> t -> t2
--               g2          g4                 g2          g1
--         g3                             g3
--                      g5
--                                  g6

It is important to know that arrows in types associate to the right, so ((t -> t1 -> t2) -> t -> t1) is actually ((t -> t1 -> t2) -> (t -> t1)), and (t -> t1 -> t2) is (t -> (t1 -> t2)).

The implementation:

g6 g5 g3 t :: t2 
  g3 t t1 :: t2          -- need t1
  g5 g3 t :: t1
  g3 t (g5 g3 t) :: t2   -- so, 

h f g x = g x (f g x)

So, when we have a type, it's just a matter of connecting the wires so to speak, or putting the Lego bricks together. We try and see which combinations of the given entities (arguments) have what type, and use them in further combinations if they are useful to get to the desired output type (t2, above).

Similarly,

Prelude Control.Applicative> :t (<*>) (<*>)
(<*>) (<*>) :: (Applicative f) =>
               (f (a -> b) -> f a) -> f (a -> b) -> f b
--                         f          fg
Prelude Control.Applicative> :t let axa f fg = fg <*> f fg in axa
let axa f fg = fg <*> (f fg) in axa :: (Applicative f) =>
                                       (f (a -> b) -> f a) -> f (a -> b) -> f b
Will Ness
  • 70,110
  • 9
  • 98
  • 181
  • thanks for your extra inspiration, I came across several time on various posts in SO on combinators but I can never pick it up. Are there any article/blog/material you could recommend for learning combinators? – gatek Dec 23 '14 at 10:34
  • [Wikipedia](https://en.wikipedia.org/wiki/SKI_combinator_calculus) (and its linked articles) is good. As for a book, for me it was [Davie](http://books.google.com/books/about/Introduction_to_Functional_Programming_S.html?id=OPFoJZeI8MEC&redir_esc=y). – Will Ness Dec 23 '14 at 10:35
  • combinatory notation is actually much easier to manipulate than lambda-expressions, imo. Haskell follows the combinatory style. :) – Will Ness Dec 23 '14 at 10:47
  • thanks for the pointers, I'd take a look of them. I like your combinatory approach too and I will try to pick it up too. Merry Christmas. – gatek Dec 24 '14 at 05:16
3

So we have the function

(<*>) :: Applicative f => f (a -> b) -> f a -> f b

and apply to it <*> :: Applicative g => g (c -> d) -> g c -> g d (I replaced type variables because the have different meaning in inner and outer <*> of (<*>)(<*>). If we applied second <*> to the first <*>, then the second <*> must be of type f (a -> b). So we have following equation on types:

g (c -> d) -> g c -> g d = f (a -> b)

But g (c -> d) -> g c -> g d is a syntactic sugar for (->) (g (c -> d)) (g c -> g d). So:

(->) (g (c -> d)) (g c -> g d) = f (a -> b)

Both type constructors and parameter types of both sides must be equal, so:

(->) (g (c -> d)) = f

and

(g c -> g d) = (a -> b)

which means that a = g c and b = g d.

Now we can see that the return value of the first (<*>) is 

f a -> f b = ((->) (g (c -> d)) (g c)) -> ((->) (g (c -> d)) (g d))
           = (g (c -> d) -> g c) -> (g (c -> d) -> g d)

which is the same as (f (a -> b) -> f a) -> f (a -> b) -> f b modulo renaming variables.

The tricky part in this example is that (->) (g (c -> d)) is Applicative (same as any other (->) e).

Michal Seweryn
  • 363
  • 2
  • 8