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
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
