[Haskell-cafe] principle types

[Big Chris]

Hi Vikrant,

The other two have said basically the same thing as me, but your
description of map's type makes me think maybe an explanation of
curried functions is in order:

   map is what's called a curried function.  Basically, the type:

   (a -> b) -> [a] -> [b]

   has two interpretations.  The first is the one you gave, which is a
good way to think about the function when you intend to apply it to
both its arguments at once.  However, there is another way to think
about the function as well.  Consider that the type implicitly has
parenthesis like this:

    (a -> b) -> ([a] -> [b])

That is, we can also think of map as a function which takes a function
from a to b, and returns a function from [a] to [b].  In some sense, if
we only provide map with its first argument, then it is still "waiting"
to take the [a] argument, so it becomes a function from [a] to [b].

If we think of may this way, we can see that when it is passed
to itself, its type must be matched against the type of its first
argument.  I'll rename the type variables to make things a little
clearer - what we have to do is unify:

        (c -> d) -> ([c] -> [d])
and       a     ->     b


So in this case, when map returns a function from [a] -> [b], you
get a function from [c -> d] to [[c] -> [d]].  I hope this helps!

--Chris Casinghino

On Wed, 14 Mar 2007, Vikrant wrote:

> Hi,
>  I can understand why principle type of map is
>
> map :: (a -> b) -> [a] -> [b] ,
> I would interpret this as "map takes a function of type a->b and a list of
> type [a] as arguments and returns a list of type [b]"
>
> but it is going somewhat beyond my imagination why principle type of map map
> is
>
> (map map)::[a -> b] -> [[a] -> [b]]
>
> I am able to interpret the expressions "[a -> b] -> [[a] -> [b]]"
> vaguely...
>
> does this mean that 'map map' takes list of functions of type (a->b) and
> returns list of functions of type ([a]->[b])
> if yes ..how do I derive it from basic type declaration of map?
>
> Thanks in advance
> Vikrant
>