_4.2.scala

object Ex_4_2 extends App {

  override def main(args: Array[String]) = {
    println(factorial(5))
    println(genRecur((x, y) => x * y, 1)(x => x)(1, 5)) // same as factorial
  }

  def sum(f: Int => Int)(a: Int, b: Int): Int = {
    def iter(a: Int, accum: Int): Int = {
      if (a > b) accum
      else iter(a + 1, accum + f(a))
    }
    iter(a, 0)
  }

  def product(f: Int => Int)(a: Int, b: Int): Int =
    if (a > b) 1 else f(a) * product(f)(a + 1, b)

  def factorial(x: Int): Int =
    product(x => x)(1, x)

  // Generalized function of sum and product, iterative variant
  def genIter(aggFun: (Int, Int) => Int, initVal: Int)(f: Int => Int)(a: Int, b: Int): Int = {
    if (a > b) initVal
    else aggFun(f(a), genIter(aggFun, initVal)(f)(a + 1, b))
  }

  // Same, tail recursion
  def genRecur(aggFun: (Int, Int) => Int, initVal: Int)(f: Int => Int)(a: Int, b: Int): Int = {
    def iter(a: Int, accum: Int): Int = {
      if (a > b) accum
      else iter(a + 1, aggFun(accum, f(a)))
    }
    iter(a, initVal)
  }
}

_4.3.1.scala

object Ex_4_3_1 extends App {

  override def main(args: Array[String]) = {
    println(sqrt(16))
    println(cubeRoot(9))
  }

  def isCloseEnough(x: Double, y: Double) = Math.abs((x - y) / x) < 0.0001

  def fixedPoint(f: Double => Double)(firstGuess: Double): Double = {
    def iterate(guess: Double): Double = {
      val next = f(guess)
      // println(next)
      if (isCloseEnough(guess, next)) next
      else iterate(next)
    }
    iterate(firstGuess)
  }

  def averageDamp(f: Double => Double)(x: Double) = (x + f(x)) / 2

  def sqrt(x: Double) = fixedPoint(averageDamp(y => x / y))(1.0)

  def cubeRoot(x: Double) = fixedPoint(averageDamp(y => x / y / y))(1.0)
}

_5.0.1.scala

object Ex_5_0 extends App {

  override def main(args: Array[String]) = {
    val oddSet = new NonEmptySet(5, new EmptySet, new EmptySet).incl(3).incl(7).incl(1) // (1,3,5,7)
    val evenSet = new NonEmptySet(6, new EmptySet, new EmptySet).incl(2).incl(4) // (2,4,6)
    println(oddSet.union(evenSet)) // (1,2,3,4,5,6,7)

    val _2_4 = new NonEmptySet(2, new EmptySet, new EmptySet).incl(3).incl(4) // (2,3,4)
    val _3_5 = new NonEmptySet(3, new EmptySet, new EmptySet).incl(4).incl(5) // (3,4,5)
    println(_2_4.intersection(_3_5)) // (3,4)
  }

  trait IntSet {
    def incl(x: Int): IntSet

    def contains(x: Int): Boolean

    def union(x: IntSet): IntSet

    def intersection(x: IntSet): IntSet

    def isEmpty: Boolean
  }

  class EmptySet extends IntSet {
    def contains(x: Int): Boolean = false

    def incl(x: Int): IntSet = new NonEmptySet(x, new EmptySet, new EmptySet)

    def union(x: IntSet) = x

    def intersection(x: IntSet) = new EmptySet

    def isEmpty = true

    override def toString: String = " "
  }

  class NonEmptySet(elem: Int, left: IntSet, right: IntSet) extends IntSet {
    def contains(x: Int): Boolean =
      if (x < elem) left contains x
      else if (x > elem) right contains x
      else true

    def incl(x: Int): IntSet =
      if (x < elem) new NonEmptySet(elem, left incl x, right)
      else if (x > elem) new NonEmptySet(elem, left, right incl x)
      else this

    def union(x: IntSet): IntSet = {
      right union left union x incl elem
    }

    def intersection(x: IntSet): IntSet =
      if (x contains elem) right intersection x incl elem
      else right.intersection(x)

    def isEmpty = false

    override def toString: String = left + String.valueOf(elem) + right
  }
}

_5.0.3.scala

object Ex_5_0_3 extends App {

  override def main(args: Array[String]) = {
    println(Zero.successor.successor + Zero.predecessor.predecessor.predecessor) // 2 + (-3) = -1
  }

  abstract class Integer extends App {
    def isZero: Boolean

    def predecessor: Integer

    def successor: Integer

    def +(that: Integer): Integer

    def -(that: Integer): Integer

    def isPositive: Boolean

    def negate: Integer

    override def toString = {
      def neg(x: Integer): Int = {
        if (x.isZero) 0
        else if (x.successor.isZero) 1
        else 1 + neg(x.successor)
      }
      def pos(x: Integer): Int = {
        if (x.isZero) 0
        else if (x.predecessor.isZero) 1
        else 1 + pos(x.predecessor)
      }
      if (isPositive) String.valueOf(pos(this))
      else String.valueOf(-neg(this))
    }
  }

  object Zero extends Integer {
    def isZero: Boolean = true

    def predecessor: Integer = new Pred(Zero)

    def successor: Integer = new Succ(Zero)

    def +(that: Integer): Integer = that

    def -(that: Integer): Integer = that.negate

    def isPositive = false

    def negate = Zero
  }

  class Succ(x: Integer) extends Integer {
    def isZero: Boolean = false

    def predecessor: Integer = x

    def successor: Integer = new Succ(this)

    def +(that: Integer): Integer = x + that.successor

    def -(that: Integer): Integer = x - that.predecessor

    def isPositive = true

    def negate = {
      def helper(current: Integer, accum: Integer): Integer = {
        if (current.predecessor.isZero) accum.predecessor
        else helper(current.predecessor, accum.predecessor)
      }
      helper(this, Zero)
    }
  }

  class Pred(x: Integer) extends Integer {
    def isZero = false

    def predecessor: Integer = new Pred(this)

    def successor: Integer = x

    def +(that: Integer): Integer = x + that.predecessor

    def -(that: Integer): Integer = x - that.successor

    override def isPositive = false

    def negate = {
      def helper(current: Integer, accum: Integer): Integer = {
        if (current.successor.isZero) accum.successor
        else helper(current.successor, accum.successor)
      }
      helper(this, Zero)
    }
  }
}

_6.2.2.scala

object Ex_6_2_2 extends App {

  abstract class IntTree {
    def contains(t: IntTree, v: Int): Boolean = t match {
      case EmptyTree => false
      case Node(value, left, right) =>
        if (v < value) contains(left, v)
        else if (v > value) contains(right, v)
        else true
    }

    def insert(t: IntTree, v: Int): IntTree = t match {
      case EmptyTree => new Node(v, EmptyTree, EmptyTree)
      case Node(value, left, right) =>
        if (v < value) insert(left, v)
        else if (v > value) insert(right, v)
        else this
    }
  }

  case object EmptyTree extends IntTree

  case class Node(elem: Int, left: IntTree, right: IntTree) extends IntTree
}

_8.1.1.scala

object Ex_8_1_1 extends App {

  override def main(args: Array[String]) = {
    println(isort(List(6, 3, 4, 8, 1, 4, 7, 2)))
    println(isort_(List(6, 3, 4, 8, 1, 4, 7, 2)))
  }

  def isort_(xs: List[Int]): List[Int] =
    if (xs.isEmpty) Nil
    else insert_(xs.head, isort_(xs.tail))

  def insert_(x: Int, xs: List[Int]): List[Int] = {
    if (xs.isEmpty) List(x)
    else if (x <= xs.head) x :: xs
    else xs.head :: insert_(x, xs.tail)
  }

  def isort(xs: List[Int]): List[Int] = xs match {
    case List() => List()
    case y :: ys => insert(y, isort(ys))
  }

  def insert(x: Int, xs: List[Int]): List[Int] = xs match {
    case List() => List(x)
    case y :: ys => if (x <= y) x :: xs else y :: insert(x, ys)
  }
}

_8.4.1.scala

object Ex_8_4_1 extends App {

  override def main(args: Array[String]) = {
    println(squareList(List(1, 2, 3, 4, 5)))
    println(squareList_(List(1, 2, 3, 4, 5)))
  }

  def squareList(xs: List[Int]): List[Int] = xs match {
    case List() => List()
    case y :: ys => y * y :: squareList(ys)
  }

  def squareList_(xs: List[Int]): List[Int] =
    xs map (x => x * x)
}

_8.4.3.scala

object Ex_8_4_3 extends App {

  override def main(args: Array[String]) = {
    println(mapFun[Int, String](List(1, 2, 3, 4), (x => "#" + x * x)))
    println(lengthFun(List(1, 2, 3, 4, 5)))
  }

  def mapFun[A, B](xs: List[A], f: A => B): List[B] =
    (xs :\ List[B]()) {
      (y, ys) => f(y) :: ys
    }

  def lengthFun[A](xs: List[A]): Int =
    (0 /: xs) {
      (y, ys) => 1 + y
    }
}

_9.1.1.scala

object Ex_9_1_1 extends App {

  override def main(args: Array[String]) = {
    println(queens(8).length) // 92 seems OK according to Wikipedia article
  }

  def queens(n: Int): List[List[Int]] = {
    def placeQueens(k: Int): List[List[Int]] =
      if (k == 0) List(List())
      else for {queens <- placeQueens(k - 1)
                column <- List.range(1, n + 1)
                if isSafe(column, queens, 1)} yield column :: queens
    placeQueens(n)
  }

  def isSafe(col: Int, queens: List[Int], delta: Int): Boolean =
    if (queens.isEmpty) true
    else if (queens.contains(col)) false
    else if (queens.head == col + delta || queens.head == col - delta) false
    else isSafe(col, queens.tail, delta + 1)
}

_9.3.1.scala

object Ex_9_3_1 extends App {

  override def main(args: Array[String]) = {
    println(flatten(List(List(1, 2), List(3, 4), List(5, 6))))
    println(flatten_(List(List(1, 2), List(3, 4), List(5, 6))))
  }

  def flatten[A](xss: List[List[A]]): List[A] =
    (xss :\ (Nil: List[A]))((xs, ys) => xs ::: ys)

  def flatten_[A](xss: List[List[A]]): List[A] =
    for {xs <- xss; x <- xs} yield x
}

_9.3.2.scala

object Ex_9_3_2 extends App {

  override def main(args: Array[String]) = {

    case class Book(title: String, authors: List[String])

    val books: List[Book] = List(
      Book("Structure and Interpretation of Computer Programs", List("Abelson, Harold", "Sussman, Gerald J.")),
      Book("Principles of Compiler Design", List("Aho, Alfred", "Ullman, Jeffrey")),
      Book("Programming in Modula2", List("Wirth, Niklaus")),
      Book("Introduction to Functional Programming", List("Bird, Richard")),
      Book("The Java Language Specification", List("Gosling, James", "Joy, Bill", "Steele, Guy", "Bracha, Gilad")))

    println(for (b <- books; a <- b.authors if a startsWith "Bird") yield b.title)
    println(for (b <- books if (b.title indexOf "Program") >= 0) yield b.title)

    println(books.filter(b => b.authors(0).startsWith("Bird")).map(b => b.title))
    println(books.filter(b => (b.title indexOf "Program") >= 0).map(b => b.title))
  }
}

Programming in Scala

My (not yet complete) solutions to exercises from 'Programming in Scala' book