[Haskell-cafe] Restricted type classes

[David Menendez]

On Thu, Sep 9, 2010 at 11:33 PM, wren ng thornton <wren at 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 <dave at zednenem.com>
<http://www.eyrie.org/~zednenem/>