SnocList

gistfile1.scala

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)( _ + _ ))