// Lists
//
//  immutable, but
//  flexible recursive structure
//  rich set of predefined ops
//

// like arrays (and like tupels) lists are homogeneous

val fruit: List[String] = List("apples", "oranges", "pears")
val nums : List[Int] = List(1, 2, 3, 4)
val diag3: List[List[Int]] = List(List(1, 0, 0), List(0, 1, 0), List(0, 0, 1))
val empty: List[Int] = List()

// "constructor"   ::

val fruit = "apples" :: ("oranges" :: ("pears" :: Nil))
val nums = 1 :: (2 :: (3 :: (4 :: Nil)))
val diag3 = (1 :: (0 :: (0 :: Nil))) ::
  (0 :: (1 :: (0 :: Nil))) ::
  (0 :: (0 :: (1 :: Nil))) :: Nil
val empty = Nil

// right-associative -> can drop parenthesis

val nums1 = 1 :: 2 :: 3 :: 4 :: Nil

// basic ops:
//  head
//  tail
//  isEmpty

/*
empty.isEmpty = true
fruit.isEmpty = false
fruit.head = "apples"
fruit.tail.head = "oranges"
diag3.head = List(1, 0, 0)
*/

// insertion sort ...

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)
}


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


def length(l: List[Int]): Int = l match {
  case Nil => 0
  case x :: xs => 1 + length(xs)
}

// can you do a tail-recursive version ...



def last(l: List[Int]): Int = l match {
  case Nil => error("Nil.last")
  case x :: Nil => x
  case x :: xs => last(xs)
}



def take(l: List[Int], n: Int): List[Int] =
  if (n == 0 || l.isEmpty) Nil else l.head :: take(l.tail,n-1)

def drop(l: List[Int], n: Int): List[Int] =
  if (n == 0 || l.isEmpty) l else drop(l.tail,n-1)

def split(l: List[Int], n: Int): (List[Int], List[Int]) = (take(l,n), drop(l,n))


def subList(l: List[Int], from: Int, to: Int): List[Int] = take( drop(l,from), to-from)



def zip(l1: List[Int], l2: List[Int]): List[(Int,Int)] = {
  if (l1.isEmpty || l2.isEmpty) Nil
  else (l1.head, l2.head) :: (l1.tail zip l2.tail)
}


//  concatenate (or append) lists using :::

// reversing a list

def reverse(xs: List[Int]): List[Int] = xs match {
  case Nil => Nil
  case x :: xs => reverse(xs) ::: List(x)
}

// this is O(n^2), can you do a linear version ???

def msort[Int](less: (Int, Int) => Boolean)(xs: List[Int]): List[Int] = {
  def merge(xs1: List[Int], xs2: List[Int]): List[Int] =
    if (xs1.isEmpty) xs2
    else if (xs2.isEmpty) xs1
    else if (less(xs1.head, xs2.head)) xs1.head :: merge(xs1.tail, xs2)
    else xs2.head :: merge(xs1, xs2.tail)
  val n = xs.length/2
  if (n == 0) xs
  else merge(msort(less)(xs take n), msort(less)(xs drop n))
}


val intSort = msort((x: Int, y: Int) => x < y) _
val reverseSort = msort((x: Int, y: Int) => x > y) _