A Zipper and Comonad example

There are some software concepts which you hear about and after some time you roughly understand what they are. But you still wonder: "where can I use this?". "Zippers" and "Comonads" are like that. This post will show an example of:

• using a Zipper for a list
• using the Comonad cojoin operation for the Zipper
• using the new specs2 contain matchers to specify collection properties

The context for this example is simply to specify the behaviour of the following function:

def partition[A](seq: Seq[A])(relation: (A, A) => Boolean): Seq[NonEmptyList[A]]

Intuitively we want to partition the sequence seq into groups so that all the elements in a group have "something in common" with at least one other element. Here is a concrete example

val near = (n1: Int, n2: Int) => math.abs(n1 - n2) <= 1
partition(Seq(1, 2, 3, 7, 8, 9))(near)

> List(NonEmptyList(1, 2, 3), NonEmptyList(7, 8, 9))

Properties

If we want to encode this behaviour with ScalaCheck properties we need to check at least 3 things:

1. for each element in a group, there exists at least another related element in the group
2. for each element in a group, there doesn't exist a related element in any other group
3. 2 elements which are not related must end up in different groups

How do we translate this to some nice Scala code?

Contain matchers

"for each element in a group, there exists another related element in the same group"

prop { (list: List[Int], relation: (Int, Int) => Boolean) =>
  val groups = partition(list)(relation)
  groups must contain(relatedElements(relation)).forall
}

The property above uses a random list, a random relation, and does the partitioning into groups. We want to check that all groups satisfy the property relatedElements(relation). This is done by:

• using the contain matcher
• passing it the relatedElements(relation) function to check a given group
• do this check forall groups

The relatedElements(relation) function we pass has type NEL[Int] => MatchResult[NEL[Int]] (type NEL[A] = NonEmptyList[A]) and is testing each group. What does it do? It checks that each element of a group has at least one element that is related to it.

def relatedElements(relation: (Int, Int) => Boolean) = (group: NonEmptyList[Int]) => {
  group.toZipper.cojoin.toStream must contain { zipper: Zipper[Int] =>
    (zipper.lefts ++ zipper.rights) must contain(relation.curried(zipper.focus)).forall
  }
}

This function is probably a bit mysterious so we need to dissect it.

Zipper

In the relatedElements function we need to check each element of a group in relation to the other elements. This means that we need to traverse the sequence, while keeping the context of where we are in the traversal. This is exactly what a Zipper is good at!

A List Zipper is a structure which keeps the focus on one element of the list and can return the elements on the left or the elements on the right. So in the code above we transform the group into a Zipper with the toZipper method. Note that this works because the group is a NonEmptyList. This wouldn't work with a regular List because a Zipper cannot be empty, it needs something to focus on:

// a zipper for [1, 2, 3, 4, 5, 6, 7, 8, 9]
//     lefts      focus    rights
// [  [1, 2, 3]     4      [5, 6, 7, 8, 9]  ]

Now that we have a Zipper that is focusing on the one element of the group. But we don't want to test only one element, we want to test all of them, so we need to get all the possible zippers over the original group!

Cojoin

It turns out that there is a method doing exactly this for Zippers, it is called cojoin. I won't go here into the full explanation of what a Comonad is, but the important points are:

• Zipper has a Comonad instance
• Comonad has a cojoin method with this signature cojoin[A](zipper: Zipper[A]): Zipper[Zipper[A]]

Thanks to cojoin we can create a Zipper of all the Zippers, turn it into a Stream[Zipper[Int]] and do the checks that really matters to us

def relatedElements(relation: (Int, Int) => Boolean) = (group: NonEmptyList[Int]) => {
  group.toZipper.cojoin.toStream must contain { zipper: Zipper[Int] =>
    val otherElements = zipper.lefts ++ zipper.rights
    otherElements must contain(relation.curried(zipper.focus))
  }
}

We get the focus of the Zipper, an element, and we check it is related to at least one other element in that group. This is easy because the Zipper gives us all the other elements on the left and on the right.

Cobind

If you know a little bit about Monads and Comonads you know that there is a dualism between join in Monads and cojoin in Comonads. But there is also one between bind and cobind. Is it possible to use cobind then to implement the relatedElements function? Yes it is, and the result is slightly different (arguably less understandable):

def relatedElements(relation: (Int, Int) => Boolean) = (group: NonEmptyList[Int]) => {
  group.toZipper.cobind { zipper: Zipper[Int] =>
    val otherElements = zipper.lefts ++ zipper.rights
    otherElements must contain(relation.curried(zipper.focus))
  }.toStream must contain((_:MatchResult[_]).isSuccess).forall
}

In this case we cobind each zipper with a function that will check if there are related elements in the groups. This will gives us back a Zipper of results and we need to make sure that it full of success values.

Second property

"for each element in a group, there doesn't exist a related element in another group"

prop { (list: List[Int], relation: (Int, Int) => Boolean) =>
  val groups = partition(list)(relation)
  groups match {
    case Nil          => list must beEmpty
    case head :: tail => nel(head, tail).toZipper.cojoin.toStream must not contain(relatedElementsAcrossGroups(relation))
  }
}

This property applies the same technique but now across groups of elements by creating a Zipper[NonEmptyList[Int]] instead of a Zipper[Int] as before:

def relatedElementsAcrossGroups(relation: (Int, Int) => Boolean) = (groups: Zipper[NonEmptyList[Int]]) =>
  groups.focus.list must contain { e1: Int =>
    val otherGroups = (groups.lefts ++ groups.rights).map(_.list).flatten
    otherGroups must contain(relation.curried(e1))
  }

Note that the ability to "nest" the new specs2 contain matchers is very useful in this situation.

Last property

Finally the last property is much easier because it doesn't require any context to be tested. For this property we just make sure that no element is ever related to another one and check that they end up partitioned into distinct groups.

"2 elements which are not related must end up in different groups"

prop { (list: List[Int]) =>
  val neverRelated = (n1: Int, n2: Int) => false
  val groups = partition(list)(neverRelated)
  groups must have size(list.size)
}

Conclusion

Building an intuition for those crazy concepts is really what counts. For me it was "traversal with a context". Then I was finally able to spot it in my own code.