S-99 P46-P50

p46-p50.scala

// P46
def and(a: Boolean, b: Boolean) = a && b
def or(a: Boolean, b: Boolean) = a || b
def nand(a: Boolean, b: Boolean) = !(a && b)
def nor(a: Boolean, b: Boolean) = !(a || b)
def impl(a: Boolean, b: Boolean) = a && b
def equ(a: Boolean, b: Boolean) = !a || b
def xor(a: Boolean, b: Boolean) = a ^ b
def not(a: Boolean) = !a

def table2(f: (Boolean, Boolean) => Boolean): Unit = {
  println("A     B     result")
  for (a <- List(true, false); b <- List(true, false)){
    printf("%-5s %-5s %-5s\n", a, b, f(a,b))
  }
}

// P47
case class P47(a: Boolean){
  lazy val not = !a
  def and(b: Boolean) = a && b
  def or(b: Boolean) = a || b
  def nand(b: Boolean) = !(a && b)
  def nor(b: Boolean) = !(a || b)
  def xor(b: Boolean) = a ^ b
  def impl(b: Boolean) = !a || b
  def eq(b: Boolean) = a == b
}

implicit def fromBooleanToP47(a: Boolean): P47 = P47(a)

// P49
def gray(n: Int): List[String] = {
  def grayR(n: Int, ls: List[String]): List[String] = {
    if (n == 1) ls
    else {
      grayR(n-1, ls flatMap {n => List(n + "0", n + "1")})
    }
  }
  grayR(n, List("0", "1"))
}

// P50
abstract sealed class Node[A]{
  val freq: Int
}

case class Leaf[A](element: A, freq: Int) extends Node[A]
case class Branch[A](left: Node[A], right: Node[A]) extends Node[A]{
  val freq = left.freq + right.freq
}

def huffman[A](ls: List[(A, Int)]): List[(A, String)] = {
  def makeTree(ls: List[Node[A]]): Node[A] = ls match{
    case Nil => throw new IllegalArgumentException
    case top :: Nil => top
    case _ => {
      val last = ls.sortBy(_.freq).slice(0, 2)
      makeTree(Branch(last(0), last(1)) :: ls filterNot {last.contains})
    }
  }
  def huffmanCode(n: Node[A], code: String): List[(A, String)] = n match{
    case Leaf(element, freq) => List((element, code))
    case Branch(left, right) => huffmanCode(left, code + "0") ::: huffmanCode(right, code + "1")
    case _ => throw new IllegalArgumentException
  }
  val top = makeTree(ls map {n => Leaf(n._1, n._2): Node[A]})
  huffmanCode(top, "")
}

// scala> huffman(List(("a", 45), ("b", 13), ("c", 12), ("d", 16), ("e", 9), ("f", 5)))
// res18: List[(java.lang.String, String)] = List((a,0), (c,100), (b,101), (f,1100), (e,1101), (d,111))