20 June 2013

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
}
}
``````

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.