Skip to content

Instantly share code, notes, and snippets.

@dekosuke
Created December 17, 2011 17:34
Show Gist options
  • Save dekosuke/1490821 to your computer and use it in GitHub Desktop.
Save dekosuke/1490821 to your computer and use it in GitHub Desktop.
SnocList
object SnocList{
}
sealed trait SnocList[+A] {
def isEmpty : Boolean
def ::>[B >: A] (x: B): SnocList[B] = new ::>[B](this, x)
def map[B](f: A=>B) : SnocList[B] = this match {
case SnocNil => SnocNil
case xs ::> x => xs.map(f) ::> f(x)
}
def foldLeft[B](z: B)(f: (B, A) => B): B = this match {
case SnocNil => z
case xs ::> x => f(xs.foldLeft(z)(f), x)
}
override def toString() = {
val contents = getContents()
"SnocList(" + contents + ")"
}
def getContents():String = this match {
case SnocNil => ""
case SnocNil ::> x => x.toString()
case xs ::> x => xs.getContents() + ", " + x.toString()
}
}
case object SnocNil extends SnocList[Nothing] {
val list = Nil
override def isEmpty = true
def head: Nothing = throw new NoSuchElementException("head of empty list")
def tail: SnocList[Nothing] = throw new NoSuchElementException("tail of empty list")
}
case class ::>[B](tl:SnocList[B], hd: B) extends SnocList[B] {
val list = Nil
override def isEmpty = false
def head : B = hd
def tail : SnocList[B] = tl
}
val l = SnocNil ::> 1 ::> 2 ::> 3
println(""+l)
println(""+l.map(x=>2*x))
println(""+l.map(x=>2*x).foldLeft(1)( _ + _ ))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment