[Haskell-beginners] question on types

[Daniel Seidel]

On Fri, 2011-07-29 at 07:27 -0400, Jake Penton wrote:
> On 2011-07-29, at 6:54 AM, Gary Klindt wrote:
> 
> > So, why is it possible to work with the map :: (a -> b) -> [a] -> [b] function? One can use it with list of number and functions on numbers, can't one.
> > 
> 
> Yeah. Your question is pretty much an example of what what troubling me in my original post. And frankly, I doubt that my reasoning on this will get straightened out until I have studied the type system more thoroughly.
> 
> Naively, the difference I see between your example using map and my original post is that I was *defining*  f:
> 
> f::a
> f = 1
> 
> which, I suppose, is quite a bit different than *calling* map. To parallel my example, one would (mistakenly) write something like this:
> 
> map::(a -> b)  -> [a] ->  [b]
> map f lst = ['a','b','c']
> 
> The above gives the same message I got. It is tempting to think that " ['a','b','c'] is a list of b's, so it should work", but that is clearly wrong.

Maybe it helps to read the type signatures with explicit type
abstraction and instantiation.

f :: a 

means

f :: forall a. a

that is, I can choose any type for a, and f will have that type.
Let us make the choice explict: say if I use f in  "hello" ++ f, f will
be of type String, we can write f_{String} :: String, if I use it in
(5 :: Int) + f, it will be an Int, ie. f_{Int} :: Int, and so on. So f
must be typable to every type we can instantiate it with.

Now consider map. Here the thing different from f is, that type
variables occur not only on output positions, but also on input
positions of the function, ie. (a -> b) and [a] are at input positions.
And the type instantiation of map gets fixed by the inputs.
If we apply map to a function g :: Char -> Int, the concrete
instantiation of map is already fixed, we have to choose Int for a and
Char for b, ie apply

map_{Char, Int} :: (Char -> Int) -> [Char] -> [Int]

to g. Otherwise the program can't be typed.
In particular, that means that map g only takes lists with characters as
further argument and returns lists with integers.
What happens in your definition above is that you fix b already to
[Char] by your fixed output, so the map above can only be typed to

map :: forall a. (a -> b) -> [a] -> [Char]

Its maybe interesting to think about what functions of polymorphic type
can do. map for example is vastly  described by its type.
The type says it takes an arbitrary function mapping from a to b and a
list of elements of type a to return elements of type b.
Since map does not "know" what types a and b will be when it is called,
it can only apply f to values of type a to generate values of type b (or
use undefined).

For example

map f [] 

can only return a list with entries undefined, or f undefined.

Cheers,

Daniel.
> 
> - j -
> _______________________________________________
> Beginners mailing list
> Beginners at haskell.org
> http://www.haskell.org/mailman/listinfo/beginners