SIP-NN - comonadic-comprehensions

By: Shimi Bandiel

History

Date Version
Feb 22nd 2017 Initial Draft

Motivation

Scala provides a concise syntax for working with Monads(map & flatMap): the for comprehension.

Following is a proposal for a concise syntax for working with Comonads(map, extract & coflatMap): the cofor comprehension.

The proposal has an existing implementation in PR 5725

Motivating Examples

Examples

Consider the following class:

case class StreamZipper[A](left: Stream[A], focus: A, right: Stream[A]) {
  def map[B](f: A => B): StreamZipper[B] = 
    StreamZipper(left.map(f), f(focus), right.map(f))
  def extract: A = 
	focus 
  def coflatMap(f: StreamZipper[A] => B): StreamZipper[B] = 
	??? 
}

StreamZipper[A] represents a non-empty Stream of As with a cursor (focus).

  • The map method invokes f on every element and produces a StreamZipper of the results.
  • The extract method returns the value at the cursor
  • The coflatMap method invokes f on every cursor (all possible zippers) providing a contextual global operation. The result is a StreamZipper[B] of the results with a cursor pointing at the same location as this.

The above implementation for coflatMap was left out for brevity. See 3.

Now, consider the following methods:

  
  // returns whether the current cursor in a zipper of ints is between the previous
  // and the next numbers.
  def isInTheMiddle(z : StreamZipper[Int]): Boolean = 
    z match {
      case StreamZipper(pi +: _, i, ni +: _) if (pi < i && i < ni) => true
      case _ => false
    }  

  // counts how many consecutive values of <i>true</i> starting from the cursor
  def numberOfTrues(z: StreamZipper[Boolean]) : Int  = 
    if (z.focus) 1 + z.right.takeWhile(true ==).size else 0 

And, let’s say we have a StreamZipper[Person]:

  case class Person(name: String, age: Int)
  
  // a given stream with cursor at some position
  val people: StreamZipper[Person] = ???

We would like to get the following:

  /*
  * A StreamZipper of triplets containing:
  *  _1 -- the original Person value.
  *  _2 -- whether this Person's age is higher than the previous and lower than the next.
  *         We'll call this boolean TAG.
  *  _3 -- how many consecutive TAGs with value "true" starting from current cursor.
  */
	val goal: StreamZipper[(Person, Boolean, Int)] = ???

It seems we can re-use the isInTheMiddle and numberOfTrues methods. However, without the proposed cofor syntax we’ll probably end with:

   val goal = people.map(p => (p, p.age)).coflatMap { zipperOfTuple =>
		val ages = zipperOfTuple.map(_._2)
		(zipperOfTuple.extract._1, isInTheMiddle(ages))
   }.coflatMap { zipperOfTuple =>
		val tags = zipperOfTuple.map(_._2)
		val persons = zipperOfTuple.map(_._1)
		val trues = numberOfTrues(tags)
		persons.extract, tags.extract, trues)
   }

From the code above, you can see that it is quite cumbersome to handle the passing of the context between the invocations of coflatMap.

The proposed syntax allows for the following usage:

  val flow : StreamZipper[Person] => (Person, Boolean, Int) = 
    cofor (p @ Person(_, age)) {
      tag <- isInTheMiddle(age)
      count <- numberOfTrues(tag)
    } yield (p.extract, tag.extract, count.extract)
	
  val goal = people.coflatMap(flow)

Syntax

The proposed syntax is based on the paper by Dominic Orchard and Alan Mycroft 1.

The syntax for cofor is defined as:

	cofor (pattern0) {
		pattern1 <- generator1
		pattern2 <- generator2
		...
	} yield body
	
	patternN    = regular case patterns
	generatorN  = expr 
	body        = expr

The result type of a cofor expression is a function from the comonad type to a result (T[A] => B). This means that the return type must be available at call-site! Note that unlike for, guards and assignments are not supported.

Desugaring

A cofor desugaring is much more complex than the respective for.

Desugaring example:

  val flow : StreamZipper[Person] => (Person, Boolean, Int) = 
    cofor (p @ Person(_, age)) {
      tag <- isInTheMiddle(age)
      count <- numberOfTrues(tag)
    } yield (p.extract, tag.extract, count.extract)
	
  val goal = people.coflatMap(flow)

The above cofor expression will be desugared into the following function:

	input => {
	  // desugaring the generators
	  val enums = 
		// assign values to input variables
		// actual assignment is done through pattern matching
		input.map(p => (
			p match {
				case p @ Person(_, age) => p
			}
			, (p match {
				case p @ Person(_, age) => age
			}, ()))).
		coflatMap(env => {
			// extracting collected values from the context
			val p = env.map(env => env._1)
			val age = env.map(env => env._2._1)
			// now we pass the current context and the generator result
			(isInTheMiddle(age), env.extract)
		}).coflatMap(env => {
			// extracting collected values from the context
			val tag = env.map(env => env._1)
			val p = env.map(env => env._2._1)
			val age = env.map(env => env._2._2._1)
			// now we pass the current context and the generator result
			(numberOfTrues(tag), env.extract)
		})
		// the body phase (yield)
		{
			// deconstructing the collected context
			val count = enums.map(env => env._1)
			val tag = enums.map(env => env._2._1)
			val p = enums.map(env => env._2._2._1)
			val age = enums.map(env => env._2._2._2._1)
			(p.extract, tag.extract, count.extract)
		}
	}

Drawbacks

  1. Adding a new keyword to the language makes it more complex
  2. Understanding the desugaring and concept behind cofor is not trivial and it's much more complex than for (which many developers still don't feel at ease with).

References

  1. A Notation for Comonads
  2. Implementation Pull-Request
  3. StreamZipper Example

Contents