/** * 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} |