[Haskell-cafe] Restricted type classes

[wren ng thornton]

On 9/10/10 12:47 AM, David Menendez wrote:
> It seems like you could use a similar argument to show that fmap id /= id.
>
> Specifically, xs and map id xs are equivalent lists, but they occupy
> different locations in memory. By replacing xs with map id xs, you can
> come arbitrarily close to doubling a program's memory requirements.
> (You can also use pointer comparison to distinguish them, but I assume
> that doesn't count.)

That doesn't really follow. The Haskell values and types do not capture 
heap transformations, so those don't count for the same reason that 
pointer equality doesn't count.

The fmap id = id law only needs to apply at each use site, not 
necessarily when doing whole-program analysis. Given any list xs, it is 
indeed true that the result of (fmap id xs) is equal to the result of 
(id xs). They even take up the same amount of space after full 
evaluation. The only difference is that the latter avoids some extra 
allocation and garbage collection and preserves sharing, none of which 
is captured by the type system. Indeed, that's why we'd like to know the 
laws hold, so that we can rewrite occurences of (fmap id) with id; just 
as we'd like to replace (fmap f . fmap g) by fmap(f.g) since it improves 
time performance by only performing a single traversal. Time is also not 
captured by the type system. Technically we could rewrite programs in 
the other direction and introduce new fmaps, we just have no reason to 
do so.

However, in the example I gave, the actual values (E (f a) a) and (E (f 
a) (f a)) are not equal even when ignoring time, space, and sharing. 
They may be *isomorphic* because they have the same observable behavior 
within the language (assuming no polymorphic seq or heap-size 
reflection), but they are not *equal*. Your comments about increasing 
total-program allocation just points out that (fmap id) and id are not 
*identical*--- which we know already. But even if they cannot be 
identical, they must be equal if the fmap instance is lawfully a 
functor. The notions of being identical, equal, isomorphic, and 
equivalent are all quite different. I was only using the size of their 
heap representation as evidence for the non-equality of these two terms 
in spite of their isomorphism.

-- 
Live well,
~wren