Skip to content

Instantly share code, notes, and snippets.

@akabe
Last active June 24, 2016 00:48
Show Gist options
  • Save akabe/ba96899fc4cc60796c88b5c6374eb3a8 to your computer and use it in GitHub Desktop.
Save akabe/ba96899fc4cc60796c88b5c6374eb3a8 to your computer and use it in GitHub Desktop.
A simple example of type-safe head, tail, and zip of List by Peano-style type-level natural number via phantom type in Scala
object SafeList {
trait Z // phantom type "zero" (corresponding to 0)
trait S[N] // phantom type "successor" (correspoding to n => n+1)
class SList[N, E] private[SafeList] (private[SafeList] val list: List[E])
// SList[N, E] is a list of elements of type E, and length N.
def empty[E] = new SList[Z, E](Nil)
def cons[N, E] (x: E, xs: SList[N, E]) = new SList[S[N], E](x :: xs.list)
def head[N, E] (xs: SList[S[N], E]) = xs.list.head
def tail[N, E] (xs: SList[S[N], E]) = new SList[N, E](xs.list.tail)
def zip[N, A, B] (xs: SList[N, A], ys: SList[N, B]) = new SList[N, (A, B)](xs.list.zip(ys.list))
}
import SafeList._
val a = empty[String] // a: SList[Z, String]
val b = cons("foo", a) // b: SList[S[Z], String]
val c = cons("bar", b) // c: SList[S[S[Z]], String]
val d = tail(c) // "head" and "tail" of a non-zero-length list succeed.
val e = head(a) // "head" and "tail" of a zero-length list cause a type error.
val f = zip(b, d) // "zip" for lists of the same length succeed.
val g = zip(a, c) // "zip" for lists of different sizes cause a type error.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment