import scala.math.abs

def sqrt(x: Double): Double = {
	// Nest helper functions in block to reduce namespace pollution
	// We don't need to pass constant x to any of these helper functions!
	def sqrtIter(guess: Double): Double =
		if (isGoodEnough(guess)) guess else sqrtIter(improve(guess))

	// Divide by x in order to scale for very small/large values for guess
	def isGoodEnough(guess: Double) =
		abs((guess * guess) - x) / x < 0.001

	def improve(guess: Double) =
		(x / guess + guess) / 2

	// Always guess 1.0
	sqrtIter(1.0, x)
}

// Tail recursive
def gcd(a: Int, b: Int): Int =
	if (b == 0) a else gcd(b, a % b)

// NOT tail recursive, since we have to multiply by n after calling factorial
def factorial(n: Int): Int =
	if (n == 0) 1 else n * factorial(n - 1)

// Tail recursive
def factorialTR(n: Int): Int = {
	def loop(acc: Int, n: Int): Int
		if (n == 0) acc else loop(acc * n, n - 1)
	loop(1, n)
}

// A higher order function
// f: Int => Int means a function f with parameter Int that returns Int
def sum(f: Int => Int, a: Int, b: Int): Int = {
	def loop(a: Int, acc: Int): Int = {
		if (a > b) acc
		else loop(a + 1, acc + f(a))
	}
	loop(a, 0)
}

def id(x: Int): Int = x
def cube(x: Int): Int = x * x * x
def factorial(n: Int): Int = if (n == 0) 1 else n * factorial(n - 1)

// Or, use anonymous function syntactic sugar; x => x
def sumInts(a: Int, b:Int) = sum(id, a, b)
// Or, use anonymous function syntactic sugar; x => x * x * x
def sumCubes(a: Int, b: Int) = sum(cube, a, b)
def sumFactorials(a: Int, b: Int) = sum(factorial, a, b)

// Syntactic sugar for function returning functions
// Its type is (Int => Int) => ((Int, Int) => Int)
def sum(f: Int => Int)(a: Int, b: Int): Int =
	if (a > b) 0 else f(a) + sum(f)(a + 1, b)

// Then, we can define w/o (a, b) and use these like sumCubes(1, 10) as before
def sumInts = sum(x => x)
def sumCubes = sum(x => x * x * x)
def sumFactorials = sum(factorial)

// Or, use the general function directly
sum(cube)(1, 10)

def product(f: Int => Int)(a: Int, b: Int): Int =
	if (a > b) 1 else f(a) * product(f)(a + 1, b)

def factorial(n: Int) = product(x => x)(1, n)

// f => map function to apply to each element
// combine => reduce elements after mapping
// zero => value to return if the range is empty
def mapReduce(f: Int => Int, combine: (Int, Int) => Int, zero: Int)(a: Int, b: Int): Int =
	if (a > b) zero else combine(f(a), mapReduce(f, combine, zero)(a + 1, b))

def product = mapReduce(f, (x, y) => x * y, 1)(a, b)
def sum = mapReduce(f, (x, y) => x + y, 0)(a, b)

val tolerance = 0.0001

def isCloseEnough(x: Double, y: Double) =
	abs((x - y) / x) / x < tolerance

def fixedPoint(f: Double => Double)(firstGuess: Double) = {
	def iterate(guess: Double): Double = {
		val next = f(guess)
		if (isCloseEnough(guess, next)) next
		else iterate(next)
	}
	iterate(firstGuess)
}

// Find the fixed point of f(x) = 1 + x / 2
fixedPoint(x => 1 + x/2)(1)

def sqrt(x: Double) = fixedPoint(y => x / y)(1)

// Unfortunately, this doesn't converge (guesses oscillate between 1 and 2)
sqrt(2)

// To fix this, we can average our last guess (y) and the current guess (x/y)
def sqrt(x: Double) = fixedPoint(y => (y + x / y) / 2)(1)

// Stabilizing by averaging can be written in general as:
def averageDamp(f: Double => Double)(x: Double) = (x + f(x)) / 2

// Using this in sqrt, we have
def sqrt(x: Double) = fixedPoint(averageDamp(y => x / y))(1)

// Implicit primary constructor
class Rational(x: Int, y: Int) {

	require(y != 0, "denominator must be nonzero")

	// Alternate constructor
	def this(x: Int) = this(x, 1)

	private def gcd(a: Int, b: Int): Int = if (b == 0) a else gcd(b, a % b)

	// We could also simplify only at print time, but we could run into overflow
	def numer = x / gcd(x, y)
	def denom = y / gcd(x, y)

	def < (that: Rational) = numer * that.denom < that.numer * denom

	def max(that: Rational) = if (this < that) that else this

	def + (that: Rational) =
		new Rational(
			numer * that.denom + that.numer * denom,
			denom * that.denom
		)

	def unary_- : Rational = new Rational(-numer, denom)

	def - (that: Rational) = this + -that

	override def toString = numer + "/" + denom
}

val x = new Rational(1, 2)
x.numer // 1
x.denom // 2

val y = new Rational(2, 3)
x + y // 7/6

val strange = new Rational(1, 0) // IllegalArgumentException from require

new Rational(1, 2).numer
// [1/x, 2/y][][new Rational(1, 2) / this] x
//  --------- substitute class parameters x and y
//           -- substitute function parameters for numer
//             --------------------------- sustitute this for Rational object
//                                         - function body

// Evaluation:
// = 1

new rational(1, 2).less(new Rational(2, 3))
// [1/x, 2/y][new Rational(2, 3) / that][new Rational(1, 2) / this]
// this.numer * that.denom < that.numer * this.denom

// Evaluation:
// = new Rational(1, 2).numer * new Rational(2, 3).denom <
//   new Rational(2, 3).numer * new Rational(1, 2).denom
// = 1 * 3 < 2 * 2
// = true

r max s === r.max(s)

// Evaluation of precendence example:
(a + b ^? c ?^ d less a ==> b | c) === (

((a + b) ^? (c ?^ d)) less ((a ==> b) | c)

)

abstract class IntSet {
	def contains(x: Int): Boolean
	def incl(x: Int): IntSet
	def union(other: IntSet): IntSet
}

// Let's implement IntSet as a binary tree

// object keyword => singleton value, since all instances of Empty are the same
object Empty extends IntSet {
	def contains(x: Int): Boolean = false
	def incl(x: Int): Intset = new NonEmpty(x, Empty, Empty) // not `new Empty`
	def union(other: IntSet): IntSet = other
	override def toString = "."
}

// NonEmpty has the base classes IntSet and Object
// Object is a default base class for all user-defined classes, like in Java
class NonEmpty(elem: Int, left: IntSet, right: IntSet) extends IntSet {
	def contains(x: Int): Boolean =
		if (x < elem) left contains x
		else if (x > elem) right contains x
		else true

	def incl(x: Int): IntSet =
		if (x < elem) new NonEmpty(elem, left incl x, right)
		else if (x > elem) new NonEmpty(elem, left, right incl x)
		else this

	// this terimnates because each call to union is on a set that is smaller
	def union(other: IntSet): IntSet = ((left union right) union other) incl elem

	// You cannot override a base class method without the override keyword
	// Using override without a base class method being overriden is legal, but
	// gives a warning
	override def toString = "{" + left + elem + right + "}"
}

package profun.examples

import week3.IntSet // import IntSet from week 3
import week2.{Rational, FunSet} // import 2 things from week 2
import week1._ // import everything from week 1

// places Hello in the pacakge "profun.examples"
object Hello {
	// run in cmdline with `scala profun.examples.Hello`
	def main(args: Array[String]) = println("hello world!")
}

// Traits cannot have value parameters, unlike classes
trait Planar {
	// Can contain fields and concrete methods
	def height: Int
	def width: Int
	def surface = height * width
}

class Square extends Shape with Planar with Movable ...

if (true) 1 else false // expression has type AnyVal

List(1, 2, 3)
/**
is represented as:
[]
| \
1 []
  | \
  2  []
     | \
     3  Nil
**/
List(List(true, false), List(3))
/**
is represented as:
  []
 /  \_________
[]            []
| \           | \
1 []          []  Nil
  | \         | \
  0  Nil      3  Nil
**/

trait List[T] {
	def isEmpty: Boolean
	def head: T
	def tail: List[T]
}

// use of "val" in the constructor defines fields `head` and `tail`
// this also implements `def head` and `def tail` in the trait List[T]
class Cons[T](val head: T, val tail: List[T]) extends List[T] {
	def isEmpty = false
}

class Nil extends List[T] {
	def isEmpty = true
	// Nothing is a subtype of T, so this definition works
	def head: Nothing = throw new NoSuchElementException("Nil.head")
	def tail: Nothing = throw new NoSuchElementException("Nil.tail")
}

def singleton[T](elem: T) = new Cons[T](elem, new Nil[T])

// use as:
singleton[Int](1)
singleton(true) // Scala compiler infers T as Boolean

// 0 index => 1st element
def nth[T](n: Int, xs: List[T]): T =
	if(xs.isEmpty) throw new IndexOutOfBoundsException
	else if(n == 0) xs.head
	else nth(n - 1, xs.tail)

val list = new Cons(1, new Cons(2, new Cons(3, new Nil)))
nth(2, list) // 3
nth(-1, list) // IndexOutOfBoundsException

package idealized.scala

abstract class Boolean {
	// if (cond) t else e === cond.ifThenElse(t, e)
	def ifThenElse[T](t: => T, e: => T): T

	// cond && x === if (cond) then x else false
	def &&(x: => Boolean): Boolean = ifThenElse(x, false)
	def ||(x: => Boolean): Boolean = ifThenElse(true, x)
	def unary_!: Boolean = ifThenElse(false, true)

	def ==(x: Boolean): Boolean = ifThenElse(x, x.unary_!)
	def !=(x: Boolean): Boolean = ifThenElse(x.unary_!, x)
	// Assume false < true
	def <(x: Boolean): Boolean = ifThenElse(false, x)
}

object true extends Boolean {
	// if (true) t else e === t
	def ifThenElse[T](t: => T, e: => T): t
}

object false extends Boolean {
	// if (false) t else e === e
	def ifThenElse[T](t: => T, e: => T): e
}

class Int {
	// method overloading is allowed, as in Java
	def + (that: Double): Double
	def + (that: Float): Float
	def + (that: Long): Long
	def + (that: Int): Int // same for -, *, /, %

	def << (cnt: Int): Int // same for >>

	def & (that: Long): Long
	def & (that: Int): Int // same for |, ^

	def == (that: Double): Boolean
	def == (that: Float): Boolean
	def == (that: Long): Boolean // same for !=, <, >, <=, >=
}

// Natural number class (simplified Int class)
abstract class Nat {
	def isZero: Boolean
	def predecessor: Nat // returns the previous natural number before this
	def successor: Nat = new Succ(this) // returns the next natural number after this
	def + (that: Nat): Nat
	def - (that: Nat): Nat
}

object Zero extends Nat {
	def isZero: Boolean = true
	def predecessor: Nat = throw new Error("0.predecessor")
	def + (that: Nat): Nat = that
	def - (that: Nat): Nat = if (that.isZero) this else throw new Error("negative number")
}

class Succ(n: Nat) extends Nat {
	def isZero: Boolean = false
	def predecessor: Nat = n
	def + (that: Nat): Nat = new Succ(n + that)
	// 5 - 2 => 4 - 1 => 3 - 0 => 3
	def - (that: Nat): Nat = if (that.isZero) this else n - that.predecessor
}

package scala

// Function2, Function3 ... Function22 also exist to take more parameters
trait Function1[A, B] {
	def apply(x: A): B
}

// We can write `def f(x: Int) => x * x` by eta-expansion as:
val f1 = {
	class AnonFun extends Function1[Int, Int] {
		def apply(x: Int) = x * x
	}
	new AnonFun
}
// or, using anonymous class syntax (also in Java):
val f2 = new Function1[Int, Int] {
	// Notice, the apply method itself is not a function object, because that
	// would be an infinite recursive definition
	def apply(x: Int) = x * x
}
// Then, f(7) would be
f2.apply(7)

trait List[T] {
	def isEmpty: Boolean
	def head: T
	def tail: List[T]
}

class Cons[T](val head: T, val tail: List[T]) extends List[T] {
	def isEmpty = false
}

class Nil extends List[T] {
	def isEmpty = true
	def head: Nothing = throw new NoSuchElementException("Nil.head")
	def tail: Nothing = throw new NoSuchElementException("Nil.tail")
}

object List {
	def apply[T](x1: T, x2: T): List[T] = new Cons(x1, new Cons(x2, new Nil))
	def apply[T](x: T): List[T] = new Cons(x, new Nil)
	def apply[T]() = new Nil
}

// This lets us instantiate lists up to length 2
List() // the empty list
List(1) // list with single element 1
List(2, 3) // list with elements 2, 3

def assertAllPos(s: IntSet): IntSet

// S <: T means that S is a subtype of T, T is an upper bound of type S
// S >: T would mean that S is a supertype of T
// So, assertAllPos takes a subtype of IntSet and returns it
def assertAllPos(S <: IntSet)(r: S): S

// If assertAllPos threw an exception if the set was empty, we could write:
def assertNotEmptyAndAllPos(S >: NonEmpty <: IntSet)(r: S): S

val a: Array[NonEmpty] = Array(new NonEmpty(1, Empty, Empty))
val b: Array[IntSet] = a
b(0) = Empty // notice b(0), because arrays are a form of method call in Scala
val s: NonEmpty = a(0)

type A = IntSet => NonEmpty
type B = NonEmpty => IntSet

package scala
trait Function1[-T, +U] {
	def apply(x: T): U
}

// A Java covariant array would look something like this
class Array[+T] {
	// Impossible, since T is method parameter which is covariant
	def update(x: T) // ...
}

// Covariance is necessary so that List[Nothing] <: List[T]
trait List[+T] {
	def isEmpty: Boolean
	def head: T
	def tail: List[T]
	// covariant types can be lower bounds, contravariant types can be upper bounds
	def prepend [U >: T] (elem: U): List[U] = new Cons(elem, this)
}

class Cons[T](val head: T, val tail: List[T]) extends List[T] {
	def isEmpty = false
}

// use Nothing instead of T because objects cannot have type parameters
object Nil extends List[Nothing] {
	def isEmpty = true
	// Nothing == Nothing
	def head: Nothing = throw new NoSuchElementException("Nil.head")
	// Nothing <: List[Nothing]
	def tail: Nothing = throw new NoSuchElementException("Nil.tail")
}

object List {
	def apply[T](x1: T, x2: T): List[T] = new Cons(x1, new Cons(x2, new Nil))
	def apply[T](x: T): List[T] = new Cons(x, new Nil)
	def apply[T]() = new Nil
}

val x: List[String] = Nil

// f returns type List[IntSet] since in prepend,
// T would be NonEmpty and U would be empty
// But U >: T is false! So the type inferencer picks the lowest possible U, IntSet
def f(xs: List[NonEmpty], x: Empty) = xs prepend x

trait Expr {
	def isNumber: Boolean
	def isSum: Boolean
	def numValue: Int
	def leftOp: Expr
	def rightOp: Expr
}

class Number(n: Int) extends Expr {
	def isNumber: Boolean = true
	def isSum: Boolean = false
	def numValue: Int = n
	def leftOp: Expr = throw new Error("Number.leftOp")
	def rightOp: Expr = throw new Error("Number.rightOp")
}

class Sum(e1: Expr, e2: Expr) extends Expr {
	def isNumber: Boolean = false
	def isSum: Boolean = true
	def numValue: Int = throw new Error("Sum.numValue")
	def leftOp: Expr = e1
	def rightOp: Expr = e2
}

def eval(e: Expr): Int = {
	if (e.isNumber) e.numValue
	else if (e.isSum) eval(e.leftOp) + eval(e.rightOp)
	// We could have an expression which is not a number or a sum!
	else throw new Error("Unkown expression " + e)
}

// Using type tests and type casts, the Expr class could be empty
def eval(e: Expr): Int =
	if (e.istanceOf[Number])
		e.asInstanceOf[Number].numValue
	else if (e.instanceOf[Sum])
		eval(e.InstanceOf[Sum].leftOp) +
		eval(e.InstanceOf[Sum].rightOp)
	else
		throw new Error("Unkown expression " + e)

trait Expr {
	def eval: Int
}

class Number(n: Int) extends Expr {
	def eval: Int = n
}

class Sum(e1: Expr, e2: Expr) extends Expr {
	def eval: Int = e1.eval + e2.eval
}

trait Expr {
	// Now we can pull out the construction args using pattern matching
	// This eval only deals with Number and Sum
	def eval(e: Expr): Int = e match {
		case Number(n) => n
		case Sum(e1, e2) => e1.eval + e2.eval
		// MatchError exception if no pattern matches e
	}
}
case class Number(n: Int) extends Expr
case class Sum(e1: Expr, e2: Expr) extends Expr
case class Var(x: String) extends Expr
case class Prod(e1: Expr, e2: Expr) extends Expr

// the case keyword automatically creates these companion objects
object Number {
	def apply(n: Int) = new Number(n) // Number(1) === new Number(1)
}
object Sum {
	def apply(e1: Expr, e2: Expr) = new Sum(e1, e2)
}
object Var // ...
object Prod // ...

// Let's see an example evaluation of eval
Sum(Number(1), Number(2).eval
=== Sum(Number(1), Number(2)) match {
	case Number(n) => n
	case Sum(e1, e2) => e1.eval + e2.eval
}
=== Number(1).eval + Number(2).eval
=== Number(1) match {
	case Number(n) => n
	case Sum(e1, e2) => e1.eval + e2.eval
} + Number(2).eval
=== 1 + Number(2).eval
=== 1 + Number(2) match {
	case Number(n) => n
	case Sum(e1, e2) => e1.eval + e2.eval
}
=== 1 + 2
=== 3

// We can use pattern matching inside or outside of classes
def show(e: Expr): String = {
	def sumBrackets(ex: Expr): String = ex match {
		case Sum(e1, e2) => "(" + show(ex) + ")"
		case _ => show(ex) // default
	}

	e match {
		case Number(n) => n.toString
		case Sum(e1, e2) => show(e1) + " + " + show(e2)
		case Prod(e1, e2) => sumBrackets(e1) + " * " + sumBrackets(e2)
		case Var(x) => x
	}
}

val l = List("a", "b", "c")
val m = "a" :: ("b" :: ("c" :: Nil))
l === m
// all operators ending in : associate to the right
val n = "a" :: "b" :: "c" :: Nil
l === m === n
// all operators ending in : are seen as method calls of the right hand operand
val o = Nil.::(4).::(3).::(2).::(1)
l === l === n === o
// so :: can be thought of as a prepend method

// Insertion sort
def isort(xs: List[Int]): List[Int] = xs match {
	case List() => List()
	case y :: ys => insert(y, isort(ys))
}
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)
}

// O(N)
def last[T](xs: List[T]): T = xs match {
	case List() => throw new Error("last of empty list")
	case List(x) => x
	case y :: ys => last(ys)
}

// O(N)
def init[T](xs: List[T]): List[T] = xs match {
	case List() => throw new Error("init of empty list")
	case List(x) => List()
	case y :: ys => y :: init(ys)
}

// O(|xs|)
def concat[T](xs: List[T], ys: List[T]) = xs match {
	case List() => ys
	case z :: zs => z :: concat(zs, ys)
}

// O(N^2) => reverse(ys) takes 1 + 2 + ... + N = O(N) steps, and we iterate N times
def reverse[T](xs: List[T]): List[T] = xs match {
	case List() => List()
	case y :: ys => reverse(ys) ::: List(y)
}

def removeAt[T](xs: List[T], n: Int): List[T] = (xs take n) ::: (xs drop n + 1)

def flatten[T](xs: List[T]): List[T] = xs.foldLeft(List()) {
	case (acc, ls: List[T]) => acc ::: flatten(ls)
	case (acc, x) => acc ::: List(x)
}

// O(NlogN)
def mergesort(xs: List[Int]): List[Int] = {
	val n = xs.length / 2
	if (n == 0) xs
	else {
		// O(N) merge
		def merge(xs: List[Int], ys: List[Int]) = (xs, ys) match {
			case (List(), _) => ys
			case (_, List()) => xs
			case (x :: xt, y :: yt) =>
				if (x < y) x :: merge(xt, ys)
				else y :: merge(xs, yt)
		}
		// tuple pattern binding
		val (fst, snd) = xs splitAt n
		merge(mergesort(fst), mergesort(snd))
	}
}

// pass a less than function
def mergesort[T](xs: List[T])(lt: (T, T) => Boolean): List[T] = {
	val n = xs.length / 2
	if (n == 0) xs
	else {
		// O(N) merge
		def merge(xs: List[T], ys: List[T]) = (xs, ys) match {
			case (List(), _) => ys
			case (_, List()) => xs
			case (x :: xt, y :: yt) =>
				if (lt(x, y)) x :: merge(xt, ys)
				else y :: merge(xs, yt)
		}
		// tuple pattern binding
		val (fst, snd) = xs splitAt n
		merge(mergesort(fst)(lt), mergesort(snd)(lt))
	}

val nums = List(1, 2, 3, -4)
val fruits = List("a", "d", "c", "b")
// we could leave out type in anonymous comparison functions
mergesort(nums)((x: Int, y: Int) => x < y)
mergesort(fruits)((x: String, y: String) => x.compareTo(y) < 0)

import math.Ordering

def mergesort[T](xs: List[T])(implicit ord: Ordering[T]): List[T] = {
	val n = xs.length / 2
	if (n == 0) xs
	else {
		// O(N) merge
		def merge(xs: List[T], ys: List[T]) = (xs, ys) match {
			case (List(), _) => ys
			case (_, List()) => xs
			case (x :: xt, y :: yt) =>
				if (ord.lt(x, y)) x :: merge(xt, ys)
				else y :: merge(xs, yt)
		}
		// tuple pattern binding
		val (fst, snd) = xs splitAt n
		// since we have implicit ord, we don't need to pass ord
		merge(mergesort(fst), mergesort(snd))
	}

val nums = List(1, 2, 3, -4)
val fruits = List("a", "d", "c", "b")

mergesort(nums)(Ordering.Int)
mergesort(fruits)(Ordering.String)

// implicit keyword means that compiler finds the correct ordering based on type
mergesort(nums)
mergesort(fruits)

abstract class List[T] {
	// Real implementations of these are more complex
	// They would be tail recursive and work on other collections

	def map[U](f: T => U): List[U] = this match {
		case Nil => this
		case x :: xs => f(x) :: xs.map(f)
	}

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

	def reduceLeft(op: (T, T) => T): T = this match {
		case Nil => throw new Error("Nil.reduceLeft")
		case x :: xs => (xs foldLeft x)(op) // acc is the first element, x
	}

	// apply op and fold into z for x1, x2 ... xN
	def foldLeft[U](z: U)(op: (U, T) => U): U = this match {
		case Nil => z
		case x :: xs => (xs foldLeft op(z, x))(op)
	}

	def reduceRight(op: (T, T) => T): T = this match {
		case Nil => throw new Error("Nil.reduceRight")
		case x :: Nil => x
		case x :: xs => op(x, xs.reduceRight(op))
	}

	// apply op and fold into z for xN,... x2, x1
	def foldRight[U][x: U](op: (T, U) => U): U = this match {
		case Nil => z
		case x :: xs => op(x, (xs foldRight z)(op))
	}
}

// We can use generic functions in other functions like this:
def scaleList(xs: List[Double], factor: Double): List[Double] =
	xs map (x => x * factor)
def squareList(xs: List[Int]): List[Int] =
	xs map (x => x * x)
def posElems(xs: List[Int]): List[Int] =
	xs filter (x => x > 0)

// we can't put foldLeft here because we can only apply :: on List(T)
def concat[T](xs: List[T], ys: List[T]): List[T] =
	(xs foldRight ys)(_ :: _)

def mapFun[T, U](xs: List[T], f: T => U): List[U] =
  (xs foldRight List[U]())((x, acc) => f(x) :: acc)

def lengthFun[T](xs: List[T]): Int =
  (xs foldRight 0)( (_, acc) => 1 + acc )

def pack[T](xs: List[T]): List[List[T]] = xs match {
	case Nil => Nil
	case x :: xt => {
		val (prefix, remainder) = xs span (e => e == x)
		prefix :: pack(remainder)
	}

val data = List("a", "a", "b", "c", "c", "a")
pack(data) // List(List("a", "a", "a"), List("b"), List("c", "c"), List("a"))

def encode[T](xs: List[T]): List[(T, Int) =
	pack(xs).map(ys => (ys.head, ys.length))

encode(data) // List((a, 3), (b, 1), (c, 2), (a, 1))

def concat[T](xs: List[T], ys: List[T]) = xs match {
	case List() => ys
	case x :: xt => x :: concat(xt, ys)
}

(xs ++ ys) ++ zs === (Nil ++ ys) ++ zs // by 1st defining clause
	=== ys + zs
xs ++ (ys ++ zs) === Nil ++ (ys ++ zs) // by 1st defining clause
	=== ys + zs

// thus, for xs => Nil,
(xs ++ ys) ++ zs === xs ++ (ys ++ zs)

(xs ++ ys) ++ zs === ((x :: xs) ++ ys) ++ zs
	=== (x :: (xs ++ ys)) ++ zs // by 2nd defining clause
	=== x :: ((xs ++ ys) ++ zs)) // by 2nd defining clause
	=== x :: (xs ++ (ys ++ zs)) // by induction hypothesis

xs ++ (ys ++ zs) === (x :: xs) ++ (ys ++ zs)
	=== x :: (xs ++ (ys ++ zs)) // by 2nd defining clause

// thus, for xs => x :: xs,
(xs ++ ys) ++ zs === xs ++ (ys ++ zs)

xs ++ Nil === Nil ++ Nil
	=== Nil // by 1st defining clause
	=== xs

(x :: xs) ++ Nil
	=== x :: (xs ++ Nil) // by 2nd defining clause
	=== x :: xs // by induction hypothesis

def reverse[T](xs: List[T]): List[T] = xs match {
	case List() => List()
	case y :: ys => reverse(ys) ::: List(y)
}

Nil.reverse.reverse
	=== Nil.reverse
	=== Nil

(x :: xs).reverse.reverse
	=== (xs.reverse ++ List(x)).reverse
// Let ys => xs.reverse
	=== (ys ++ List(x)).reverse

x :: xs
	=== x :: xs.reverse.reverse // by induction hypothesis
	=== x :: ys.reverse

// Let's now do structural induction on ys, to prove
(ys ++ List(x)).reverse === x :: ys.reverse

// Base case: ys => Nil
(Nil ++ List(x)).reverse
	=== List(x).reverse // 1st clause of ++
	=== (x :: Nil).reverse // definition of List
	=== Nil.reverse ++ List(x) // 2nd clause of reverse
	=== Nil ++ (x :: Nil) // 1st clause of reverse, definition of list
	=== x :: Nil // 1st clause of ++
	=== x :: Nil.reverse // 1st clause of reverse

// Induction step: ys => y :: ys
((y :: ys) ++ List(x)).reverse
	=== (y :: (ys ++ List(x))).reverse // 2nd clause of ++
	=== (ys ++ List(x)).reverse ++ List(y) // 2nd clause of reverse
	=== (x :: ys.reverse) ++ List(y) // induction hypothesis
	=== x :: (ys.reverse ++ List(y)) // first clause of ++
	=== x :: (y :: ys).reverse // 2nd clause of reverse

// xs => Nil
(Nil ++ ys) map f
	=== ys map f // 1st clause of ++
	=== Nil ++ ys map f // by 1st clause of ++
	=== (Nil map f) ++ ys map f // 1st clause of map

// ys => Nil
(xs ++ Nil) map f
	=== xs map f
	=== xs map f ++ Nil
	=== xs map f ++ Nil map f

// xs => x :: xs
((x :: xs) ++ ys) map f
	=== (x :: (xs ++ ys)) map f // 2nd clause of ++
	=== f(x) :: ((xs ++ ys) map f) // 2nd clause of map
	=== f(x) :: ((xs map f) ++ (ys map f)) // induction hypothesis
	=== (f(x) :: (xs map f)) ++ (ys map f) // 2nd clause of ++
	=== ((x :: xs) map f) ++ (ys map f) // 2nd clause of map

// ys => y :: ys ??? can't do this proof

val nums = Vector(1, 2, 3, -88)
val people = Vector("Bob", "James", "Peter")

// Vectors support all List operations (both subclass Seq, Iterable)
// However, instead of x :: xs, vectors have:
0 +: nums // Vector(0, 1, 2, 3, -88)
people :+ "Martin" // Vector("Bob", "James", "Peter", "Martin")

// Arrays and Strings also support Seq operations, but do not subclass Seq
// since they come from Java
val xs = Array(1, 2, 3, 44)
xs map (x => x * 2)

val s = "Hello World"
s filter (c => c.isUpper)

// Range only stores max, min, and step value
val r: Range = 1 until 5 // 1, 2, 3, 4
val s: Range = 1 to 5 // 1, 2, 3, 4, 5
1 to 10 by 3 // 1, 4, 7, 10

val s = "Hello World"
s flatMap (c => List('.', c)) // ".H.e.l.l.o. .W.o.r.l.d"

s.flatten
	==== s foldRight "")(_ ++ _)
	==== s flatMap (x => x)

// Most operations on Sequences are also available on Sets
val fruit = Set("a", "b", "c")
val s = (1 to 6).toSet

object nqueens {
	def queens(n: Int): Set[List[Int]] = {
		def placeQueens(k: Int): Set[List[Int]] =
			if (k == 0) Set(List())
			else
				for {
					queens <- placeQueens(k - 1)
					col <- 0 until n
					if isSafe(col, queens)
				} yield col :: queens
		placeQueens(n)
	}

	def isSafe(col: Int, queens: List[Int]): Boolean
		val row = queens.length
		val queensWithRow = (row - 1 to 0 by -1) zip queens
		queensWithRow forall {
			case (r, c) => col != c && math.abs(col - c) != row - r
		}

	def show(queens: List[Int]) = {
		val lines =
			for (col <- queens.reverse)
			yield Vector.fill(queens.length)("* ").updated(col, "X ").mkString
		"\n" + (lines mkString "\n")
	}
}

val romanNumerals = Map("I" -> 1, "V" -> 5, "X" -> 10) // Map[String, Int]
val capitalOfCountry = Map("US" -> "Washington", "Switzerland" -> "Bern")

// Maps are iterables, Map[K, V] extends Iterable[(K, V)]
val countryOfCapital = capitalOfCountry map {
	case (x, y) => (y, x)
}

// Maps are also functions, Map[K, V] extends K => V
capitalOfCountry("US") // "Washington"
capitalOfCountry("Andorra") // NoSuchElementException
capitalOfCountry get "Andorra" // Option[String] = None
captialOfCountry get "US" // Option[String] = Some("Washington")

val capitals = capitalOfCountry withDefaultValue "unknown"
capitals("Andorra") // "unknown

// Option definition
trait Option[+A]
case class Some[+A](value: A extends Option[A]
object None extends Option[Notion]

// Since Options are case classes, they can be pattern matched
def showCapital(country: String) = captialOfCountry.get(country) match {
	case Some(capital) => capital
	case None => "missing data"
}
// Options also support map, filter, etc.

// orderBy => sortWith and sorted
val fruit = List("apple", "pear", "orange", "pineapple")
fruit sortWith (_.length < _.length) // sort by word length
fruit.sorted // lexographic

// groupBy
fruit groupBy (_.head)
// Map("p" -> List("pear", "pineapple"),
//     "a" -> List("apple"),
//     "o" -> List("orange"))

class Poly(val terms0: Map[Int, Double]) {
	// allow us to pass a sequence for construction
	def this(bindings: (Int, Double)*) = this(bindings.toMap)

	val terms = terms0 withDefaultValue(0.0)

	// When 2 maps are added, matching keys are overwritten in the first map
	// So, we need to adjust the second map
	def + (other: Poly) = new Poly(terms ++ (other.terms map adjust))
	def adjust(term: (Int, Double)): (Int, Double) = {
		val (exp, coeff) = term
		exp -> (coeff + terms(exp))
	}

	// An faster implementation using foldLeft since we don't have to
	// store an intermediate list of adjusted terms
	def + (other: Poly) = new Poly((other.terms foldLeft terms)(addTerm)
	def addTerm(terms: Map[Int, Double], term: (Int, Double)): Map[Int, Double] = {
		val (exp, coeff) = term
		terms + exp -> (coeff + terms(exp))
	}

	override def toString =
		(for ((exp, coeff) <- terms.toList.sorted.reverse)
				yield coeff + "x^" + exp
		) mkString " + "
}

val p1 = new Poly(1 -> 2.0, 3 -> 4.0, 5 -> 6.2)
val p2 = new Poly(Map(0 -> 3.0, 3 -> 7.0))
p1 + p2

p1.terms(7) // 0.0

val mnem = Map(
	'2' -> "ABC", '3' -> "DEF", '4' -> "GHI", '5' -> "JKL", '6' -> "MNO",
	'7' -> "PQRS", '8' -> "TUV", '9' -> "WXYZ"
)

val in = Source.fromURL(...) // get dictionary from source
val words = in.getLines.toList filter (w => w forall (c => c.isLetter))
val mnem = ...

// Invert the mnem map to give a map from chars A...Z to 2...9
val charCode: Map[Char, Char] = for((digit, str) <- mnem; l <- str) yield ltr -> digit

// Maps a word to the difit string it can represeng e.g. Java -> 5282
def wordCode(word: String): String = word.toUpperCase map charCode

/*
 * A map from digit strings to the words that represent them
 * e.g. 5282 -> List("Java", "Kata", "Lava", ...)
 * Note: A missing number should map to the empty set e.g. "1111" -> List()
*/
val wordsForNum: Map[String, Seq[String]] =
	words groupBy wordCode withDefaultValue Seq()

// Return all ways to encode a number as a list of words
def encode(number: String): Set[List[String]] =
	if (number.isEmpty) Set(List())
	else {
		for {
			split <- 1 to number.length
			word <- wordsForNum(number take split)
			rest <- encode(number drop split)
		} yield word :: rest
	}.toSet

// Get phrases set
def translate(number: String): Set[String] =
	encode(number) map (_ mkString " ")