Foldable, Traversable, and parametricity

The Foldable-Traversable proposal (aka FTP) has spawned a lot of debate in the Haskell community.

Here I want to analyze the specific concern which Ben Moseley raised in his post, FTP dangers.

Ben’s general point is that more polymorphic (specifically, ad-hoc polymorphic, i.e. using type classes) functions are less readable and reliable than their monomorphic counterparts.

On the other hand, Tony Morris and Chris Allen argue on twitter that polymorphic functions are more readable due to parametricity.

Is that true, however? Are the ad-hoc generalized functions more parametric than the monomorphic versions?

@shebang @dibblego is (a -> b) -> [a] -> [b] more parametric than Functor f => (a -> b) -> f a -> f b ?

— Je Suis Petit Gâteau (@bitemyapp) February 12, 2015

Technically, the Functor-based type is more parametric. A function with type (a -> b) -> [a] -> [b] is something like map, except it may drop or duplicate some elements. On the other hand, Functor f => (a -> b) -> f a -> f b has to be fmap.

But this is a trick question! The first thing we see in the code is the function’s name, not its type. What carries more information, map or fmap? (Assuming both come from the current Prelude.) Certainly map. When fmap is instantiated at the list type, it is nothing more than map. When we see fmap, we know that it may or may not be map. When we see map, we know it is map and nothing else.

The paradox is that there are more functions with map’s type than fmap’s, but there are more functions with fmap’s name than map’s. Even though fmap is more parametric, that doesn’t win us much.

Nevertheless, is there a benefit in using more parametric functions in your code? No. If it were true, we’d all be pumping our code with «parametricity» by writing id 3 instead of 3. You can’t get more parametric than id.

Merely using parametric functions doesn’t make code better. Parametricity may pay off when we’re defining polymorphic parametric functions in our code instead of their monomorphic instantiations, since parametric types are more constrained and we’re more likely to get a compile error should we do anything stupid.

(It won’t necessarily pay off; the type variables and constraints do impose a tax on types’ readability.)

But if you have an existing, monomorphic piece of code that works with lists, simply replacing Data.List functions with Data.Foldable ones inside it, ceteris paribus, will not make your code any safer or more readable.