/*  Functional Programming in Scala (Red Book)
    Chapter 3, Functional Data Structures
    Adapted and extended code
    H. Conrad Cunningham

1234567890123456789012345678901234567890123456789012345678901234567890

2016-04-14: Adapted from Red Book code (Feb-Apr 2016)
2019-02-09: Updated comments
2019-03-06: Changed function tail to tailList, added headList
*/

// import scala.{List => _, _} // hide standard?

sealed trait List[+A]
case object Nil extends List[Nothing] 
case class Cons[+A](head: A, tail: List[A]) extends List[A]

object List {

  def sum(ints: List[Int]): Int = ints match {
    case Nil        => 0 
    case Cons(x,xs) => x + sum(xs)
  }

  def product(ds: List[Double]): Double = ds match {
    case Nil          => 1.0
    case Cons(0.0, _) => 0.0
    case Cons(x,xs)   => x * product(xs)
  }

  def remdups[A](ls: List[A]): List[A] = ls match {
    case Cons(x, Cons(y,ys)) =>
      if (x == y)
        remdups(Cons(y,ys))         // duplicate
      else
        Cons(x,remdups(Cons(y,ys))) // non-duplicate
    case _                   => ls
  }

  def apply[A](as: A*): List[A] = 
    if (as.isEmpty) 
      Nil 
    else 
      Cons(as.head, apply(as.tail: _*)) 

  def headList[A](ls: List[A]): A = ls match {
    case Nil       => sys.error("head of empty list")
    case Cons(x,_) => x
  }
 
  def tailList[A](ls: List[A]): List[A] = ls match {
    case Nil        => sys.error("tail of empty list")
    case Cons(_,xs) => xs
  }
 
  def drop[A](ls: List[A], n: Int): List[A] =
    if (n <= 0) ls
    else ls match {
      case Nil        => Nil
      case Cons(_,xs) => drop(xs, n-1)
    }

  def append[A](ls: List[A], rs: List[A]): List[A] = ls match {
    case Nil        => rs
    case Cons(x,xs) => Cons(x, append(xs, rs))
  }

  def rev[A](ls: List[A]): List[A] = ls match {
    case Nil        => Nil
    case Cons(x,xs) => append(rev(xs),List(x))
  }
  
  def reverse[A](ls: List[A]): List[A] = {
    def revAux[A](rs: List[A], as: List[A]): List[A] = rs match {
      case Nil        => as
      case Cons(x,xs) => revAux(xs,Cons(x,as))
    }
    revAux(ls,Nil)
  }

  def dropWhile [A](ls: List[A], f: A => Boolean): List[A] =
    ls match {
      case Cons(x,xs) if f(x) => dropWhile(xs, f)
      case _                  => ls
    }

  def dropWhile2[A](ls: List[A])(f: A => Boolean): List[A] =
    ls match {
      case Cons(x,xs) if f(x) => dropWhile2(xs)(f)
      case _                  => ls
    }

  def foldRight[A,B](ls: List[A], z: B)(f: (A, B) => B): B = 
    ls match {
      case Nil        => z
      case Cons(x,xs) => f(x, foldRight(xs, z)(f))
    }

  def sum2(ns: List[Int]) =
    foldRight(ns, 0)((x,y) => x + y)

  def product2(ns: List[Double]) =
    foldRight(ns, 1.0)(_ * _)

  def length[A](ls: List[A]): Int =
    foldRight(ls, 0)((_,acc) => acc + 1)

  def append2[A](ls: List[A], rs: List[A]): List[A] =
    foldRight(ls, rs)(Cons(_,_))

  def concat[A](ls: List[List[A]]): List[A] =
    foldRight(ls, Nil: List[A])(append) 

  @annotation.tailrec
  def foldLeft[A,B](ls: List[A], z: B)(f: (B, A) => B): B = ls match {
    case Nil        => z
    case Cons(x,xs) => foldLeft(xs, f(z,x))(f)
  }

  def sum3(ns: List[Int]) =
    foldLeft(ns, 0)(_ + _)

  def product3(ns: List[Double]) =
    foldLeft(ns, 1.0)(_ * _)

  def length2[A](ls: List[A]): Int =
    foldLeft(ls, 0)((acc,_) => acc + 1)

  def reverse2[A](ls: List[A]): List[A] =
    foldLeft(ls, List[A]())((acc,x) => Cons(x,acc))

  def foldRight2[A,B](ls: List[A], z: B)(f: (A,B) => B): B =
    foldLeft(reverse(ls), z)((b,a) => f(a,b))

  def squareAll(ns: List[Int]): List[Int] = ns match {
    case Nil         => Nil
    case Cons(x, xs) => Cons(x*x, squareAll(xs))
  } 

  def lengthAll[A](lss: List[List[A]]): List[Int] =
    lss match {
      case Nil          => Nil
      case Cons(xs,xss) => Cons(length(xs),lengthAll(xss))
    }
  
  def map[A,B](ls: List[A])(f: A => B): List[B] = ls match {
    case Nil       => Nil
    case Cons(x,xs) => Cons(f(x),map(xs)(f))
  }

  def squareAll2(ns: List[Int]): List[Int] =
    map(ns)(x => x*x)

  def lengthAll2[A](lss: List[List[A]]): List[Int] =
    map(lss)(length)

  def map1[A,B](ls: List[A])(f: A => B): List[B] =
    foldRight(ls, Nil: List[B])((x,xs) => Cons(f(x),xs))

  def map2[A,B](ls: List[A])(f: A => B): List[B] = {
    val buf = new collection.mutable.ListBuffer[B]

    @annotation.tailrec
    def go(ls: List[A]): Unit = ls match {
      case Nil        => ()
      case Cons(x,xs) => buf += f(x); go(xs)
    }
    
    go(ls)
    List(buf.toList: _*) 
  }

  def getEven(ns: List[Int]): List[Int] = ns match {
    case Nil        => Nil
    case Cons(x,xs) =>
      if (x % 2 == 0)  // divisible evenly by 2
        Cons(x,getEven(xs))
      else
        getEven(xs)
    }

  def doublePos(ns: List[Int]): List[Int]  = ns match {
    case Nil        => Nil
    case Cons(x,xs) =>
      if (0 < x)
        Cons(2*x, doublePos(xs))
      else
        doublePos(xs)
  }

  def filter[A](ls: List[A])(p: A => Boolean): List[A] =
    ls match {
      case Nil        => Nil
      case Cons(x,xs) =>
    val fs = filter(xs)(p)
    if (p(x)) Cons(x,fs) else fs
  }

  def getEven2(ns: List[Int]): List[Int] =
    filter(ns)(x => x % 2 == 0)

  def doublePos2(ns: List[Int]): List[Int] =
    map(filter(ns)(x => 0 < x))(y => 2 * y)

  def filter1[A](ls: List[A])(p: A => Boolean): List[A] =
    foldRight(ls, Nil:List[A])((x,xs) => if (p(x)) Cons(x,xs) else xs)

  def flatMap[A,B](ls: List[A])(f: A => List[B]): List[B] =
    concat(map(ls)(f))

  def flatMap1[A,B](ls: List[A])(f: A => List[B]): List[B] =
    foldRight(ls, Nil: List[B])(
             (x: A, ys: List[B]) => append(f(x),ys))

  def filter2[A](ls: List[A])(p: A => Boolean): List[A] =
    flatMap(ls)(x => if (p(x)) List(x) else Nil)

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

  def insert(x: Int, xs: List[Int]): List[Int] = xs match {
    case Nil        => List(x)
    case Cons(y,ys) =>
      if (x <= y)
        Cons(x,xs)
      else
        Cons(y,insert(x,ys))
  }

  def isort1[A <% Ordered[A]](ls: List[A]): List[A] = ls match {
    case Nil        => Nil
    case Cons(x,xs) => insert1(x,isort1(xs))
  }

  def insert1[A <% Ordered[A]](x: A, xs: List[A]): List[A] =
    xs match {
      case Nil=> List(x)
      case Cons(y,ys) =>
        if (x <= y)
          Cons(x,xs)
        else
         Cons(y,insert1(x,ys))
    }

    def isort2[A](ls: List[A])(leq: (A,A) => Boolean): List[A] =
      ls match {
        case Nil        => Nil
        case Cons(x,xs) => insert2(x,isort2(xs)(leq))(leq)
      }

  def insert2[A](x:A, xs:List[A])(leq:(A,A)=>Boolean):List[A] =
    xs match {
      case Nil=> List(x)
      case Cons(y,ys) =>
        if (leq(x,y))
          Cons(x,xs)
        else
          Cons(y,insert2(x,ys)(leq))
      }

  def msort[A](less: (A, A) => Boolean)(ls: List[A]): List [A] = {

  def merge(as: List[A], bs: List[A]): List[A] = (as,bs) match {
    case (Nil,_)                 => bs
    case (_,Nil)                 => as
    case (Cons(x,xs),Cons(y,ys)) =>
      if (less(x,y))
        Cons(x,merge(xs,bs))
      else
        Cons(y,merge(as,ys))
  }

  val n = length(ls)/2
  if (n == 0)
    ls
  else
    merge(msort(less)(take(ls,n)), msort(less)(drop(ls,n)))
  }

  def take[A](ls: List[A], n: Int): List[A] = 
    if (n <= 0) Nil
    else ls match {
      case Nil        => Nil
      case Cons(x,xs) => Cons(x,take(xs, n-1))
    }

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

}