Home » forums » LtU Forum

type derivation for 'map map', yelp

*newbie alert* I'm hoping this is a permissible question to ask here. I looked at the FAQ and it doesn't seem to explicitly disallow it. :)

[haskell]
I was learning haskell a few years ago and I was recommended mr. Hudak's book "The Haskell School of Expression". This was my first foray into functional programming and it turned out this wasn't a great book to start with. Having done some amount of Haskelling by now I regret to realize that when I see an expression like "map map" I continue to scratch my head. Hudak gives this and similar examples as exercises, but there are no solutions in the back of the book.

The funny thing is that I've written map map to map a function over items in lists contained in a list. But I still don't understand this at all:
map map :: [a -> b] -> [[a] -> [b]]
Let alone how you derive it.
[/haskell]

By numerodix at 2008-08-22 11:00 | LtU Forum | previous forum topic | next forum topic | other blogs | 9869 reads

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Not appropriate

This is not an appropriate question for LtU. If you have Haskell-specific questions then the Haskell mailinglists (haskell-cafe@haskell.org or beginners@haskell.org), the Haskell IRC channel (#haskell on freenode.net), or the Haskell newsgroup (comp.lang.haskell) are the places to ask.

By Derek Elkins at Fri, 2008-08-22 12:28 | login or register to post comments

Maybe off-topic, but not inappropriate

I'm ambivalent whether this is off-topic or not, but it certainly is not inappropriate.

I hope LtU can maintain quality discussions and avoid becoming a "Slashdot for Programming Languages", but I also hope we can do this without being too intimidating to newcomers.

But yes, the aforementioned forums would be a better venue for this kind of question.

By Leon P Smith at Fri, 2008-08-22 18:36 | login or register to post comments

I agree. The OP is welcome

I agree. The OP is welcome to hang around, and ask question. The topic in general is ok for LtU. The current question, however, is rather specific and a Haskell mailing list or discussion group would be more appropriate. If anyone has general observation that are relevant, feel free to post them.

By Ehud Lamm at Fri, 2008-08-22 19:22 | login or register to post comments

Map applies a function of

Map applies a function of one argument to a list of items. 

double n = n*2
map double [x,y,z] => [double x, double y, double z]

But map isn't a one argument function: it takes two arguments. So what happens if you apply map to one argument? map double returns a function that doubles all numbers in a list.

double_all = map double
double_all [1,2,3] => [2,4,6]

Instead of thinking of map as taking a function and a list, try to think of it as a function transformer. map fn transforms the function fn to work on lists. double doubles a number; map double doubles a list of numbers.

map transforms a function; map map transforms a list of functions. So map takes a function (type a -> b) and transforms the function to operate on lists (type [a] -> [b]). map map is a function that takes a list of functions [a -> b] and returns a list of transformed functions [[a] -> [b]].

I hope this helps.

It's also possible to derive the type by syntactic transformations and substitutions like the Haskell implementation, but that doesn't teach you as much about the function.

By Jules Jacobs at Fri, 2008-08-22 12:43 | login or register to post comments

Algebraically speaking...

The type of map is represented as map :: (a -> b) -> [a] -> [b]. You could think of this as a 2-argument function or, thanks to currying, think of it as a function taking one function argument and returning another. You should recognize that the function operator (->) is right-associative, so if you add some extra parentheses for clarity, you get map :: (a -> b) -> ([a] -> [b]).

Suppose you had a place in code requiring some vague polymorphic function of type c -> d. Now, knowing what you learned above, you can see how map can be substituted in this location. (a -> b) generalizes to c, and ([a] -> [b]) generalizes to d.

It turns out the map is itself such a function that takes an argument of type c -> d (or use your favorite two different type variables). The rest is just algebraic substitution.

Suppose we have these two functions (for the sake of argument and clarity):

map :: (c -> d) -> ([c] -> [d])
map' :: (a -> b) -> ([a] -> [b])

Let's write map map'. First, we substitute (a -> b) for c. Then, we substitute ([a] -> [b]) for d. Lastly, we remove the first argument, because it has already been applied (it is map' after all).

(0) map :: (c -> d) -> ([c] -> [d])
(1) map :: ((a -> b) -> d) -> ([a -> b] -> [d])
(2) map :: ((a -> b) -> ([a] -> [b])) -> ([a -> b] -> [([a] -> [b])])
(3) map map' :: [a -> b] -> [[a] -> [b]]

Of course, really map == map'. And that's it!

By Sean Leather at Fri, 2008-08-22 20:07 | login or register to post comments