Discussion: Allow custom constraint for elem in Foldable

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
9 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Discussion: Allow custom constraint for elem in Foldable

David Feuer
The Foldable class offers the method

  elem :: Eq a => a -> t a -> Bool

Unfortunately, this is really awful for sets, hash maps, etc. See
https://stackoverflow.com/questions/45361801/implement-an-olog-n-foldable-elem-for-binary-search-trees-in-haskell#45362110
for an example. We could fix it, kinda:

class Foldable t where
  type ElemConstr t :: * -> Constraint
  type ElemConstr t = Eq

  elem :: ElemConstr t a => a -> t a -> Bool
  default elem :: (ElemConstr t ~ Eq, Eq a) => a -> t a -> Bool

One might legitimately complain that such a wild type is ad hoc, but
one might counter that complaint by saying that most of Foldable is
already ad hoc.

David
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Discussion: Allow custom constraint for elem in Foldable

Eric Mertens
I would prefer to see designs for something like this explored in a separate package before we worried about changing base’s Foldable class.

> On Jul 27, 2017, at 3:45 PM, David Feuer <[hidden email]> wrote:
>
> The Foldable class offers the method
>
>  elem :: Eq a => a -> t a -> Bool
>
> Unfortunately, this is really awful for sets, hash maps, etc. See
> https://stackoverflow.com/questions/45361801/implement-an-olog-n-foldable-elem-for-binary-search-trees-in-haskell#45362110
> for an example. We could fix it, kinda:
>
> class Foldable t where
>  type ElemConstr t :: * -> Constraint
>  type ElemConstr t = Eq
>
>  elem :: ElemConstr t a => a -> t a -> Bool
>  default elem :: (ElemConstr t ~ Eq, Eq a) => a -> t a -> Bool
>
> One might legitimately complain that such a wild type is ad hoc, but
> one might counter that complaint by saying that most of Foldable is
> already ad hoc.
>
> David
> _______________________________________________
> Libraries mailing list
> [hidden email]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Discussion: Allow custom constraint for elem in Foldable

Niklas Hambüchen
In reply to this post by David Feuer
On 28/07/17 00:45, David Feuer wrote:
> Unfortunately, this is really awful for sets, hash maps, etc.
If this is done at some point, I suppose we could fix `nub` in the same way?
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Discussion: Allow custom constraint for elem in Foldable

David Feuer
In reply to this post by Eric Mertens
What would that exploration look like in your view? Could you sketch a path?

On Jul 27, 2017 7:35 PM, "Eric Mertens" <[hidden email]> wrote:
I would prefer to see designs for something like this explored in a separate package before we worried about changing base’s Foldable class.

> On Jul 27, 2017, at 3:45 PM, David Feuer <[hidden email]> wrote:
>
> The Foldable class offers the method
>
>  elem :: Eq a => a -> t a -> Bool
>
> Unfortunately, this is really awful for sets, hash maps, etc. See
> https://stackoverflow.com/questions/45361801/implement-an-olog-n-foldable-elem-for-binary-search-trees-in-haskell#45362110
> for an example. We could fix it, kinda:
>
> class Foldable t where
>  type ElemConstr t :: * -> Constraint
>  type ElemConstr t = Eq
>
>  elem :: ElemConstr t a => a -> t a -> Bool
>  default elem :: (ElemConstr t ~ Eq, Eq a) => a -> t a -> Bool
>
> One might legitimately complain that such a wild type is ad hoc, but
> one might counter that complaint by saying that most of Foldable is
> already ad hoc.
>
> David
> _______________________________________________
> Libraries mailing list
> [hidden email]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

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


_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Discussion: Allow custom constraint for elem in Foldable

Ivan Lazar Miljenovic
In reply to this post by Niklas Hambüchen
On 28 July 2017 at 09:37, Niklas Hambüchen <[hidden email]> wrote:
> On 28/07/17 00:45, David Feuer wrote:
>> Unfortunately, this is really awful for sets, hash maps, etc.
> If this is done at some point, I suppose we could fix `nub` in the same way?

I'd prefer we have a "needs only Eq" function like nub, as I've used
it in the past.

--
Ivan Lazar Miljenovic
[hidden email]
http://IvanMiljenovic.wordpress.com
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Discussion: Allow custom constraint for elem in Foldable

Carter Schonwald
In reply to this post by Eric Mertens
agreed.

this needs to be tested out in a user space lib first.


On Thu, Jul 27, 2017 at 7:35 PM, Eric Mertens <[hidden email]> wrote:
I would prefer to see designs for something like this explored in a separate package before we worried about changing base’s Foldable class.

> On Jul 27, 2017, at 3:45 PM, David Feuer <[hidden email]> wrote:
>
> The Foldable class offers the method
>
>  elem :: Eq a => a -> t a -> Bool
>
> Unfortunately, this is really awful for sets, hash maps, etc. See
> https://stackoverflow.com/questions/45361801/implement-an-olog-n-foldable-elem-for-binary-search-trees-in-haskell#45362110
> for an example. We could fix it, kinda:
>
> class Foldable t where
>  type ElemConstr t :: * -> Constraint
>  type ElemConstr t = Eq
>
>  elem :: ElemConstr t a => a -> t a -> Bool
>  default elem :: (ElemConstr t ~ Eq, Eq a) => a -> t a -> Bool
>
> One might legitimately complain that such a wild type is ad hoc, but
> one might counter that complaint by saying that most of Foldable is
> already ad hoc.
>
> David
> _______________________________________________
> Libraries mailing list
> [hidden email]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

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


_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Discussion: Allow custom constraint for elem in Foldable

Carter Schonwald
i wasnt aware of such guidelines for the libraries list

constrained monads/ functors are still an area of study / experimentation, they need experimentation and more community knowledge before they land in base for core type classes

On Thu, Jul 27, 2017 at 8:37 PM, David Feuer <[hidden email]> wrote:
Off-list: Repeating what Eric Mertens said does not contribute to the discussion. Perhaps you can offer an answer to my follow-up question to him.

On Jul 27, 2017 8:26 PM, "Carter Schonwald" <[hidden email]> wrote:
agreed.

this needs to be tested out in a user space lib first.


On Thu, Jul 27, 2017 at 7:35 PM, Eric Mertens <[hidden email]> wrote:
I would prefer to see designs for something like this explored in a separate package before we worried about changing base’s Foldable class.

> On Jul 27, 2017, at 3:45 PM, David Feuer <[hidden email]> wrote:
>
> The Foldable class offers the method
>
>  elem :: Eq a => a -> t a -> Bool
>
> Unfortunately, this is really awful for sets, hash maps, etc. See
> https://stackoverflow.com/questions/45361801/implement-an-olog-n-foldable-elem-for-binary-search-trees-in-haskell#45362110
> for an example. We could fix it, kinda:
>
> class Foldable t where
>  type ElemConstr t :: * -> Constraint
>  type ElemConstr t = Eq
>
>  elem :: ElemConstr t a => a -> t a -> Bool
>  default elem :: (ElemConstr t ~ Eq, Eq a) => a -> t a -> Bool
>
> One might legitimately complain that such a wild type is ad hoc, but
> one might counter that complaint by saying that most of Foldable is
> already ad hoc.
>
> David
> _______________________________________________
> Libraries mailing list
> [hidden email]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

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


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



_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Discussion: Allow custom constraint for elem in Foldable

Edward Kmett-2
In reply to this post by David Feuer
On Thu, Jul 27, 2017 at 6:45 PM, David Feuer <[hidden email]> wrote:
One might legitimately complain that such a wild type is ad hoc, but
one might counter that complaint by saying that most of Foldable is
already ad hoc.
 
My feelings largely echo Eric's in this regard.

Ultimately, the difference is that the rest of Foldable exists in a form that can be standardized as part of Haskell' without requiring us to be able to describe how type families, equality constraints, constraint kinds, and default signatures work and also standardize them. The last one of which being something that I'd say we really don't want in the language standard as it causes all sorts of contortions about where you put code by virtue of information flowing the wrong way, and all of which are highly ghc specific. 

Moreover, it interacts with non-trivial awkwardness with many of the more complicated existing Foldable instances, e.g. Product, Sum, or really, almost anybody else's Foldable instance that glues together more than one 'f' pretty much then has to override this member.

I'm pretty strongly -1 on changing `elem` in this manner.

-Edward

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Discussion: Allow custom constraint for elem in Foldable

Henning Thielemann
In reply to this post by David Feuer

On Thu, 27 Jul 2017, David Feuer wrote:

> The Foldable class offers the method
>
>  elem :: Eq a => a -> t a -> Bool
>
> Unfortunately, this is really awful for sets, hash maps, etc. See
> https://stackoverflow.com/questions/45361801/implement-an-olog-n-foldable-elem-for-binary-search-trees-in-haskell#45362110
> for an example.

I'd prefer to keep Foldable Haskell-98. You may introduce methods with
advanced types in a sub-class.

I also think that the Set type does not perfectly fit to Foldable. Most
Set methods require Ord constraint, but Set.toList does not. Only this
allows to have instance Foldable Set. This looks to me like an
implementation detail. E.g. for Vector.Storable this trick does not work.
You cannot omit the Storable constraint in Vector.toList.
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Loading...