Functor instance for ordered lists

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
12 messages Options
Reply | Threaded
Open this post in threaded view
|

Functor instance for ordered lists

Martin Drautzburg
Hello all,

Data.List.Ordered is just a bunch of functions operating on ordinary Lists. Fmapping a function over an ordered list has
the potential of blowing the ordering.

Would it be possible to define a newtype for ordered lists where the order is guaranteed to be maintained? The functor
instance then may have to re-order the elements.

The problem I see is that

data Ordlist a = ...

would certainly require an Ord constraint on a, but where would I put it? I can put it on all the functions manipulating
OrdLists, but I still wouldn't know how to define a functor instance, because a Functor a does not require Ord a.
_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: Functor instance for ordered lists

Imants Cekusins
> a newtype for ordered lists

why not:
newtype Ordlist a = Ordlist [a]

and a ctor:
ordList::[a]->OrdList a
ordList = OrdList . sort

sort :: Ord a => [a] -> [a]
from Data.List
_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: Functor instance for ordered lists

Martin Drautzburg
Am 01/04/2016 um 11:45 AM schrieb Imants Cekusins:
>> a newtype for ordered lists
>
> why not:
> newtype Ordlist a = Ordlist [a]

All nice and dandy, but at first you already need an Ord constraint for your smart constructor

-- and a ctor:
ordList::(Ord a) => [a]-> OrdList a
ordList = OrdList . sort

but this is still not the main problem. When you try to define a Functor instance, you'd be tempted to do this (at least
I was):

instance Functor OrdList where
        fmap f (OrdList xs) = OrdList $ sort $ map f xs

but you can't do this, because of: "No instance for (Ord b) arising from a use of ‘sort’", where b is the return type of
f :: (a->b). This does make sense, the function has to return something which can be sorted.

So my question is: is it impossible to write a functor instance for ordered lists? It appears so, because a Functor does
not impose any constraints of f. But my knowledge is quite limited and maybe a well-set class constraint can fix things.


_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: Functor instance for ordered lists

Benjamin Edwards
It is impossible.

You can make a new functor class using contraint kinds that allows what you want. There is probably a package out there already that does!


Sections 2.2 and 5.1 have the relevant stuff. I realise this is a bit err, dense for the beginners list. There are probably better references out there.

Ben

On Mon, 4 Jan 2016 at 14:30 martin <[hidden email]> wrote:
Am 01/04/2016 um 11:45 AM schrieb Imants Cekusins:
>> a newtype for ordered lists
>
> why not:
> newtype Ordlist a = Ordlist [a]

All nice and dandy, but at first you already need an Ord constraint for your smart constructor

-- and a ctor:
ordList::(Ord a) => [a]-> OrdList a
ordList = OrdList . sort

but this is still not the main problem. When you try to define a Functor instance, you'd be tempted to do this (at least
I was):

instance Functor OrdList where
        fmap f (OrdList xs) = OrdList $ sort $ map f xs

but you can't do this, because of: "No instance for (Ord b) arising from a use of ‘sort’", where b is the return type of
f :: (a->b). This does make sense, the function has to return something which can be sorted.

So my question is: is it impossible to write a functor instance for ordered lists? It appears so, because a Functor does
not impose any constraints of f. But my knowledge is quite limited and maybe a well-set class constraint can fix things.


_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners

_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: Functor instance for ordered lists

Benjamin Edwards

On Mon, 4 Jan 2016 at 14:46 Benjamin Edwards <[hidden email]> wrote:
It is impossible.

You can make a new functor class using contraint kinds that allows what you want. There is probably a package out there already that does!


Sections 2.2 and 5.1 have the relevant stuff. I realise this is a bit err, dense for the beginners list. There are probably better references out there.

Ben

On Mon, 4 Jan 2016 at 14:30 martin <[hidden email]> wrote:
Am 01/04/2016 um 11:45 AM schrieb Imants Cekusins:
>> a newtype for ordered lists
>
> why not:
> newtype Ordlist a = Ordlist [a]

All nice and dandy, but at first you already need an Ord constraint for your smart constructor

-- and a ctor:
ordList::(Ord a) => [a]-> OrdList a
ordList = OrdList . sort

but this is still not the main problem. When you try to define a Functor instance, you'd be tempted to do this (at least
I was):

instance Functor OrdList where
        fmap f (OrdList xs) = OrdList $ sort $ map f xs

but you can't do this, because of: "No instance for (Ord b) arising from a use of ‘sort’", where b is the return type of
f :: (a->b). This does make sense, the function has to return something which can be sorted.

So my question is: is it impossible to write a functor instance for ordered lists? It appears so, because a Functor does
not impose any constraints of f. But my knowledge is quite limited and maybe a well-set class constraint can fix things.


_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners

_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: Functor instance for ordered lists

Imants Cekusins
In reply to this post by Martin Drautzburg
> 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.
_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: Functor instance for ordered lists

Imants Cekusins
In reply to this post by Martin Drautzburg
> Functor does not impose any constraints of f.

it seems so. I ran into this too. not that i wrote many functor
instances but I could not figure out how to add (any kind of)
constraint to a functor.

Ben already wrote about this  - if I understand him correctly.
_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: Functor instance for ordered lists

Martin Drautzburg
In reply to this post by Imants Cekusins
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?


_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: Functor instance for ordered lists

Marcin Mrotek
In reply to this post by Martin Drautzburg
> would certainly require an Ord constraint on a, but where would I put it? I can put it on all the functions manipulating
> OrdLists, but I still wouldn't know how to define a functor instance, because a Functor a does not require Ord a.

It's of questionable utility, as it still doesn't let you define a
Functor instance (and can no longer be a newtype), but if you want,
you can use a GADT:

data OrdList a where
   OrdList :: Ord a => a -> OrdList a

Best regards
Marcin Mrotek
_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: Functor instance for ordered lists

Imants Cekusins

Is predicate a function specific to each product, used to compose product? 

Or is it used when querying products to filter them?

I'd define data structures as records, sometimes with a couple variable types. Then if variable types are used, define classes to query, modify data.

Why not define product as
data Prod a c = Prod a [c]

where a is product info and c is child item data.

Then define predicate class.

Then define a's and c's separately for each use case. Maybe add types for each specific product.

Then add instances.

This way future changes will be easy. It is easier to work on specifics when generics are simple. Specific products may be as complex as necessary.

If you define product as a complex type with a few type variables, changes will be more difficult.


_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: Functor instance for ordered lists

Martin Drautzburg
Am 01/04/2016 um 10:11 PM schrieb Imants Cekusins:


> Why not define product as
> data Prod a c = Prod a [c]
>
> where a is product info and c is child item data.

Well first the Product is not necessarily a single "thing". There can be various a's which satisfy the criteria to fall
into a specific Product. So either a must be a set-like thing or a function a->Bool.

Then there is not necessarily just one level of nesting. The c's can still be containers, and it matters what's inside
them. It's like a carton of iPhones, which has iPhone packages inside and each iPhone package consists of an iPhone, a
Charger, a Manual and ... and the Charger consists of a Cable, a circuit board ...

If any of the conditions are not met, if e.g. you receive a carton of iPhones where one charger lacks its cable, you
have reason to complain.

_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: Functor instance for ordered lists

Imants Cekusins

a and c can be anything: function, algebraic type, ...

That's the thing. Prod a [c] leaves plenty of room.


_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners