Type-Level Programming in Scala, Part 8c: KList ZipWith

One use of KList and the ‘transform’ and ‘down’ methods from 8b is to implement methods like ‘zipWith’ for arbitrary tuple lengths. To start with, the signature of zipWith for a pair of Streams, operating on a fixed arity of 2, looks like:

def zipWith2[A,B,C](t2: (Stream[A], Stream[B]))(f: (A,B) => C): Stream[C] =
   t2 match
   {
      case (ha #:: ta, hb #:: tb) => Stream.cons( f(ha, hb), zipWith2( (ta, tb) )(f) )
      case _ => Stream.empty
   }

Example usage:

val nats = Stream.from(1)
val random = Stream.continually( math.random )
val seq = zipWith2( (nats, random) ) { (n, r) => if(r > 0.3) n else -n }

scala> seq.take(10).toList
res0: List[Int] = List(-1, 2, 3, 4, 5, 6, -7, -8, 9, 10)

For the implementation of zipWith2, if either Stream in the pair is empty, the resulting Stream is empty. Otherwise, there is a head element for each stream in the pair. We apply the provided function to these elements and make the result the head of a new Stream. The tail of this new Stream will be the result of recursing on the tails of the input pair.

To generalize this to arbitrary arity, we will operate on a KList of Streams. Because we want to abstract over arity, we use a heterogeneous list. We use KList instead of HList because we want to constrain each element in the tuple to be a Stream and we don’t care what the specific types of Streams the elements are, but we do want to preserve those types. When we take the head element of each Stream, the resulting list is the underlying HList type of the input KList. For example, given an input of type KList[Stream, A :: B :: HNil], when we take the head of each Stream in the KList we will get an HList of type A :: B :: HNil. This is like going from (Stream[A], Stream[B]) to (A,B).

So, if we end up with the underlying HList type, the function we will apply to the input KList must be a function from that HList type to some other type. In the example above, the function type would be A :: B :: HNil => T for some type T, which will be the type of the output Stream. With this, we have our signature for a generalized zipWith:

def zipWith[HL <: HList, T](kl: KList[Stream, HL])(f: HL => T): Stream[T]

To implement this function, we again break the problem into two parts. If any Stream is empty, the resulting stream is empty. Otherwise, we get all the head elements of the Streams as an HList, apply the input function to it, and make this the new head. For the tail, we get all of the tails of the Streams and recurse. To get the head elements, we use ‘down’ because we want KList[Stream, HL] => HL. For the tails, we use 'transform' because we need a mapping KList[Stream, HL] => KList[Stream, HL]. The implementation looks like:

def zipWith[HL <: HList, T](kl: KList[Stream, HL])(f: HL => T): Stream[T] =
   if(anyEmpty(kl))
      Stream.empty
   else
      Stream.cons( f( kl down heads ), zipWith(kl transform tails )( f ) )

def anyEmpty(kl: KList[Stream, _]): Boolean = kl.toList.exists(_.isEmpty)

val heads = new (Stream ~> Id) { def apply[T](s: Stream[T]): T = s.head }
val tails = new (Stream ~> Stream) { def apply[T](s: Stream[T]): Stream[T] = s.tail }

The toList function on KList has type KList[M, HL] => List[M[_]] and has a trivial implementation. Since List is homogeneous, we can’t preserve each individual cell’s type, but we can at least use the common type constructor. In ‘zipWith’, this means we can call the ‘isEmpty’ method on the elements of the list but we would not get a very specific type if we called ‘head’, for example. ‘heads’ and ‘tails’ are natural transformations that map a Stream[T] to its head of type T and its tail of type Stream[T], respectively.

The original example translated to use the generalized zipWith looks like:

val nats = Stream.from(1)
val random = Stream.continually( math.random )
val seq = zipWith( nats :^: random :^: KNil ) {
   case n :: r :: HNil => if(r > 0.3) n else -n
}

scala> seq.take(10).toList
res0: List[Int] = List(-1, 2, -3, -4, -5, 6, 7, 8, 9, 10)

We can implement the related ‘zipped’ function in terms of ‘zipWith’.

def zipped[HL <: HList](kl: KList[Stream, HL]): Stream[HL] =
   zipWith(kl)(x => x)

Or, we could have implemented zipWith in terms of zipped. In any case, we can implement several other functions using zipped:

def foreach[HL <: HList, T](kl: KList[Stream, HL])(f: HL => T): Unit =
   zipped(kl).foreach(f)

def collect[HL <: HList, T](kl: KList[Stream, HL])(f: HL => Option[T]): Stream[T] =
   zipped(kl).collect(f)

def flatMap[HL <: HList, T](kl: KList[Stream, HL])(f: HL => Stream[T]): Stream[T] =
   zipped(kl).flatMap(f)

def forall[HL <: HList](kl: KList[Stream, HL])(f: HL => Boolean): Boolean =
   zippped(kl).forall(f)
      
def exists[HL <: HList](kl: KList[Stream, HL])(f: HL => Boolean): Boolean =
   zipped(kl).exists(f)

An example using ‘foreach’:

val a = Stream(1,2,5,3,9,10,101)
val b = Stream("one", "two", "three", "four")
val c = Stream(true, false, false, true, true)

zipped(a :^: b :^: c :^: KNil) foreach {
   case n :: s :: b :: HNil =>
      println( s * (if(b) 1 else n) )
}

one
twotwo
threethreethreethreethree
four

Type-Level Programming in Scala, Part 8b: KList basics

In the absence of rank-2 types, it can be useful to have a higher-kinded heterogeneous list, which I’ll call KList here. A KList defines a type constructor M[_] that is used to construct the type for all cells in the list. The parameter passed to this type constructor can be different for each cell, which is the heterogeneous part. One use of a KList is to define a generic zipWith function. KLists are also used in the implementation of the new task engine in sbt 0.9. Each of these applications will be described in subsequent posts.

We’ll start with the basic definition of KList, which looks like:

sealed trait KList[+M[_], HL <: HList]

final case class KCons[H, T <: HList, +M[_]](head: M[H], tail: KList[M,T]) extends KList[M, H :+: T] {
  // prepend
  def :^: [N[X] >: M[X], G](g: N[G]) = KCons(g, this)
}

sealed class KNil extends KList[Nothing, HNil] {
  def :^: [M[_], H](h: M[H]) = KCons(h, this)
}

object KNil extends KNil

object KList {
  // nicer alias for pattern matching
  val :^: = KCons
}

It looks similar to HList with the exception of the type constructor M. We keep the type of ‘head’ in KCons in two pieces: the type constructor M common to all cells in the KList and the type parameter to M that is specific to this cell. The full type of ‘head’ is then M[H].

An example construction:

  val m = List(1, 2, 3, 4) :^: List("str1", "str2") :^: KNil

This has type:

KCons[Int,java.lang.String :: HNil,List]

Note that we can mix type constructors that are compatible:

  val m = Seq(1, 2, 3, 4) :^: List("str1", "str2") :^: KNil
  m: KCons[Int,java.lang.String :: HNil,Seq]

Ones that are not compatible crash the compiler:

val m = Seq(1, 2, 3, 4) :^: Option("str1", "str2") :^: KNil
scala.tools.nsc.symtab.Types$NoCommonType: lub/glb of incompatible types: [X]Option[X] and Seq

It is not possible to have types inferred in several cases, such as when the type constructor is Id, where type Id[X] = X :

  // does not compile
  val p = 1 :^: true :^: KNil

A key use of a KList is to apply a natural transformation to its contents. We have kept the type constructor separate from the type parameters, which means we can apply a natural transformation M ~> N to each element and preserve the underlying type parameters. As an example, consider our heterogeneous list of Lists:

  val m = List(1, 2, 3, 4) :^: List("str1", "str2") :^: KNil

and a natural transformation that takes a List and calls headOption on it:

val headOption = new (List ~> Option) {
  def apply[T](list: List[T]): Option[T] =
    list.headOption
}

Then, apply headOption to m:

val heads = m transform headOption
heads: KCons[Int,(java.lang.String :: HNil),Option] = KCons(Some(1),KCons(Some(str1),KNil))

We get a KList of Options, preserving the knowledge that the first element has type Option[Int] and the second has type Option[String].

The ‘transform’ method on KList is straightforward to implement:

sealed trait KList[+M[_], HL <: HList] {
  ...
  def transform[N[_]](f: M ~> N): KList[N, HL]
}

final case class KCons[H, T <: HList, +M[_]](head: M[H], tail: KList[M,T]) extends KList[M, H :+: T] {
  ...  
  def transform[N[_]](f: M ~> N) = KCons( f(head), tail transform f )
}

sealed class KNil extends KList[Nothing, HNil] {
  ...
  def transform[N[_]](f: Nothing ~> N) = KNil
}

We can add another method that down-converts a KList to its underlying HList. For example, we might reduce each List in our KList above to its head element:

val head = new (List ~> Id) {
  def apply[T](list: List[T]): T =
    list.head
}

val heads = m down head
heads: Int :: java.lang.String :: HNil = 1 :: str1 :: HNil

The definition of ‘down’ looks like:

sealed trait KList[+M[_], HL <: HList] {
  ...
  // For converting KList to an HList
  def down(f: M ~> Id): HL
}

final case class KCons[H, T <: HList, +M[_]](head: M[H], tail: KList[M,T]) extends KList[M, H :+: T] {
  ...
  def down(f: M ~> Id) = HCons(f(head), tail down f)
}

sealed class KNil extends KList[Nothing, HNil] {
  ...
  def down(f: Nothing ~> Id) = HNil
}

We will use ‘down’ and ‘transform’ in the next section to implement zipWith for arbitrary arity.

Type-Level Programming in Scala, Part 8a: KList motivation

In part 8, we will look at operations on arbitrary arity tuples over a type constructor. These are higher-kinded heterogeneous lists, which I’ll KLists. To motivate why we might want such a structure, we’ll start with Tuple2 for simplicity.

Consider some basic transformations on the elements of a Tuple2. If we want to apply the same function to both elements, we can require that the elements have a common supertype and that the function operates on that supertype:

def map1[A <: C,B <: C,C,D](t: (A,B), f: C => D): (D,D) =
 (f(t._1), f(t._2))

scala> map1( ("3", true), (_: Any).hashCode )
res1: (Int, Int) = (51,1231)

Or, we might want to supply two separate functions to operate on each component independently:

def map2[A,B,C,D](t: (A,B), f: A => C, g: B => D): (C,D) =
  (f(t._1), g(t._2))

scala> map2( (1, true), (_: Int) + 1, ! (_: Boolean) )
res3: (Int, Boolean) = (2,false)

Now, consider a Tuple2 where the types of both components are created by the same type constructor, such as (List[Int], List[Boolean]) or (Option[String], Option[Double]).

One useful operation on such a structure looks like:

def transform[F[_], A, B, G[_]] (k: (F[A], F[B]), g: F ~> G): (G[A], G[B]) =
  ( g(k._1), g(k._2) )

This applies the provided natural transformation to each element, preserving the underlying type parameter, but with a new type constructor. As an example, we can apply the toList transformation we defined in part 7:

val toList = new (Option ~> List) {
  def apply[T](opt: Option[T]): List[T] =
    opt.toList
}

// these are so that we get Option[T] as the type
// and not Some[T] or None
def some[T](t: T): Option[T] = Some(t)
def none[T]: Option[T] = None

scala> transform((some(3), some("str")), toList)
res5: (List[Int], List[java.lang.String]) = (List(3),List(str))

scala> transform((some(true), none[Double]), toList)
res6: (List[Boolean], List[Double]) = (List(true),List())

In part 6, we were concerned with the generalization of TupleN to arbitrary arity. In part 8, we will generalize ‘transform’ and related operations to heterogeneous lists over a type constructor.