Scalaz: request for use case for Cokleisli composition

Question

This question isn't meant as flame-bait! As it might be apparent, I've been looking at Scalaz recently. I'm trying to understand why I need some of the functionality that the library provides. Here's something:

import scalaz._
import Scalaz._
type NEL[A] = NonEmptyList[A]
val NEL = NonEmptyList

I put some println statements in my functions to see what was going on (aside: what would I have done if I was trying to avoid side effects like that?). My functions are:

val f: NEL[Int] => String    = (l: NEL[Int]) => {println("f: " + l); l.toString |+| "X" }
val g: NEL[String] => BigInt = (l: NEL[String]) => {println("g: " + l);  BigInt(l.map(_.length).sum) }

Then I combine them via a cokleisli and pass in a NEL[Int]

val k = cokleisli(f) =>= cokleisli(g)
println("RES: "  + k( NEL(1, 2, 3) ))

What does this print?

f: NonEmptyList(1, 2, 3)
f: NonEmptyList(2, 3)
f: NonEmptyList(3)
g: NonEmptyList(NonEmptyList(1, 2, 3)X, NonEmptyList(2, 3)X, NonEmptyList(3)X)
RES: 57

The RES value is the character count of the (String) elements in the final NEL. Two things occur to me:

1. How could I have known that my NEL was going to be reduced in this manner from the method signatures involved? (I wasn't expecting the result at all)
2. What is the point of this? Can a reasonably simple and easy-to-follow use case be distilled for me?

This question is a thinly-veiled plea for some lovely person like retronym to explain how this powerful library actually works.

Answer 1

To understand the result, you need to understand the Comonad[NonEmptyList] instance. Comonad[W] essentially provides three functions (the actual interface in Scalaz is a little different, but this helps with explanation):

map:    (A => B) => W[A] => W[B]
copure: W[A] => A
cojoin: W[A] => W[W[A]]

So, Comonad provides an interface for some container W that has a distinguished "head" element (copure) and a way of collecting all permutations of the container so that we get one container per element, with that element at the head (cojoin).

The way that this is implemented for NonEmptyList is that copure returns the head of the list, and cojoin returns a list of lists, with this list at the head and all tails of this list at the tail.

Example (I'm shortening "NonEmptyList" to "Nel"):

Nel(1,2,3).copure = 1
Nel(1,2,3).cojoin = Nel(Nel(1,2,3),Nel(2,3),Nel(3))

The =>= function is coKleisli composition. How would you compose two functions f: W[A] => B and g: W[B] => C, knowing nothing about them other than that W is a Comonad? The input type of f and the output type of g aren't compatible. However, you can map(f) to get W[W[A]] => W[B] and then compose that with g. Now, given a W[A], you can cojoin it to get the W[W[A]] to feed into that function. So, the only reasonable composition is a function k that does the following:

k(x) = g(x.cojoin.map(f))

So for your nonempty list:

g(Nel(1,2,3).cojoin.map(f))
= g(Nel(Nel(1,2,3),Nel(2,3),Nel(3)).map(f))
= g(Nel("Nel(1,2,3)X","Nel(2,3)X","Nel(3)X"))
= BigInt(Nel("Nel(1,2,3)X","Nel(2,3)X","Nel(3)X").map(_.length).sum)
= BigInt(Nel(11,9,7).sum)
= 27

Answer 2

Cojoin is also defined for scalaz.Tree and scalaz.TreeLoc. This can be exploited to find a stream of all paths from the root of the tree to each leaf node.

def leafPaths[T](tree: Tree[T]): Stream[Stream[T]]
  = tree.loc.cojoin.toTree.flatten.filter(_.isLeaf).map(_.path)

Using coKleisli arrow composition, we can do this, for example:

def leafDist[A] = (cokleisli(leafPaths[A]) &&& cokleisli(_.rootLabel))
  =>= (_.map(s => (s._2, s._1.map(_.length).max)))

leafDist takes a Tree and returns a copy of it with each node annotated with its maximum distance from a leaf.