Le 27 sept. 08 à 15:24, Andrew Coppin a écrit :
David Menendez wrote:
I wouldn't say that. It's important to remember that Haskell class
Monad does not, and can not, represent *all* monads, only (strong)
monads built on a functor from the category of Haskell types and
functions to itself.
Data.Set is a functor from the category of Haskell types *with
decidable ordering* and *order-preserving* functions to itself.
That's
not the same category, although it is closely related.
I nominate this post for the September 2008 Most Incomprehensible
Cafe Post award! :-D
Seriously, that sounded like gibberish. (But then, you're talking to
somebody who can't figure out the difference between a set and a
class, so...)
All I know is that sometimes I write stuff in the list monad when
the result really ought to be *sets*, not lists, because
1. there is no senamically important ordering
2. there should be no duplicates
But Haskell's type system forbids me. (It also forbids me from
making Set into a Functor, actually... so no fmap for you!)
Think about it this way: fmap is supposed to be an homomorphism on the
functor's structure, it just changes the type of the holes in the
structure. To implement such map function in Set (not debating if Set
should require Ord or not here!) and keep the structure invariants,
the function you give to map should be order-preserving. Actually,
Set.map accepts any function but it must construct the new Set using a
fold behind the scenes because otherwise the function may break the
internal balancing invariants. But map_monotonous is there for the
case where it does respect the orders and the map can be done much
more naturally and efficiently.
There's simply no way to state that a function must be monotonous
using haskell's limited type system. except by using a new datatype
that represents only the order-preserving functions between any two
types A and B (is that even possible?). So you only see the [Ord]
constraint getting in the way of defining a functor on Sets, but it's
more profound than that, the functions themselves don't fit exactly.
Otherwise, to implement Sets correctly I think you need at least [Eq]
(and give [Eq] preserving functions to fmap).
You can certainly declare a new EqFunctor (f : * -> *) where eqfmap :
Eq a, Eq b => (a -> b) -> f a -> f b and assume that functions are
[Eq]-preserving there (similarly with [Ord]).
Hope this helps,
-- Matthieu_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe