Specifying Function Argument by Type

Question

I'm sure this is pretty obvious, but bear with me, I'm new to this stuff and it's not clicking. So I've, like many other people, been trying to get my head around Monads. I've gotten to the point where I'm comfortable with the >>= and return operators and so forth. But I feel like I won't really understand it until I get behind it and do some writing myself.

Consequently, I've been playing with trying to implement the bind >>= operator for the List as a composition of map and foldr. For example, [5,6,7,8] >>= (\x -> [x*5, x*6, x*7]) yields [25,30,35,30,36,42,35,42,49,40,48,56]. This looks a lot like the composition of a map and a fold. But if I try something like foldr (++) [] . map I get the obvious type error that map doesn't have type [a] -> [[a]] as expected. Of course, if I instead use something like map (\x -> [x*5, x*6, x*7]) as the right argument to the composition operator it all works.

But it would be a hassle to specify a specific function every time; somehow the >>= operator behaves in a more general fashion. Is there a way to specify an argument by its type? Like, can I somehow tell map to only take functions of the type a -> [a] in this composition? Do I need to write a function that has type (a -> [a]) -> [a] -> [[a]] from scratch because there isn't really a way to narrow the map function to the type of function I want?

Also, please feel free to tell me I'm approaching this all wrong. I am still pretty new to this type of stuff. If so, please point me in the right direction though.

J. Abrahamson J. Abrahamson · Accepted Answer · 2014-10-08T02:58:38

If you check the type of something like

> :t \f -> foldr (++) [] . map f

in GHCi as I did above you'll notice something interesting

\f -> foldr (++) [] . map f :: (a -> [b]) -> [a] -> [b]

Or, to cut to the chase, it turns out that the input function f already and naturally has the more restricted type you asked for. Why is this the case?

Let's examine foldr (++) [] which is more naturally called concat

concat :: [[a]] -> [a]
concat = foldr (++) []

we see that its input must be that of a list of lists. If we consider what that means in the context of post composition with map

concat           ::        [[c]] -> [c]
       . map f   :: [a] -> [ b ]          -- for (f :: a -> b)

we can see that b must be the same as [c] for some type c. In other words, information about the use of the result of mapping f, e.g. its passage through concat, has flowed backwards to specialize the information we know about map and even its argument f.

So, unifying b and [c] above we see that map must have a slightly more restrictive type

map ::* (a -> [c]) -> [a] -> [[c]]

where I write (::*) to indicate that this is a specialization of map's natural type carried out naturally by unification with the type of concat.

Specifying Function Argument by Type

1 Answers