Scala 11 - Abstract Class, Basics

스칼라 튜토리얼, scala의 Abstract class에 대해 알아보자

---

Abstract Class: Specification

Abstract Classes can be used to abstract away the implementation details.

In short, abstract classes is used for specfication, and concrete sub-classes for implementation.

---

Example: Abstract case for specification

abstract class Iter[A] {
  def getValue: Option[A]
  def getNext: Iter[A]
}

def sumElements[A](f: A=>Int)(xs: Iter[A]): Int = 
  xs.getValue match {
    case None => 0
    case Some(n) => f(n) + sumElements(f)(xs.getNext)
  }
def sumElementsId(xs: Iter[Int]) =
  sumElements((x:Int)=>x)(xs)

---

Example: Concrete Class for implementation

sealed abstract class MyList[A] extends Iter[A]
case class MyNil[A]() extends MyList[A] {
  def getValue = None
  def getNext = throw new Exception("...")
}

case class MyCons[A](hd: A, tl: MyList[A])
  extends MyList[A]
{
  def getValue = Some(hd)
  def getNext = tl
}

val tl = MyCons(3, MyCons(5, MyCons(7, MyNil())))

sumElementsId(t1)

---

Exercise

Define IntCounter(n) that implements the specification Iter[A]

class IntCounter(n: Int) extends Iter[Int] {
  def getValue = ???
  def getNext = ???
}

sumElementsId(new IntCounter(100))

• Answer :

class IntCounter(n: Int) extends Iter[Int] {
  def getValue = if (n >= 0) Some(n) else None
  def getNext = new IntCounter(n-1)
}

sumElementsId(new IntCounter(100))

---

More on Abstract Classes

• Problem: Iter for MyTree

abstract class Iter[A] {
  def getValue: Option[A]
  def getNext: Iter[A]
}

sealed abstract class MyTree[A]
case class Empty[A]() extends MyTree[A]
case class Node[A](value: A,
                   left: MyTree[A],
                   right: MyTree[A]) extends MyTree[A]                   

Q. Can MyTree[A] implement Iter[A]?
Try it, but is is not easy.

---

Solution: Better Specification

abstract class Iter[A] {
  def getValue: Option[A]
  def getNext: Iter[A]
}

abstract class Iterable[A] {
  def iter: Iter[A]
}

def sumElements[A](f: A=> Int)(xs: Iter[A]): Int = 
  xs.getValue match {
    case None => 0
    case Some(n) => f(n) + sumElements(f)(xs.getNext)
  }

def sumElementsGen[A](f: A=> Int)(xs: Iterable[A]): Int = 
  sumElements(f)(xs.iter)

---

Let's Use MyList

sealed abstract class MyList[A] extends Iter[A]
case class MyNil[A]() extends MyList[A] {
  def getValue = None
  def getNext = throw new Exception("...")
}

case class MyCons[A](val hd: A, val tl: MyList[A])
  extends MyList[A] {
    def getValue = Some(hd)
    def getNext = tl
}

---

MyTree <: Iterable (Try)

sealed abstract class MyTree[A] extends Iterable[A]

case class Empty[A]() extends MyTree[A] {
  val iter = MyNil()
}

case class Node[A](value: A,
                  left: MyTree[A],
                  right: MyTree[A]) extends MyTree[A] {
  // "val iter" is more specific than "def iter",
  // so it can be used in a sub type.
  // In this example, "val iter" is also 
  // more efficient than "def iter".
  val iter = MyCons(value, ???(left.iter,right.iter))
}

---

Extend MyList with append

sealed abstract class MyList[A] extends Iter[A] {
  def append(lst: MyList[A]) : MyList[A]
}
case class MyNil[A]() extends MyList[A] {
  def getValue = None
  def getNext = throw new Exception("...")
  def append(lst: MyList[A]) = lst
}
case class MyCons[A](val hd: A, val tl: MyList[A])
  extends MyList[A]
{
  def getValue = Some(hd)
  def getNext = tl
  def append(lst: MyList[A]) = MyCons(hd,tl.append(lst))
}

To make function tail-recursive, you have to avoid make function as member of the class. Compiler will not optimize member function of the class!

So how can we make append function tail-recursive?

---

Note: tail-recursive "append"

sealed abstract class MyList[A] extends Iter[A] {
  def append(lst: MyList[A]): MyList[A] = 
    MyList.revAppend(MyList.revAppend(this, MyNil()), lst)
}

object MyList {
  // Tail-recursive functions should be written in "object"
  def revAppend[A](lst1: MyList[A], lst2: MyList[A]): MyList[A] = 
    lst1 match {
      case MyNil() => lst2
      case MyCons(hd, tl) => revAppend(tl, MyCons(hd, lst2))
    }
}

case class MyNil[A]() extends MyList[A] {
  def getValue = None
  def getNext = throw new Exception("...") 
}

case class MyCons[A](val hd: A, val tl: MyList[A])
  extends MyList[A] {
    def getValue = Some(hd)
    def getNext = tl
}

---

MyTree <: Iterable

sealed abstract class MyTree[A] extends Iterable[A] {
  def iter: MyList[A]
  // Note:
  // def iter: Int // Type Error because not (Int <: Iter[A])
}
case class Empty[A]() extends MyTree[A] {
  val iter = MyNil()
}
case class Node[A](value: A,
                   left: MyTree[A],
                   right: MyTree[A]) extends MyTree[A] {
  def iter = MyCons(value, left.iter.append(right.iter))
  // def iter = left.iter.append(MyCons(value, right.iter))
  // def iter = left.iter.append(right.iter.append(
                  MyCons(value, MyNil())))
}

---

Test

def generateTree(n: Int): MyTree[Int] = {
  def gen(lo: Int, hi: Int): MyTree[Int] = 
    if(lo > hi) Empty()
    else {
      val mid = (lo+hi)/2
      Node(mid, gen(lo, mid-1), gen(mid+1, hi))
    }
    gen(1, n)
}

sumElementsGen((x: Int)=>x)(generateTree(100))

---

Problem: Inefficiency

def time[R](block: => R): R = {
  val t0 = System.nanoTime()
  val result = block    // call-by-name
  val t1 = System.nanoTime()
  println("Elapsed time: " + ((t1 - t0)/1000000)+ "ms"); result
}

// More to go...