chapter3.scala

import scala.annotation._

object chapter3 {

	/**
	  * PATTERN MATCHING
	  */

	val foo = (1, 2)

	val bar = foo match {
		case (a, b) if (a > 5) => a + b
		case (a, b) => a * b
		case _ => 0
	}

	/**
	  * SINGLY LINKED LIST
	  */

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

	// companion object to enable creation of lists by writing 
	// List(1, 2, 3) instead of Cons(1, Cons(2, Cons(3, Nil)))
	object List {
		def apply[A](as: A*): List[A] = {
			@tailrec
			def apply0(orig: Seq[A], acc: List[A]): List[A] =
				if (orig.isEmpty) acc
				else apply0(orig.tail, Cons(orig.head, acc))

			apply0(as.reverse, Nil)
		}
	}

	val l = Cons(1, Cons(2, Cons(3, Nil)))
	val l2 = Cons(1, Nil)
	val l3 = Nil

	val x = List(1,2,3,4,5) match {
		case Cons(x, Cons(2, Cons(4, _))) => x
		case Nil => 42
		case Cons(x, Cons(y, Cons(3, Cons(4, _)))) => x + y
		case Cons(h, t) => h + sum(t)
		case _ => 101
	}

	def tail[A](l: List[A]): List[A] = l match {
		case Nil => error("empty list")
		case Cons(h, t) => t
	}

	def setHead[A](l: List[A], nh: A): List[A] = l match {
		case Nil => Cons(nh, Nil)
		case Cons(h, t) => Cons(nh, t)
	}

	def drop[A](l: List[A], n: Int): List[A] = l match {
		case Nil => Nil
		case Cons(h, t) =>
			if (n > 0) drop(t, n - 1)
			else l
	}

	def tail2[A](l: List[A]): List[A] = drop(l, 1)

	def dropWhile[A](l: List[A], f: A => Boolean): List[A] = l match {
		case Nil => Nil
		case Cons(h, t) =>
			if (f(h)) dropWhile(t, f)
			else l
	}

	def init[A](l: List[A]): List[A] = l match {
		case Nil => Nil
		case Cons(h, Nil) => Nil
		case Cons(h, t) => Cons(h, init(t))
	}

	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(x,xs) => x * product(xs)
	}

	/**
	  * FOLDS
	  */

	// generalizing the sum and product functions
	
	def foldRight[A, B](as: List[A], zero: B)(fn: (A, B) => B): B = as match {
		case Nil => zero
		case Cons(head, tail) => fn(head, foldRight(tail, zero)(fn))
	}

	def sum2(ints: List[Int]): Int = foldRight(ints, 0)(_ + _)

	def product2(ds: List[Double]): Double = foldRight(ds, 1.0)(_ * _)
	
	// going from left to right - the tail recursive fold

	@tailrec
	def foldLeft[A, B](as: List[A], zero: B)(fn: (B, A) => B): B = as match {
		case Nil => zero
		case Cons(head, tail) => foldLeft(tail, fn(zero, head))(fn)
	}

	/**
	  * zero: 0, list: List(1,2,3)
	  * zero: 0, list: Cons(1, Cons(2, Cons(3, Nil)))
	  *
	  * foldLeft:  fn(fn(fn(0, 1), 2), 3)
	  *
	  *         fn
	  *        /  \
	  *      fn    3
	  *     /  \
	  *   fn    2
	  *  /  \
	  * 0    1
	  *
	  *
	  * foldRight: fn(1, fn(2, fn(3, 0)))
	  *
	  *   fn
	  *  /  \
	  * 1    fn
	  *     /  \
	  *    2    fn
	  *        /  \
	  *       3    0
	  *
	  */

	def foldRightViaFoldLeft[A, B](as: List[A], zero: B)(fn: (A, B) => B): B =
		foldLeft(reverse(as), zero)((b, a) => fn(a, b))

	def foldLeftViaFoldRight[A, B](as: List[A], zero: B)(fn: (B, A) => B): B =
		foldRight(as, (b: B) => b)((a, g) => b => g(fn(b, a)))(zero)

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

	def reverse[A](list: List[A]): List[A] =
		foldLeft(list, Nil: List[A])( (b: List[A], a: A) => Cons(a, b) )

	def reverseRight[A](list: List[A]): List[A] =
		foldRight(list, Nil: List[A])( (a: A, b: List[A]) => append(b, List(a)) )

	def append[A](left: List[A], right: List[A]): List[A] =
		foldRight(left, right)(Cons(_, _))
		
	// btw can you do append using foldLeft?

	def concat[A](lol: List[List[A]]): List[A] =
		foldLeft(lol, Nil: List[A])( (acc: List[A], a: List[A]) => append(acc, a) )
		
	def addOne(list: List[Int]): List[Int] = foldRight(list, Nil: List[Int])((n, acc) => Cons(n + 1, acc))

	def doubleToString(list: List[Double]): List[String] = foldRight(list, Nil: List[String])((d, acc) => Cons(d.toString, acc))

	def map[A,B](list: List[A])(f: A => B): List[B] = foldRight(list, Nil: List[B])((a, acc) => Cons(f(a), acc))

	def filter[A](list: List[A])(f: A => Boolean): List[A] = foldRight(list, Nil: List[A])((a, acc) => if (f(a)) Cons(a, acc) else acc)

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

	def filter2[A](list: List[A])(f: A => Boolean): List[A] = flatMap(list)(a => if (f(a)) Cons(a, Nil) else Nil)

	def addLists(left: List[Int], right: List[Int]): List[Int] = (left, right) match {
		case (Cons(lh, lt), Cons(rh, rt)) => Cons(lh + rh, addLists(lt, rt))
		case _ => Nil
	}

	def zipWith[A, B, C](left: List[A], right: List[B])(f: (A, B) => C): List[C] = (left, right) match {
		case (Cons(lh, lt), Cons(rh, rt)) => Cons(f(lh, rh), zipWith(lt, rt)(f))
		case _ => Nil
	}

}