Scala by Example — Chapter 09

/**
 * Exercise 9.1.1 Provide an implementation of the missing function insert.
 */

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] = xs match {
  case Nil     => List(x)
  case t :: ts => 
    if (x < = t)
      x :: xs
    else
      t :: insert(x, ts)
}

val testList = 9 :: 3 :: 10 :: 12 :: 1 :: 37 :: 2 :: 200 :: Nil

println("Original: " + testList)
println("Sorted: " + isort(testList))

 

 

/**
 * Exercise 9.2.1 Design a tail-recursive version of length.
 */
def length(list: List[Int]): Int = {
  def iter(l: List[Int], accumulator: Int): Int = l match {
    case Nil    => accumulator
    case h :: t => iter(t, accumulator + 1)
  }
  iter(list, 0)
}


// test
val testList =  9 :: 3 :: 10 :: 12 :: 1 :: 37 :: 2 :: 200 :: Nil

println("Size of list: " + length(testList))

 

 

/**
 * Exercise 9.4.1 Consider a function which squares all elements of a list
 * and returns a list with the results. Complete the following two equivalent
 * definitions of squareList.
 *
 *    def squareList(xs: List[Int]): List[Int] = xs match {
 *      case List() => ??
 *      case y :: ys => ??
 *    }
 *
 *    def squareList(xs: List[Int]): List[Int] = xs map ??
 */

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


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

 

 

/**
 * Exercise 9.4.2 Consider the problem of writing a function flatten, which
 * takes a list of element lists as arguments. The result of flatten should be
 * the concatenation of all element lists into a single list. Here is an
 * implementation of this method in terms of :\.
 *
 * def flatten[A](xs: List[List[A]]): List[A] =
 *   (xs :\ (Nil: List[A])) {(x, xs) => x ::: xs}
 * 
 * Consider replacing the body of flatten by
 *
 *        ((Nil: List[A]) /: xs) ((xs, x) => xs ::: x)
 *
 * What would be the difference in asymptotic complexity between the two
 * versions of flatten?
 * 
 * In fact flatten is predefined together with a set of other userful function
 * in an object called List in the standatd Scala library. It can be accessed
 * from user program by calling List.flatten. Note that flatten is not a method
 * of class List - it would not make sense there, since it applies only to
 * lists of lists, not to all lists in general.
 */

/*
  In fact, the use of {} vs () doesn't make sintatic or semantic difference.
  In curry model of Scala, both the foldLeft /: and foldRight :\ methods
  define the function as second curry parammeter. So, the version of function
  that use /: can be writen like :\
*/
def flattenRight[A](xs: List[List[A]]): List[A] =
  (xs :\ (Nil: List[A])) {(x, xs) => x ::: xs}

/*
  Note that is the same function, just changing the application of flatten
  function. So, there's no difference in asymptotic complexity between the
  two implementation.
*/

 

 

/**
 * Exercise 9.4.3 Fill in the missing expressions to complete the following
 * definitions of some basic list-manipulation operations as fold operations.
 *
 * def mapFun[A, B](xs: List[A], f: A => B): List[B] =
 *   (xs :\ List[B]()){ ?? }
 *
 * def lengthFun[A](xs: List[A]): int =
 *   (0 /: xs){ ?? }
 */

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

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