Well, map is of type (a->b) -> [a] -> [b]. Applying precedence rules gives (a->b) -> ([a]->[b]). That is, map takes a function from a to b and returns a function that takes a list of a and returns a list of b. So if we are applying map to a map, then... Well, let's start by using a' and b' for the outer call to map. Then a' must be of the form (a->b) and b' must be of the form ([a]->[b]). Which means that the outer map must have a type of ((a->b)->([a]->[b]) -> [a->b] -> [[a]->[b]]. That must be the answer. So I pull up GHCi and take peek at :t map map and it brings me back to earth:
[a->b] -> [[a]->[b]]
Hmm. Let's try this again, bottom up this time. What's map map xs going to look like? Well, we know that xs better be a list, so map map [a, b, c] will be [map a, map b, map c]. So our xs are mappable functions; for example, map map [(<3),(<4),(<5)]. This gives us [map (<3), map(<4), map (<5)]. This is a list of functions, each of which takes a list of Num and returns a list of Bool.
So where did I go wrong in the first place? Let's take a closer look at the first answer: ((a->b)->([a]->[b]) -> [a->b] -> [[a]->[b]]. The first argument looks suspiciously like the signature for map itself. And [(<3),(<4),(<5)] does indeed look suspiciously like map (<) [3..5]! But the whole expression would then be map map map (<) [3..5]. Or maybe not. Actually it would be map map $ map (<) [3..5], a rather different creature. Mind the dollar sign.
In fact, as a beginning Haskell programmer, I’ve been bitten by function precedence and the $ operator more than anything else. This results in a cryptic type error from the compiler that I’m just beginning to get familiar with. So my advice to others is this: if you are getting an incomprehensible type error message from the compiler, try using parentheses to group your expressions. That will fix many of your problems (and if you have any Lisp experience, those familiar parens are like a gateway drug).
Back to map map, and its type. Looking at the type I derived, and paying attention to the context, it all becomes clear. Because ((a->b)->([a]->[b]) -> [a->b] -> [[a]->[b]] is the type of the outer map, which is known to have map as its first argument. So indeed the type of the outer map in map map is ((a->b)->([a]->[b]) -> [a->b] -> [[a]->[b]], but the type of map map as a whole is [a->b] -> [[a]->[b]]. Or, what GHC said. Duh!
So, map map converts a list of functions which take a single value into a list of functions that take a list?
ReplyDeleteTim: you got it. I'm not seeing this as something I'd want to do very often. Let's think about how we'd use the result.
ReplyDeleteTo apply the result of map map, you'd want a function that is sort of the inverse of map. It would have type [c->d] -> c -> [d]. That is, it would take a list of functions c->d and a single c and return a list of d's. c here is [a] from the original [a->b] that went into map map, and d here is [b]. Let's call this function mapf, because it's mapping a list of functions to a single argument (even though in this case, that "single argument" is a list of a's).
To extend my concrete example, map map [(<3),(<4),(<5)] gives us [map(<3),map(<4),map(<5)]. If this value is x, then mapf x [1,3,5] will return [[True,False,False],[True,True,False],[True,True,False]].