No subject

identity. But if tested and checked separately it is. Maybe something
weird is going on with (fmap f) and (fmap g) and/or their composition.
Before we dive into that let us try one more example:

ex7 =3D toList $ fmap f . (empty `union`) . fmap g $ fromList xs

print ex7 just like ex6 gives us [X 5 5] should we assume that (empty
`union`) is not identity either? This hints that, probably something
is wrong with (fmap f), (fmap g), or their composition.

Let us check.

If one symbolically evaluates ex4 and ex6 (I did it with pen and paper
and I am too lazy to type it here), one can notice that:

ex4 boils down to evaluating Data.Set.map (f . g) (Data.Set.fromList xs)

while

ex6 boils down to evaluating Data.Set.map f (Data.Set.map g
(Data.Set.fromList xs))

(BTW, is not it great that Data.Set.Monad managed to fuse f and g for ex4)

So for your Eq and Ord instances and f and g functions the following
does not hold for the underlaying Data.Set library:

map f . map g =3D map (f . g)

So putting identity functions like (fromList . toList) or (empty
`union`) prevents the fusion and allows one to observe that (map f .
map g) is not the same  as (map (f . g)) for the underlaying Data.Set
and for your particular choice of f and g.

This violates the second functor law. So does this mean that I (and
few other people [1, 2]) should not have attempted to turn Set into a
functor? I do not think so.

(BTW, what distinguishes the approach used in Data.Set.Monad from
other efforts is that it does not require changes in the definitions
of standard Functor and Monad type classes).

In my opinion, the problem here lies with the Eq and Ord instances of
the X data type AND with the function f that can tell apart two values
that are proclaimed to be equal by the Eq instance. As I said, such
instances and accompanied functions not only break useful properties
of Data.Set.Monad, but also useful properties of the library that
underlies it (i.e., the original Data.Set), and possibly many other
standard libraries and functions (see [4]).

Putting the functor laws aside, there are even more fundamental
set-oriented properties that can be broken by Ord instances that are
not law abiding. See the following GHCi session taken from [3]:

Prelude> import Data.Set
Prelude Data.Set> let x =3D fromList  [0, -1, 0/0, -5, -6, -3] :: Set Float
Prelude Data.Set> member 0 x
True
Prelude Data.Set> let x' =3D insert (0/0) x
Prelude Data.Set> member 0 x'
False

Is this because Data.Set is broken? No, in my opinion, this is because
the Ord instance of Float does not satisfy the Ord laws (about total
order).

To summarise, in my opinion the problem here lies with the fact that
the Eq and Ord instances for the X data type proclaim two values as
equal when it can be easily observed that they are not equal (in this
case with the function f). Note, that the functions of Data.Set.Monad
and Data.Set rely on your Eq and Ord instances.

Of course, there would be nothing wrong with the Eq and Ord instances
for X as long as you would export it as abstract data type and you
would not export functions that can observe two values to be different
when your Eq instance says they are equal. One could also clearly mark
functions that can tell two equal (in the sense of Eq) values apart as
unsafe (perhaps maybe even in the SafeHaskell sense).

The opinions may differ, but I think the raised issue is more about
what the specifications of Eq and Ord should be and what the client
code that uses Eq and Ord instance can assume. There has been a long
discussion on this topic [4].

Again the opinions may differ, but I think in this case the problem
lies with the Eq and Ord instances for the X data type and not with
the Data.Set.Monad and (its underlaying) Data.Set libraries.

Derek and Dan, thanks for the interesting example. I would be
interested to hear whether you have an example that could potentially
break set-oriented, and/or monad and functor laws for element types
where Eq instance respects observational equality and Ord instance
respects total order.

Cheers, George

[1] http://www.haskell.org/pipermail/haskell-cafe/2010-July/080977.html
[2] http://haskell.1045720.n5.nabble.com/Functor-instance-for-Set-td5525789=
.html
[3] http://stackoverflow.com/questions/6399648/what-happens-to-you-if-you-b=
reak-the-monad-laws
[4] http://www.haskell.org/pipermail/haskell-cafe/2008-March/thread.html