Add intersections function

[milesfrain]

We have union, unions, and intersection, but no intersections.

I've been using this locally:

intersections :: forall f a. Foldable f => Ord a => f (Set a) -> Set a
intersections sets = case List.fromFoldable sets of
  Nil -> Set.empty
  (x : xs) -> foldl intersection x xs

PR with tests and docs on the todo list.

[hdgarrood]

The only problem with this is that the intersections of an empty list of sets really ought to be a set containing every inhabitant of a, which is not possible without an extra constraint (I think BoundedEnum is enough) but also constructing such a set is probably not something you ever want to do anyway. I think this should have a Foldable1 constraint if we are going to include it here.

[milesfrain]

We can start with a Foldable1 intersections, but I suspect there will be requests for a version that allows an empty list of sets (and returns a more pragmatic empty set in that case). I think many algorithms end up being cleaner with this allowance.

For example, I tried rewriting this Venn diagram code with non-empty intersections, and it ended up turning into a huge mess. Here's the original:
https://try.ps.ai/?gist=6a0fff8192710ab520e9cc1039ddd223
Maybe someone with more FP experience can see a better way to rewrite this with Foldable1.

The simplest fix I found for the above is to simply recreate the desired library function locally:

my_intersections :: forall f a. Foldable f => Ord a => f (Set a) -> Set a
my_intersections sets = case List.fromFoldable sets of
  Nil -> Set.empty
  (x : xs) -> intersections $ NEL.cons' x xs

Also, I was hoping that this would be a valid way to write the Foldable1 version:

intersections :: forall f a. Foldable1 f => Ord a => f (Set a) -> Set a
intersections = foldl1 intersection

But it will not compile because foldl1 is not a member of Foldable1. This is surprising because foldl is a member Foldable. Should Foldable1 be changed to include equivalents of all the Foldable members (foldr, foldl, foldMap)? If not, how would you write this function?

[kl0tl]

Foldable1 has a foldl1 method since purescript/purescript-foldable-traversable#121.

[hdgarrood]

The reason I don’t want to have an intersections function which says that the intersection of an empty list of sets is empty is that properties like intersections (xs <> ys) = intersect (intersections xs) (intersections ys) are the kind of thing you’ll make use of without realising you’re doing so, especially since unions already satisfies a similar property. I’m not currently convinced that lots of algorithms end up being cleaner with the Foldable version of intersections, but I’m open to being persuaded. I don’t see it as too much of a problem if people do end up writing my_intersections functions downstream, because at least they will have had to consciously consider the empty list input that way.

[hdgarrood]

I have to admit I haven’t been able to work out what your vennCell is trying to do.

[milesfrain]

I don’t see it as too much of a problem if people do end up writing my_intersections functions downstream

That sounds good for now. Can always add it to the library later if there's more demand or evidence that it simplifies things.

---

Foldable1 has a foldl1 method since purescript/purescript-foldable-traversable#121.

Thanks. I've been relying too much on Pursuit / Starsuit to answer these questions.

---

I have to admit I haven’t been able to work out what your vennCell is trying to do.

It finds the contents of a "cell" in a venn diagram if provided with which sets to consider ("keep") and exclude ("toss"). For example, given these labeled sets:

"A" [1, 2, 4, 5]
"B" [1, 3, 4, 7]
"C" [1, 2, 3, 6]

which represents this diagram:

If vennCell is given {keep: [A, B], toss: [C]}, it will find [4] and apply the appropriate "A B" label.

Full try-purescript output for that basic input is:

-----
A B C
-----
1

-----
B C
-----
3

-----
A C
-----
2

-----
C
-----
6

-----
A B
-----
4

-----
B
-----
7

-----
A
-----
5

The results are more interesting if each cell contains more than one element, such as in purescript/purescript-lists#183