containers: intersections for Set, along with Semigroup newtype

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

containers: intersections for Set, along with Semigroup newtype

Reed Mullanix
Hey all,

I've found myself reaching for the following function a couple of times now, so I figured it might make a good addition.

  intersections :: Ord a => NonEmpty (Set a) -> Set a
  intersections (s :| ss) = Foldable.foldl' intersection s ss

In a similar vein, we may as well add the following newtype + instance combo:

  newtype Intersection a = Intersection { getIntersection :: Set a }

  instance (Ord a) => Semigroup (Intersection a) where
      (Intersection a) <> (Intersection b) = Intersection $ intersection a b
      stimes = stimesIdempotent

Would love to hear everyone's thoughts on this!

Thanks
Reed Mullanix

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

Re: containers: intersections for Set, along with Semigroup newtype

Georgi Lyubenov
+1 from me

Seems like additional motivation for adding NonEmptyFoldable (or however people want to call it)

=======
Georgi

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

Re: containers: intersections for Set, along with Semigroup newtype

Emily Pillmore
Makes sense to me. 


On Sun, Dec 06, 2020 at 2:40 AM, Georgi Lyubenov <[hidden email]> wrote:
+1 from me

Seems like additional motivation for adding NonEmptyFoldable (or however people want to call it)

=======
Georgi

_______________________________________________
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
|

RE: containers: intersections for Set, along with Semigroup newtype

Alexandre Rodrigues Baldé
In reply to this post by Reed Mullanix

Sounds like a good idea, could it be possible to use a typeclass instead of `NonEmpty (Set a)`?

I recall needing this a few times, but not over a NonEmpty.

 

De: Libraries <[hidden email]> em nome de Reed Mullanix <[hidden email]>
Enviado: Sunday, December 6, 2020 6:20:02 AM
Para: Haskell Libraries <[hidden email]>
Assunto: containers: intersections for Set, along with Semigroup newtype

 

Hey all,

I've found myself reaching for the following function a couple of times now, so I figured it might make a good addition.

 

  intersections :: Ord a => NonEmpty (Set a) -> Set a
  intersections (s :| ss) = Foldable.foldl' intersection s ss

 

In a similar vein, we may as well add the following newtype + instance combo:

 

  newtype Intersection a = Intersection { getIntersection :: Set a }

 

  instance (Ord a) => Semigroup (Intersection a) where
      (Intersection a) <> (Intersection b) = Intersection $ intersection a b
      stimes = stimesIdempotent

 

Would love to hear everyone's thoughts on this!

Thanks

Reed Mullanix


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

Re: containers: intersections for Set, along with Semigroup newtype

Reed Mullanix
In a perfect world we would use something like Foldable1 from semigroupoids, but sadly that is not in base.
However, this is exactly why I proposed the Intersection newtype, as it would make it nice and easy to use with a Foldable1
like type class.

On Sun, Dec 6, 2020 at 10:27 AM Alexandre Rodrigues Baldé <[hidden email]> wrote:

Sounds like a good idea, could it be possible to use a typeclass instead of `NonEmpty (Set a)`?

I recall needing this a few times, but not over a NonEmpty.

 

De: Libraries <[hidden email]> em nome de Reed Mullanix <[hidden email]>
Enviado: Sunday, December 6, 2020 6:20:02 AM
Para: Haskell Libraries <[hidden email]>
Assunto: containers: intersections for Set, along with Semigroup newtype

 

Hey all,

I've found myself reaching for the following function a couple of times now, so I figured it might make a good addition.

 

  intersections :: Ord a => NonEmpty (Set a) -> Set a
  intersections (s :| ss) = Foldable.foldl' intersection s ss

 

In a similar vein, we may as well add the following newtype + instance combo:

 

  newtype Intersection a = Intersection { getIntersection :: Set a }

 

  instance (Ord a) => Semigroup (Intersection a) where
      (Intersection a) <> (Intersection b) = Intersection $ intersection a b
      stimes = stimesIdempotent

 

Would love to hear everyone's thoughts on this!

Thanks

Reed Mullanix


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

Re: containers: intersections for Set, along with Semigroup newtype

Sven Panne-2
In reply to this post by Reed Mullanix
Am So., 6. Dez. 2020 um 07:20 Uhr schrieb Reed Mullanix <[hidden email]>:
[...]
  intersections :: Ord a => NonEmpty (Set a) -> Set a
  intersections (s :| ss) = Foldable.foldl' intersection s ss
[...]

Why NonEmpty? I would expect "intersections [] = Set.empty", because the result contains all the elements which are in all sets, i.e. none. That's at least my intuition, is there some law which this would violate? 

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

Re: containers: intersections for Set, along with Semigroup newtype

Reed Mullanix
It doesn't violate any laws per say, due to the general lawlessness of Foldable, but violates aesthetics. If we restrict it to NonEmpty then we get a lovely semigroup homomorphism!
If we loosen it to lists, then the identity element of the list monoid gets mapped to an absorbing element in the Set semigroup under intersection, which just feels... off.

On Sun, Dec 6, 2020 at 10:50 AM Sven Panne <[hidden email]> wrote:
Am So., 6. Dez. 2020 um 07:20 Uhr schrieb Reed Mullanix <[hidden email]>:
[...]
  intersections :: Ord a => NonEmpty (Set a) -> Set a
  intersections (s :| ss) = Foldable.foldl' intersection s ss
[...]

Why NonEmpty? I would expect "intersections [] = Set.empty", because the result contains all the elements which are in all sets, i.e. none. That's at least my intuition, is there some law which this would violate? 

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

Re: containers: intersections for Set, along with Semigroup newtype

Eric Mertens
In reply to this post by Sven Panne-2
First consider how `and` and `or` work for booleans.


and (x ++ y) == and x && and y

For this to work we need `and [] == True`

or (x ++ y) == or x || or y

For this to work we need `or [] == False`

and and or are duals of each other.


There’s an analogue here to union and intersection which are also duals of each other.

We have: unions (x ++ y) == union (unions x) (unions y)

This requires `union [] == []` since any list xs could be split as `[] ++ xs`

We'd like to have: intersections (x ++ y) == intersect (intersections x) (intersections y)

For this kind of splitting property to make sense for intersections we’d need `intersections [] == listOfAllElementsOfThisType`, but it’s not easy to construct that list of all elements in general.
So instead we punt on the problem and refuse to define intersections on an empty list.

-glguy

On Dec 6, 2020, at 10:50 AM, Sven Panne <[hidden email]> wrote:

Am So., 6. Dez. 2020 um 07:20 Uhr schrieb Reed Mullanix <[hidden email]>:
[...]
  intersections :: Ord a => NonEmpty (Set a) -> Set a
  intersections (s :| ss) = Foldable.foldl' intersection s ss
[...]

Why NonEmpty? I would expect "intersections [] = Set.empty", because the result contains all the elements which are in all sets, i.e. none. That's at least my intuition, is there some law which this would violate? 
_______________________________________________
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
|

Re: containers: intersections for Set, along with Semigroup newtype

Sven Panne-2
In reply to this post by Reed Mullanix
Am So., 6. Dez. 2020 um 19:56 Uhr schrieb Reed Mullanix <[hidden email]>:
It doesn't violate any laws per say, due to the general lawlessness of Foldable, but violates aesthetics. [...]

To me it's just the other way around: It violates aesthetics if it doesn't follow the mathematical definition in all cases, which is why I don't like NonEmpty here.

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

Re: containers: intersections for Set, along with Semigroup newtype

Georgi Lyubenov
In reply to this post by Sven Panne-2
I would be opposed to
intersections [] = []
as it is true that *all* things have the property of being a member of every element of []. In set theory without classes I've usually seen this worked around by never using intersections on an empty set (ie using NonEmpty)

=======
Georgi

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

Re: containers: intersections for Set, along with Semigroup newtype

David Feuer
In reply to this post by Sven Panne-2
intersections [] = empty is unacceptable to me. The options that make sense to me are the nonempty (ideally Foldable1) one, one producing a Maybe, and I guess even one that throws an error on an empty list (ouch).

On Sun, Dec 6, 2020, 1:50 PM Sven Panne <[hidden email]> wrote:
Am So., 6. Dez. 2020 um 07:20 Uhr schrieb Reed Mullanix <[hidden email]>:
[...]
  intersections :: Ord a => NonEmpty (Set a) -> Set a
  intersections (s :| ss) = Foldable.foldl' intersection s ss
[...]

Why NonEmpty? I would expect "intersections [] = Set.empty", because the result contains all the elements which are in all sets, i.e. none. That's at least my intuition, is there some law which this would violate? 
_______________________________________________
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
|

Re: containers: intersections for Set, along with Semigroup newtype

David Casperson
In reply to this post by Sven Panne-2
Intersection is a lattice operation, whose identity element is the "whole
universe" not the empty set.

Imagine if we had an intersections :: [Set a] -> Set a

we would expect it have the law
    intersections (a ++ b) = (intersections a) `intersect` (intersections b)

now let b be [] and aa == intersections a, and we get
     aa == aa `intersect` (intersections [])
and this must hold for all aa, which is impossible unless we have some
kind of universe set.

David
--
David Casperson, PhD, R.P.,                  |  [hidden email]
Associate Professor and Chair,               |  (250)   960-6672 Fax 960-5544
Computer Science                             |  3333 University Way
University of Northern British Columbia      |  Prince George, BC   V2N 4Z9
                                              |  CANADA

Sven Panne, on 2020-12-06, you wrote:

> From: Sven Panne <[hidden email]>
> To: Reed Mullanix <[hidden email]>
> Date: Sun, 6 Dec 2020 10:50:13
> Cc: Haskell Libraries <[hidden email]>
> Subject: Re: containers: intersections for Set, along with Semigroup newtype
> Message-ID:
>     <CANBN=muqE8tE11UCGgYYuUEKP=SN19TAQ7_3wE68v46583H-=[hidden email]>
>
>
> CAUTION: This email is not from UNBC. Avoid links and attachments. Don't buy gift cards.
>
> Am So., 6. Dez. 2020 um 07:20 Uhr schrieb Reed Mullanix <[hidden email]>:
>       [...]
>   intersections :: Ord a => NonEmpty (Set a) -> Set a
>   intersections (s :| ss) = Foldable.foldl' intersection s ss
> [...]
>
>
> Why NonEmpty? I would expect "intersections [] = Set.empty", because the result contains all the elements which are
> in all sets, i.e. none. That's at least my intuition, is there some law which this would violate?
>
>
_______________________________________________
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
|

Re: containers: intersections for Set, along with Semigroup newtype

Henning Thielemann
In reply to this post by Reed Mullanix

On Sun, 6 Dec 2020, Reed Mullanix wrote:

> In a perfect world we would use something like Foldable1 from
> semigroupoids, but sadly that is not in base.

Is it necessary to have it in base for your use? For me, 'NonEmpty.foldl1
Set.intersection' is perfect.
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: containers: intersections for Set, along with Semigroup newtype

David Feuer
That implementation doesn't short-circuit if the accumulator goes empty. It also relies on the optimizer to accumulate strictly.

On Mon, Dec 7, 2020, 3:44 AM Henning Thielemann <[hidden email]> wrote:

On Sun, 6 Dec 2020, Reed Mullanix wrote:

> In a perfect world we would use something like Foldable1 from
> semigroupoids, but sadly that is not in base.

Is it necessary to have it in base for your use? For me, 'NonEmpty.foldl1
Set.intersection' is perfect.
_______________________________________________
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
|

Re: containers: intersections for Set, along with Semigroup newtype

Ben Franksen
In reply to this post by Sven Panne-2
Am 06.12.20 um 19:58 schrieb Sven Panne:
> To me it's just the other way around: It violates aesthetics if it doesn't
> follow the mathematical definition in all cases, which is why I don't like
> NonEmpty here.

I think you've got that wrong.

  x `elem` intersections []
= {definition}
  forall xs in []. x `elem` xs
= {vacuous forall}
  true

Any proposition P(x) is true for all x in []. So the mathematical
definition of intersections::[Set a]-> Set a would not be the empty set
but the set of all x:a, which in general we have no way to construct.

Cheers
Ben

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

Re: containers: intersections for Set, along with Semigroup newtype

Tom Ellis-5
On Sun, Dec 20, 2020 at 11:05:39PM +0100, Ben Franksen wrote:

> Am 06.12.20 um 19:58 schrieb Sven Panne:
> > To me it's just the other way around: It violates aesthetics if it doesn't
> > follow the mathematical definition in all cases, which is why I don't like
> > NonEmpty here.
>
> I think you've got that wrong.
>
>   x `elem` intersections []
> = {definition}
>   forall xs in []. x `elem` xs
> = {vacuous forall}
>   true
>
> Any proposition P(x) is true for all x in []. So the mathematical
> definition of intersections::[Set a]-> Set a would not be the empty set
> but the set of all x:a, which in general we have no way to construct.

Yes, and to bring this back to Sven's original claim

| Why NonEmpty? I would expect "intersections [] = Set.empty", because
| the result contains all the elements which are in all sets,
| i.e. none. That's at least my intuition, is there some law which
| this would violate?

the correct definition of "intersections []" should be "all elements
which are in all of no sets" i.e. _every_ value of the given type!

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

Re: containers: intersections for Set, along with Semigroup newtype

David Feuer
One *could* write

  import Data.Universe.Class (Finite (..))

  class (Ord a, Finite a) => OrderedFinite a where
    orderedFiniteUniverse :: Set a
    orderedFiniteUniverse = S.fromList universeF

  data SMaybe a = SJust !a | SNothing

  wackyIntersections :: OrderedFinite a => [Set a] -> Set a
  wackyIntersections = \ss -> foldr go stop ss SNothing
    where
      stop SNothing = orderedFiniteUniverse
      stop (SJust s) = s

      go s r SNothing = r (SJust s)
      go s r (SJust acc)
        | null acc = empty
        | otherwise = r (SJust acc `intersection` s)

No such things will be going in `containers`, but perhaps they would
fit in `universe`.

On Mon, Dec 21, 2020 at 5:12 AM Tom Ellis
<[hidden email]> wrote:

>
> On Sun, Dec 20, 2020 at 11:05:39PM +0100, Ben Franksen wrote:
> > Am 06.12.20 um 19:58 schrieb Sven Panne:
> > > To me it's just the other way around: It violates aesthetics if it doesn't
> > > follow the mathematical definition in all cases, which is why I don't like
> > > NonEmpty here.
> >
> > I think you've got that wrong.
> >
> >   x `elem` intersections []
> > = {definition}
> >   forall xs in []. x `elem` xs
> > = {vacuous forall}
> >   true
> >
> > Any proposition P(x) is true for all x in []. So the mathematical
> > definition of intersections::[Set a]-> Set a would not be the empty set
> > but the set of all x:a, which in general we have no way to construct.
>
> Yes, and to bring this back to Sven's original claim
>
> | Why NonEmpty? I would expect "intersections [] = Set.empty", because
> | the result contains all the elements which are in all sets,
> | i.e. none. That's at least my intuition, is there some law which
> | this would violate?
>
> the correct definition of "intersections []" should be "all elements
> which are in all of no sets" i.e. _every_ value of the given type!
>
> Tom
> _______________________________________________
> 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
|

Re: containers: intersections for Set, along with Semigroup newtype

Carter Schonwald
In reply to this post by Tom Ellis-5
why are we equating the lattice operators for True and false with the lattice operators for set? (for both structures, we have the dual partial order is also a lattice, so unless we have )
(i'm going to get the names of these equations wrong, but )

the "identity" law is going to be  max `intersect` y == y ,  min `union` y === y

the "absorbing" law is going to be   min `intersect` y == min , max `union` y == max

these rules work the same for (min = emptyset, max == full set, union == set union, intersect == set intersecct)
OR for its dual lattice (min == full set, max == emtpy set, union = set intersection, intersect == set union)

at some level arguing about the empty list case turns into artifacts of "simple" definitions

that said, i suppose a case could be made that for intersect :: [a] -> a , that as the list argument gets larger the result should be getting *smaller*, so list intersect of lattice elements should be "anti-monotone", and list union should be monotone (the result gets bigger). I dont usually see tht

either way, I do strongly feel that either way, arguing by how we choose to relate the boolean lattice and seet lattices is perhaps the wrong choice... because both lattices are equivalent to theeir dual lattice

On Mon, Dec 21, 2020 at 5:12 AM Tom Ellis <[hidden email]> wrote:
On Sun, Dec 20, 2020 at 11:05:39PM +0100, Ben Franksen wrote:
> Am 06.12.20 um 19:58 schrieb Sven Panne:
> > To me it's just the other way around: It violates aesthetics if it doesn't
> > follow the mathematical definition in all cases, which is why I don't like
> > NonEmpty here.
>
> I think you've got that wrong.
>
>   x `elem` intersections []
> = {definition}
>   forall xs in []. x `elem` xs
> = {vacuous forall}
>   true
>
> Any proposition P(x) is true for all x in []. So the mathematical
> definition of intersections::[Set a]-> Set a would not be the empty set
> but the set of all x:a, which in general we have no way to construct.

Yes, and to bring this back to Sven's original claim

| Why NonEmpty? I would expect "intersections [] = Set.empty", because
| the result contains all the elements which are in all sets,
| i.e. none. That's at least my intuition, is there some law which
| this would violate?

the correct definition of "intersections []" should be "all elements
which are in all of no sets" i.e. _every_ value of the given type!

Tom
_______________________________________________
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
|

Re: containers: intersections for Set, along with Semigroup newtype

Carter Schonwald
edit: neglected to mention that choosing which lattice (and or dual) to use only really matters when considering products/sums of lattices to form new lattices

On Mon, Dec 21, 2020 at 11:12 AM Carter Schonwald <[hidden email]> wrote:
why are we equating the lattice operators for True and false with the lattice operators for set? (for both structures, we have the dual partial order is also a lattice, so unless we have )
(i'm going to get the names of these equations wrong, but )

the "identity" law is going to be  max `intersect` y == y ,  min `union` y === y

the "absorbing" law is going to be   min `intersect` y == min , max `union` y == max

these rules work the same for (min = emptyset, max == full set, union == set union, intersect == set intersecct)
OR for its dual lattice (min == full set, max == emtpy set, union = set intersection, intersect == set union)

at some level arguing about the empty list case turns into artifacts of "simple" definitions

that said, i suppose a case could be made that for intersect :: [a] -> a , that as the list argument gets larger the result should be getting *smaller*, so list intersect of lattice elements should be "anti-monotone", and list union should be monotone (the result gets bigger). I dont usually see tht

either way, I do strongly feel that either way, arguing by how we choose to relate the boolean lattice and seet lattices is perhaps the wrong choice... because both lattices are equivalent to theeir dual lattice

On Mon, Dec 21, 2020 at 5:12 AM Tom Ellis <[hidden email]> wrote:
On Sun, Dec 20, 2020 at 11:05:39PM +0100, Ben Franksen wrote:
> Am 06.12.20 um 19:58 schrieb Sven Panne:
> > To me it's just the other way around: It violates aesthetics if it doesn't
> > follow the mathematical definition in all cases, which is why I don't like
> > NonEmpty here.
>
> I think you've got that wrong.
>
>   x `elem` intersections []
> = {definition}
>   forall xs in []. x `elem` xs
> = {vacuous forall}
>   true
>
> Any proposition P(x) is true for all x in []. So the mathematical
> definition of intersections::[Set a]-> Set a would not be the empty set
> but the set of all x:a, which in general we have no way to construct.

Yes, and to bring this back to Sven's original claim

| Why NonEmpty? I would expect "intersections [] = Set.empty", because
| the result contains all the elements which are in all sets,
| i.e. none. That's at least my intuition, is there some law which
| this would violate?

the correct definition of "intersections []" should be "all elements
which are in all of no sets" i.e. _every_ value of the given type!

Tom
_______________________________________________
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
|

type class Boolean

Ben Franksen
All this talk about lattices reminds me of one of my pet gripes I have
with the standard libraries (base), namely that the boolean operators
aren't overloaded. I don't want to open endless discussions about the
perfect generalization, because there are lots of valid generalizations
and the lattice package is fine for those.

But most generalizations don't have a 'not' (complement) operator. So, a
simple type class Boolean with instances for Bool and functions
returning Booleans should cover the majority of use cases; more
instances could be added of course. Something like

{-# LANGUAGE NoImplicitPrelude #-}
module Data.Boolean where

import Prelude hiding ((&&),(||),not)
import qualified Prelude

infixr 3 &&
infixr 2 ||

class Boolean a where
  -- laws: that of a boolean algebra, i.e.
  -- complemented distributive lattice, see
  -- https://en.wikipedia.org/wiki/Boolean_algebra#Laws
  (&&) :: a -> a -> a
  (||) :: a -> a -> a
  not :: a -> a
  top :: a
  bottom :: a

instance Boolean Bool where
  (&&) = (Prelude.&&)
  (||) = (Prelude.||)
  not = Prelude.not
  top = True
  bottom = False

instance Boolean b => Boolean (a->b) where
  (f && g) x = f x && g x
  (f || g) x = f x || g x
  (not f) x = not (f x)
  top = const top
  bottom = const bottom

IMHO this would be absolutely benign, no problems with type inference,
fully Haskell98, no breakage of existing code I can think of. (I didn't
check that last point but I would be very surprised if there were.)

Cheers
Ben

Am 21.12.20 um 17:14 schrieb Carter Schonwald:

> edit: neglected to mention that choosing which lattice (and or dual) to use
> only really matters when considering products/sums of lattices to form new
> lattices
>
> On Mon, Dec 21, 2020 at 11:12 AM Carter Schonwald <
> [hidden email]> wrote:
>
>> why are we equating the lattice operators for True and false with the
>> lattice operators for set? (for both structures, we have the dual partial
>> order is also a lattice, so unless we have )
>> (i'm going to get the names of these equations wrong, but )
>>
>> the "identity" law is going to be  max `intersect` y == y ,  min `union` y
>> === y
>>
>> the "absorbing" law is going to be   min `intersect` y == min , max
>> `union` y == max
>>
>> these rules work the same for (min = emptyset, max == full set, union ==
>> set union, intersect == set intersecct)
>> OR for its dual lattice (min == full set, max == emtpy set, union = set
>> intersection, intersect == set union)
>>
>> at some level arguing about the empty list case turns into artifacts of
>> "simple" definitions
>>
>> that said, i suppose a case could be made that for intersect :: [a] -> a ,
>> that as the list argument gets larger the result should be getting
>> *smaller*, so list intersect of lattice elements should be "anti-monotone",
>> and list union should be monotone (the result gets bigger). I dont usually
>> see tht
>>
>> either way, I do strongly feel that either way, arguing by how we choose
>> to relate the boolean lattice and seet lattices is perhaps the wrong
>> choice... because both lattices are equivalent to theeir dual lattice
>>
>> On Mon, Dec 21, 2020 at 5:12 AM Tom Ellis <
>> [hidden email]> wrote:
>>
>>> On Sun, Dec 20, 2020 at 11:05:39PM +0100, Ben Franksen wrote:
>>>> Am 06.12.20 um 19:58 schrieb Sven Panne:
>>>>> To me it's just the other way around: It violates aesthetics if it
>>> doesn't
>>>>> follow the mathematical definition in all cases, which is why I don't
>>> like
>>>>> NonEmpty here.
>>>>
>>>> I think you've got that wrong.
>>>>
>>>>   x `elem` intersections []
>>>> = {definition}
>>>>   forall xs in []. x `elem` xs
>>>> = {vacuous forall}
>>>>   true
>>>>
>>>> Any proposition P(x) is true for all x in []. So the mathematical
>>>> definition of intersections::[Set a]-> Set a would not be the empty set
>>>> but the set of all x:a, which in general we have no way to construct.
>>>
>>> Yes, and to bring this back to Sven's original claim
>>>
>>> | Why NonEmpty? I would expect "intersections [] = Set.empty", because
>>> | the result contains all the elements which are in all sets,
>>> | i.e. none. That's at least my intuition, is there some law which
>>> | this would violate?
>>>
>>> the correct definition of "intersections []" should be "all elements
>>> which are in all of no sets" i.e. _every_ value of the given type!
>>>
>>> Tom
>>> _______________________________________________
>>> 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
12