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 |
> 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 |
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 |
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: _______________________________________________ Beginners mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners |
This is a bit better: https://dorchard.wordpress.com/2011/10/18/subcategories-in-haskell-exofunctors/ On Mon, 4 Jan 2016 at 14:46 Benjamin Edwards <[hidden email]> wrote:
_______________________________________________ Beginners mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners |
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 |
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 |
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 |
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 |
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 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 |
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 |
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 |
Free forum by Nabble | Edit this page |