[Haskell-cafe] The container problem

[Matthieu Sozeau]

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