Skip to content

Instantly share code, notes, and snippets.

@dohzya
Last active August 29, 2015 14:09
Show Gist options
  • Save dohzya/84de3d09cb3ca079ce69 to your computer and use it in GitHub Desktop.
Save dohzya/84de3d09cb3ca079ce69 to your computer and use it in GitHub Desktop.
// avoid warnings about the use of Higher Kinds
import scala.language.higherKinds
// implementing Forall
trait Forall[+G[_]] { def apply[A]: G[A] }
// note: this implementation is covariant, in order to make Null works
// The Cons type, based on Forall
type Cons[+A, +B] = Forall[({ type G[C] = ((A, B) => C) => C })#G]
def cons[A, B](a: A, b: B): Cons[A, B] = new Cons[A, B] {
def apply[C]: ((A, B) => C) => C = { f => f(a, b) }
}
// The car and cdr methods are really simple
def car[A, B](c: Cons[A, B]): A = c[A]((a, b) => a)
def cdr[A, B](c: Cons[A, B]): B = c[B]((a, b) => b)
// Conventionnal end-of-the-list value
trait Empty
object Empty extends Empty
// that's why we needed a covariant version of Forall:
// an instance of Empty has type Empty.type which extends Empty
// A basic helper
def list[A1, A2, A3](a1: A1, a2: A2, a3: A3) = {
cons(a1, cons(a2, cons(a3, Empty)))
}
// Now it's time to play
val l: Cons[Int, Cons[String, Cons[Boolean, Empty]]] = list(1, "a", true)
// checks that the types are right
car(l): Int
cdr(l): Cons[String, Cons[Boolean, Empty]]
car(cdr(l)): String
// checks that the values are right
println(car(l))
println(car(cdr(l)))
println(car(cdr(cdr(l))))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment