// Lists
//
// Chapter 9, Part 2,  Scala Programming by Example
//

// "higher-order" stuff
//
// transforming every element
// selecting some elements
// combining elements

// who has heard of Google's map-reduce?


// tedious write the same code all the time (and it is not even tail-recursive)

def scaleList(xs: List[Double], factor: Double): List[Double] = xs match {
  case Nil => xs
  case x :: xs1 => x * factor :: scaleList(xs1, factor)
}



def map(f: Double => Double, l: List[Double]): List[Double] = l match {
  case Nil => Nil
  case x :: xs => f(x) :: map(f,xs)
}



def scaleList(xs: List[Double], factor: Double) =
  xs map (x => x * factor)


def foreach(l: List[String], f: String => Unit) {
  l match {
    case Nil => ()
    case x :: xs => f(x); xs foreach f  
  }
}


//======================================================================

// some exercise, fill in the ??

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

def squareList_2(xs: List[Int]): List[Int] = 
  xs map ?? 


//======================================================================

// filtering: collecting all positive ints
def posElems(xs: List[Int]): List[Int] = xs match { 
  case Nil => xs 
  case x :: xs1 => if (x > 0) x :: posElems(xs1) else posElems(xs1) 
} 

// generalize

def filter(p: A => Boolean): List[A] = this match { 
  case Nil => this 
  case x :: xs => if (p(x)) x :: xs.filter(p) else xs.filter(p) 
} 

// rewrite posElems
def posElems(xs: List[Int]): List[Int] = 
 xs filter (x => x > 0) 

//======================================================================

def forall(p: A => Boolean, l: List[A]): Boolean = 
  l.isEmpty || (p(l.head) && (l.tail forall p)) 

def exists(p: A => Boolean, l: List[A]): Boolean = 
  !l.isEmpty && (p(l.head) || (l.tail exists p))

//======================================================================

def isPrime(n: Int) = 
  List.range(2, n) forall (x => n % x != 0) 


// compare the two following results:

val m1 = List(1,2,3).map( x => List.range(1,x*x))

val m2 = List(1,2,3).flatMap( x => List.range(1,x*x))


* //======================================================================
// reducing lists
//======================================================================


// sum all elements of a list ...
def sum(xs: List[Int]): Int = xs match { 
  case Nil => 0 
  case y :: ys => y + sum(ys) 
} 

// multiply all elements of a list ...
def product(xs: List[Int]): Int = xs match { 
  case Nil => 1 
  case y :: ys => y * product(ys) 
}


// again generalize
def foldLeft[A,B](l: List[A], z: B)(op: (B, A) => B): B = l match {
  case Nil => z
  case x :: xs => foldLeft(xs, op(z, x)) (op)
}


def sum(xs: List[Int]) = foldLeft(xs, 0) {(x, y) => x + y} 
def product(xs: List[Int]) = foldLeft(xs, 1) {(x, y) => x * y} 


def flatMap[A,B](l: List[A], op: (A => List[B])): List[B] =
  ff( l, Nil: List[B]) ((x,y) => x ++ y)


// some more list magic

List.range(1, 10) 
.map(i => List.range(1, i).map(x => (i, x))) 
.foldRight(List[(Int, Int)]()) {(xs, ys) => xs ::: ys} 
.filter(pair => isPrime(pair._1 + pair._2))