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@haskell.org http://www.haskell.org/mailman/listinfo/beginners