[Haskell-cafe] The container problem
Matthieu Sozeau
sozeau at lri.fr
Sat Sep 27 09:53:04 EDT 2008
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
More information about the Haskell-Cafe
mailing list