[Haskell-beginners] Functor instance for ordered lists

[martin]

Am 01/04/2016 um 03:53 PM schrieb Imants Cekusins:
>> is it impossible to write a functor instance for ordered lists?
> 
> is such specialized functor instance necessary?
> 
> I mean, why not fmap over unconstrained list and init OrdList before
> passing it to a fun where sorted list is really essential?
> 
> this would eliminate the need to maintain sorted order at every step
> in list processing.
> 
> This way, OrdList type would ensure that sort-critical consumer fun
> gets a sorted list, and every other fun - fmap or not - would not
> care.

I see.

The reason why I am asking is I tried to model a predicate on nested items and I came up with this:

data Product a = Prod (a -> Maybe (Product a)) | Pany

The idea was that given an Item a, a Product would return Nothing if the toplevel Item (the "container") does not
statisfy the predicate. Otherwise it returns Just a new Product which captures the condition which each of the contained
items must satisfy.

That alone did not buy me much, particularly becuase I needed a way to "show" a product. So I needed a showable data
structure, which can be used like a Product, i.e. which can be converted into a Product. I came up with

data  MP a = MPacked  (M.Map a (MP a)) | MPany deriving (Show)

Then I tried to define a Functor instance and failed for the afforementioned reasons: a Map needs Ord keys. I found this
puzzling because a Functor on Product makes perfect sense to me.

I assume, this is because M.Map is implemented in such a way, that Ord a is required. Had I used a List of Pairs instead
of a Map, then no Ord constraint would have been required.

Does this make some sense?