On Thu, Sep 9, 2010 at 11:33 PM, wren ng thornton <w...@freegeek.org> wrote: > On 9/9/10 1:04 AM, David Menendez wrote: >> >> Fascinating. I figured there might be a counter-example involving seq, >> but this is pretty subtle. >> >> In particular, would it be fair to say that in Haskell-without-seq, "E >> (f a) a" and "E (f a) (f a)" are indistinguishable? > > Yes, I think that without polymorphic seq (or within a strict language) they > are observationally equivalent. But, observational equivalence is not the > same as equality. And the category theoretic laws really do mean equality. > > To pick an example: consider the case where 'a' is an enormous data > structure and (f a) returns some small value. Even though (E (f a) a) and (E > (f a) (f a)) are observationally equivalent within Haskell, they're still > observationally distinct from outside of the language because they have very > different memory profiles. (We may need to make E strict in the second > argument, or NOINLINE impure, in order to guarantee this behavior.) Thus, > the equality still fails, though this may go undetected for a long time > until someone notices the memory leak.
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.) What about Set.map? We have forall s. Set.map id s == s, but the actual structure may not be identical. In principle, there's no way to observe the difference, but in practice you can do it by breaking the precondition on foldMap. Does that mean we can't consider Set.Set/Set.map a functor over the subcategory of ordered Haskell types? -- Dave Menendez <d...@zednenem.com> <http://www.eyrie.org/~zednenem/> _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe