PFDS_Exercise_2.1.scala

/** 
* THE FOLLOWING EXERCISE IS FROM (THE SAMPLE OF) "PURELY FUNCTIONAL DATA STRUCTURES"
* http://www.amazon.com/Purely-Functional-Structures-Chris-Okasaki/dp/0521663504/ref=sr_1_1?s=books&ie=UTF8&qid=1282766033&sr=1-1
*
* Exercise 2.1
* 
* Write a function suffixes of type a list -> a list list that takes 
* a list xs and returns a list of all the suffixes of xs in decreasing
* order of length. For example: 
* 
* suffixes [1,2,3,4] = [[1,2,3,4],[2,3,4],[3,4],[]]
* 
* Q1 : Show that the resulting list of suffixes can be generated in O(n) time 
* Q2 : and represented in O(n) space.
* 
**/

package com.sidewayscoding.exercises

object exercise2_1 {

  // the implementation
  def suffixes(xs: List[Int]): List[List[Int]] = xs match {
    case Nil => xs :: Nil
    case head :: xy => xs :: suffixes(xy)
  }
  
  // just to test it works
  def main(args: Array[String]): Unit = {
    val xs = List(1,2,3,4)
    println( suffixes(xs) )
  }
  
  // A1 : it only runs through the list xs once, hence it's running time is O(n)
  // A2 : It only creates one new list for each element in the list xs so it's O(n)
}