map and fmap

[John Hughes]

From: "Jeffrey Yasskin" <jyasskin at google.com>

> On 8/20/06, John Hughes <rjmh at cs.chalmers.se> wrote:
>>
>> From: "Jon Fairbairn" <jon.fairbairn at cl.cam.ac.uk>
>>
>> > To
>> > reinforce what Aaron said, if a programme works now, it'll
>> > still work if map suddenly means fmap.
>>
>> Well, this isn't quite true, is it? Here's an example:
>>
>> class Foldable f where
>>   fold :: (a -> a -> a) -> a -> f a -> a
>>
>> instance Foldable [] where
>>   fold = foldr
>>
>> example = fold (+) 0 (map (+1) (return 2))
>>
>> example has the value 3 (of course), but if you replace map by fmap then 
>> the
>> code no longer compiles.
>
> There's a proposal
> http://hackage.haskell.org/trac/haskell-prime/wiki/Defaulting that
> mentions extending defaulting to other typeclasses. That seems to fix
> this particular problem, but above you mentioned that this was "a
> whole new can of worms." Could you elaborate or point me to a
> discussion of the worms?
>

Well, that proposal doesn't cover exporting defaults from modules. If 
beginners are not to need to write a default declaration in their own 
module, then we would need either to import the right default from the 
Prelude, or to have a default default for Monad and Functor, just as we have 
for numeric classes today. Importing defaults raises questions over how and 
when one can override an imported default with a different default within 
one's own module.

The big problem with extended defaulting, though, is ambiguity. The proposal 
above includes an example:

default A (Int, String, ())
default B (String, Int, ())

suggesting that a type in both classes should be defaulted to (), because 
this is the "first unambiguous type". That isn't a formal definition, and I 
actually have difficulty conceiving of a formal definition that would lead 
to this result. Even given such a thing, it would have very odd 
consequences: presumably if the first line read default A (Int,()), then Int 
would now be the first unambiguous type, and thus the chosen default. That 
means that removing a default *that was not chosen* would change the 
behaviour of the program! I wouldn't like to have to explain THAT to 
anybody!

But this simple example of ambiguity is really the least worm in the can. 
What about subclassing? Presumably a class default should also apply to its 
subclasses... yet at times, we certainly want to override a previous default 
in a subclass (e.g. Num and Floating). How should defaulting interact with 
context reduction? Imagine a default C (String), and an instance definition 
instance C a => C [a]. If we see a C [b], should we apply the detault at 
once, instantiating b to Char, or after context reduction, instantiating b 
to String? How should defaulting interact with functional dependencies? 
Given a bidirectional fundep class C a b | a->b, b->a, then defaults on a 
and b separately can conflict. Worms!

Paul Hudak and I thought about this when Haskell was first designed. We did 
come up with a proposal, but the rest of the committee thought it was too 
complex for what it bought us, hence it was omitted. Nowadays the class 
system is a lot more complicated than it was then--constructor classes, 
multi-parameter classes, fundeps--and I'm not terribly hopeful about the 
prospects for coming up with a simple and powerful design for defaulting.

John