ZSet

ZSet is a version of a set that generalizes the measure of "how many times" each element appears in the set.

Conceptually, we can think of a ZSet[A, B] as a Map[A, B], where A represents the elements of the set and B represents some notion of how many times each element appears.

We can then define a Set as a ZSet where the measure of how many times each element appears is a Boolean.

import zio.prelude.ZSet

type Set[+A] = ZSet[A, Boolean]

That is, in a Set the measure of how many times an element appears is just yes or no. Either the element is in the set or it is not.

However, we can also define many other variants of sets by choosing different types to measure how many times an element appears.

For example, by using the Natural new type from ZIO Prelude, which describes integers greater than or equal to zero, we can define the type of a MultiSet or "bag" in some programming languages.

import zio.prelude.ZSet
import zio.prelude.newtypes.Natural

type MultiSet[+A] = ZSet[A, Natural]

This ends up being a quite useful data type and can represent anything where the number of times an element appears matters but the order doesn't matter, such as a shopping cart.

By using other measures of how many times an item appears we can describe other variants of sets such as Int for sets where items can appear a negative number of times or Double for sets where the number of times an item appears can be fractional.

ZSet is focused on using the functional abstractions and new types in ZIO Prelude to describe operators on these generalizations of sets in as practical a way as possible.

Constructing ZSets

The most basic way to construct a ZSet is from a Map where the keys in the map represent the elements in the ZSet and the values in the map represent the number of times each element appears.

val shoppingList: ZSet[String, Int] =
  ZSet.fromMap(Map("apples" -> 2, "oranges" -> 3, "bananas" -> 5))
// shoppingList: ZSet[String, Int] = ZSet(apples -> 2, bananas -> 5, oranges -> 3)

We can also construct a ZSet from existing collection types.

If we have a normal Set from the Scala standard library, we can convert it to a ZSet using the fromSet operator.

val set: ZSet[Int, Boolean] =
  ZSet.fromSet(Set(1, 2, 3))
// set: ZSet[Int, Boolean] = ZSet(1 -> true, 2 -> true, 3 -> true)

If we have an Iterable we can convert it into a ZSet using the fromIterable constructor. The measure of how many times each item appears will just be how many times it appears in the Iterable.

val multiSet: MultiSet[Int] =
 ZSet.fromIterable(List(1, 1, 2))
// multiSet: MultiSet[Int] = ZSet(1 -> 2, 2 -> 1)

Finally, we can just construct an empty ZSet using the empty operator and combine ZSet with other ZSet values later.

val empty: ZSet[Nothing, Nothing] =
  ZSet.empty
// empty: ZSet[Nothing, Nothing] = ZSet()

Operators on ZSets

As a generalization of sets, ZSet supports many of the same operators that exist on sets.

Set Membership

We can determine how many times an element appears in the set using the apply operator. This requires that the measure type has an Identity defined for it.

If the element exists in the set the measure of how many times it appears will be returned. Otherwise the identity element will be returned.

Thus, shoppingList("apples") will return 2 and shoppingList("eggs") will return 0 while set(1) will return true and set(4) will return false.

Set Union

One simple way of combining sets is the union of two sets.

The union of two sets contains all elements that appear in either set. If an element appears in both sets the measure of how many times it appears in the union will be the maximum of the two measures, as determined by an Ord defined on the measure type.

val left: ZSet[Int, Int] =
  ZSet.fromMap(Map(1 -> 2, 2 -> 3, 3 -> 4))
// left: ZSet[Int, Int] = ZSet(1 -> 2, 2 -> 3, 3 -> 4)

val right: ZSet[Int, Int] =
  ZSet.fromMap(Map(2 -> 2, 3 -> 3, 4 -> 4))
// right: ZSet[Int, Int] = ZSet(2 -> 2, 3 -> 3, 4 -> 4)

val union: ZSet[Int, Int] =
  left.union(right)
// union: ZSet[Int, Int] = ZSet(1 -> 2, 2 -> 3, 3 -> 4, 4 -> 4)

Here the result will be ZSet(1 -> 2, 2 -> 3, 3 -> 4, 4 -> 4) because all elements in both sets will be included in the union of the two sets.

Set Intersection

Set intersection is another basic way of combining sets.

The intersection of two sets only contains the elements that appear in both sets. If an element appears in both sets the measure of how many times it appears in the intersection will be the minimum of the two measures, as determined by an Ord defined on the measure type.

val left: ZSet[Int, Int] =
  ZSet.fromMap(Map(1 -> 2, 2 -> 3, 3 -> 4))
// left: ZSet[Int, Int] = ZSet(1 -> 2, 2 -> 3, 3 -> 4)

val right: ZSet[Int, Int] =
  ZSet.fromMap(Map(2 -> 2, 3 -> 3, 4 -> 4))
// right: ZSet[Int, Int] = ZSet(2 -> 2, 3 -> 3, 4 -> 4)

val intersection: ZSet[Int, Int] =
  left.intersect(right)
// intersection: ZSet[Int, Int] = ZSet(2 -> 2, 3 -> 3)

The result will be ZSet(2 -> 2, 3 -> 3) because the only commonality of the two sets is that they contain these elements.

Set Difference

We can also compute the difference of two sets.

The difference of two sets is obtained by subtracting the measure of how many times each element appears in the second set from how many times it appears in the first set. This requires an Inverse defined on the Sum of the measure type to tell us what it means to "subtract" for this type.

val left: ZSet[Int, Int] =
  ZSet.fromMap(Map(1 -> 2, 2 -> 3, 3 -> 4))
// left: ZSet[Int, Int] = ZSet(1 -> 2, 2 -> 3, 3 -> 4)

val right: ZSet[Int, Int] =
  ZSet.fromMap(Map(2 -> 2, 3 -> 3, 4 -> 4))
// right: ZSet[Int, Int] = ZSet(2 -> 2, 3 -> 3, 4 -> 4)

val diff: ZSet[Int, Int] =
  left.diff(right)
// diff: ZSet[Int, Int] = ZSet(1 -> 2, 2 -> 1, 3 -> 1, 4 -> -4)

The result will be ZSet(1 -> 2, 2 -> 1, 3 -> 1, 4 -> -4).

Note that the measure of how many times 4 appears in the resulting set is negative. This is permissible because Int allows negative numbers.

If we didn't want this we could define the measure type to be a type like Natural that did not permit negative numbers.

val left: MultiSet[String] =
  ZSet.fromIterable(List("apple", "banana"))
// left: MultiSet[String] = ZSet(banana -> 1, apple -> 1)

val right: MultiSet[String] =
  ZSet.fromIterable(List("banana", "banana", "banana"))
// right: MultiSet[String] = ZSet(banana -> 3)

val diff: MultiSet[String] =
  left.diff(right)
// diff: MultiSet[String] = ZSet(banana -> 0, apple -> 1)

Now the measure of how many times each item appears is a natural number so "banana" cannot appear a negative number of times.

Set Combination

Another helpful way of combining sets that makes more sense for generalized sets is the notion of "adding" two sets. This is less relevant for traditional sets because an element can never appear more than once in a traditional set, so "adding" reduces to set union.

However, for generalized sets this way of combining can be quite intuitive. For example if we think of a multiset as John's shopping list and another multiset as Jane's shopping list, the combination of the two includes everything on both shopping lists, with overlapping items appearing the total number of times they appear on both lists.

This requires a Commutative defined on the Sum of the measure type to tell us how to do this addition.

val janeShoppingList: ZSet[String, Int] =
  ZSet.fromMap(Map("apples" -> 4, "bananas" -> 5))
// janeShoppingList: ZSet[String, Int] = ZSet(apples -> 4, bananas -> 5)

val johnShoppingList: ZSet[String, Int] =
  ZSet.fromMap(Map("eggs" -> 12, "bananas" -> 1))
// johnShoppingList: ZSet[String, Int] = ZSet(eggs -> 12, bananas -> 1)

val combinedList: ZSet[String, Int] =
  janeShoppingList.combine(johnShoppingList)
// combinedList: ZSet[String, Int] = ZSet(eggs -> 12, apples -> 4, bananas -> 6)

The result is ZSet("apples" -> 4, "bananas" -> 6, "eggs" -> 12), the combination of what each of them wants to buy.

Set Product

We can also define the product of two sets.

This is the Cartesian product of the two sets, with each combination of elements from the two sets appearing in the product set and the measure of how many times an element appears being the product of the two measures. This requires a Commutative defined on the Prod of the measure type to tell us how to do this multiplication.

A nice example of this is modeling discrete probabilities. We can define the set of all possible outcomes of a dice roll along with their associated probabilities like this:

val die: ZSet[Int, Double] =
  ZSet.fromMap(
    Map(
      1 -> 1.0 / 6.0,
      2 -> 1.0 / 6.0,
      3 -> 1.0 / 6.0,
      4 -> 1.0 / 6.0,
      5 -> 1.0 / 6.0,
      6 -> 1.0 / 6.0
    )
  )
// die: ZSet[Int, Double] = ZSet(5 -> 0.16666666666666666, 1 -> 0.16666666666666666, 6 -> 0.16666666666666666, 2 -> 0.16666666666666666, 3 -> 0.16666666666666666, 4 -> 0.16666666666666666)

The product of this set with itself represents the set of all possible outcomes of rolling two dice.

val pair: ZSet[(Int, Int), Double] =
  die.zip(die)
// pair: ZSet[(Int, Int), Double] = ZSet((5,4) -> 0.027777777777777776, (2,6) -> 0.027777777777777776, (4,1) -> 0.027777777777777776, (5,2) -> 0.027777777777777776, (1,1) -> 0.027777777777777776, (1,6) -> 0.027777777777777776, (6,4) -> 0.027777777777777776, (3,2) -> 0.027777777777777776, (3,3) -> 0.027777777777777776, (4,3) -> 0.027777777777777776, (5,6) -> 0.027777777777777776, (2,2) -> 0.027777777777777776, (3,4) -> 0.027777777777777776, (2,1) -> 0.027777777777777776, (6,1) -> 0.027777777777777776, (2,5) -> 0.027777777777777776, (4,2) -> 0.027777777777777776, (4,4) -> 0.027777777777777776, (1,2) -> 0.027777777777777776, (6,5) -> 0.027777777777777776, (6,2) -> 0.027777777777777776, (1,4) -> 0.027777777777777776, (4,5) -> 0.027777777777777776, (4,6) -> 0.027777777777777776, (2,4) -> 0.027777777777777776, (6,3) -> 0.027777777777777776, (1,5) -> 0.027777777777777776, (3,1) -> 0.027777777777777776, (5,1) -> 0.027777777777777776, (3,6) -> 0.027777777777777776, (2,3) -> 0.027777777777777776, (3,5) -> 0.027777777777777776, (1,3) -> 0.027777777777777776, (5,5) -> 0.027777777777777776, (5,3) -> 0.027777777777777776, (6,6) -> 0.027777777777777776)

This set has thirty six elements, corresponding to each possible combination of outcomes from the two dice rolls, each with a probability of one in thirty six.

This gets more interesting if we say that matters is not the individual dice rolls but their sum.

We can express this in code with the zipWith operator, which allows us to combine the elements from the product of the two sets with a function. If multiple elements from the product are mapped to the same value the measures of how many times each value appears will be added, using a Commutative instance defined on the Sum of the measure type.

val sum: ZSet[Int, Double] =
  die.zipWith(die)(_ + _)
// sum: ZSet[Int, Double] = ZSet(5 -> 0.1111111111111111, 10 -> 0.08333333333333333, 6 -> 0.1388888888888889, 9 -> 0.1111111111111111, 2 -> 0.027777777777777776, 12 -> 0.027777777777777776, 7 -> 0.16666666666666669, 3 -> 0.05555555555555555, 11 -> 0.05555555555555555, 8 -> 0.1388888888888889, 4 -> 0.08333333333333333)

The resulting set has eleven elements, corresponding to the possible sums from two dice rolls of two to twelve. The measure for each value corresponds to the probability of that sum being rolled.

So for example the probability of seven is about 16.7% whereas the probability of rolling two or twelve is only about 2.8%.

We can take this even further using the flatMap operator.

The zipWith operator lets us combine two sets when the sets are independent of each other. With the flatMap operator we can create a new set based on each element of the first set and then "flatten" the resulting set down.

We could rewrite the example above using flatMap and a for comprehension like this:

val sum: ZSet[Int, Double] =
  for {
    a <- die
    b <- die
  } yield a + b
// sum: ZSet[Int, Double] = ZSet(5 -> 0.1111111111111111, 10 -> 0.08333333333333333, 6 -> 0.1388888888888889, 9 -> 0.1111111111111111, 2 -> 0.027777777777777776, 12 -> 0.027777777777777776, 7 -> 0.16666666666666669, 3 -> 0.05555555555555555, 11 -> 0.05555555555555555, 8 -> 0.1388888888888889, 4 -> 0.08333333333333333)

This allows us to express conditional logic, such as the probability distribution of outcomes for a subsequent event depending on the outcome of a previous event.

Transforming Elements

We can transform set elements using the map operator.

For example, we could add one to each value in a set like this:

val setPlusOne: ZSet[Int, Boolean] =
  set.map(_ + 1)
// setPlusOne: ZSet[Int, Boolean] = ZSet(2 -> true, 3 -> true, 4 -> true)

This requires a Commutative instance defined for the Sum of the measure type so that we can combine the measures if we map two elements to the same value.

Transforming Measures

We can also transform the measure we use to represent how many times an item appears using the transform operator. For example, perhaps we have constructed a set where the measure is an Int but we would like to transform it to a Double so we can compose it with other ZSet values with Double as the measure type.

We can do that with transform like this:

def constant(n: Int): ZSet[Int, Double] =
  ZSet(n).transform(_.toDouble)

Extracting ZSet Values

If the number of times a value appears in the set is a natural number then we can use normal collection operators to fold over its values, treating it much like a normal set

val fruits: MultiSet[String] =
  ZSet.fromIterable(List("apple", "banana", "orange", "apple", "orange"))
// fruits: MultiSet[String] = ZSet(banana -> 1, orange -> 2, apple -> 2)

val fruitCount: Int =
  fruits.foldLeft(0)((n, _) => n + 1)
// fruitCount: Int = 5

This will return 5 because there are five elements in the set we are folding over.

We can convert a ZSet back to a Map from elements to a measure of how many times they appear using the toMap operator.

We can also always convert a ZSet back to a Set using the toSet operator. Any elements in the ZSet with a measure equal to zero based on an Identity defined on the Sum of the measure type will be discarded from the resulting set.