// Scala Lecture 3
//=================

// Pattern Matching
//==================

// A powerful tool which is supposed to come to Java in a few years
// time (https://www.youtube.com/watch?v=oGll155-vuQ)...Scala already
// has it for many years. Other functional languages have it already for
// decades. I think I would be really upset if a programming language 
// I have to use does not have pattern matching....its is just so 
// useful. ;o)

// The general schema:
//
//    expression match {
//       case pattern1 => expression1
//       case pattern2 => expression2
//       ...
//       case patternN => expressionN
//    }


// remember
val lst = List(None, Some(1), Some(2), None, Some(3)).flatten


def my_flatten(xs: List[Option[Int]]): List[Int] = {
  if (xs == Nil) Nil
  else if (xs.head == None) my_flatten(xs.tail)
  else xs.head.get :: my_flatten(xs.tail)
}



val lst = List(None, Some(1), Some(2), None, Some(3))

def my_flatten(lst: List[Option[Int]]): List[Int] = lst match {
  case Nil => Nil
  case None::xs => my_flatten(xs)
  case Some(n)::xs => n::my_flatten(xs)
}

my_flatten(lst)

Nil == List()


// another example including a catch-all pattern
def get_me_a_string(n: Int): String = n match {
  case 0 => "zero"
  case 1 => "one"
  case 2 => "two"
  case _ => "many"
}

get_me_a_string(10)

// you can also have cases combined
def season(month: String) = month match {
  case "March" | "April" | "May" => "It's spring"
  case "June" | "July" | "August" => "It's summer"
  case "September" | "October" | "November" => "It's autumn"
  case "December" | "January" | "February" => "It's winter"
}
 
println(season("November"))

// What happens if no case matches?

println(season("foobar"))


// we can also match more complicated pattern
//
// let's look at the Collatz function on binary strings

// adding two binary strings in a very, very lazy manner

def badd(s1: String, s2: String) : String = 
  (BigInt(s1, 2) + BigInt(s2, 2)).toString(2)


"111".dropRight(1)
"111".last

def bcollatz(s: String) : Long = (s.dropRight(1), s.last) match {
  case ("", '1') => 1                               // we reached 1
  case (rest, '0') => 1 + bcollatz(rest)            
                                  // even number => divide by two
  case (rest, '1') => 1 + bcollatz(badd(s + '1', s))
                                  // odd number => s + '1' is 2 * s + 1
                                  // add another s gives 3 * s + 1  
} 

bcollatz(6.toBinaryString)
bcollatz(837799.toBinaryString)
bcollatz(100000000000000000L.toBinaryString)
bcollatz(BigInt("1000000000000000000000000000000000000000000000000000000000000000000000000000").toString(2))




// User-defined Datatypes
//========================

abstract class Colour
case object Red extends Colour 
case object Green extends Colour 
case object Blue extends Colour

def fav_colour(c: Colour) : Boolean = c match {
  case Red   => false
  case Green => true
  case Blue  => false 
}

fav_colour(Green)


// actually colors can be written with "object",
// because they do not take any arguments

abstract class Day
case object Monday extends Day 
case object Tuesday extends Day 
case object Wednesday extends Day
case object Thursday extends Day 
case object Friday extends Day 
case object Saturday extends Day
case object Sunday extends Day 

abstract class Suit
case object Spades extends Suit
case object Hearts extends Suit
case object Diamonds extends Suit
case object Clubs extends Suit

//define function for colour of suits

abstract class Rank
case class Ace extends Rank
case class King extends Rank
case class Queen extends Rank
case class Jack extends Rank
case class Num(n: Int) extends Rank

//define functions for beats
//beats Ace _ => true
//beats _ Acs => false


// ... a bit more useful: Roman Numerals

abstract class RomanDigit 
case object I extends RomanDigit 
case object V extends RomanDigit 
case object X extends RomanDigit 
case object L extends RomanDigit 
case object C extends RomanDigit 
case object D extends RomanDigit 
case object M extends RomanDigit 

type RomanNumeral = List[RomanDigit] 

def RomanNumeral2Int(rs: RomanNumeral): Int = rs match { 
  case Nil => 0
  case M::r    => 1000 + RomanNumeral2Int(r)  
  case C::M::r => 900 + RomanNumeral2Int(r)
  case D::r    => 500 + RomanNumeral2Int(r)
  case C::D::r => 400 + RomanNumeral2Int(r)
  case C::r    => 100 + RomanNumeral2Int(r)
  case X::C::r => 90 + RomanNumeral2Int(r)
  case L::r    => 50 + RomanNumeral2Int(r)
  case X::L::r => 40 + RomanNumeral2Int(r)
  case X::r    => 10 + RomanNumeral2Int(r)
  case I::X::r => 9 + RomanNumeral2Int(r)
  case V::r    => 5 + RomanNumeral2Int(r)
  case I::V::r => 4 + RomanNumeral2Int(r)
  case I::r    => 1 + RomanNumeral2Int(r)
}

RomanNumeral2Int(List(I,V))             // 4
RomanNumeral2Int(List(I,I,I,I))         // 4 (invalid Roman number)
RomanNumeral2Int(List(V,I))             // 6
RomanNumeral2Int(List(I,X))             // 9
RomanNumeral2Int(List(M,C,M,L,X,X,I,X)) // 1979
RomanNumeral2Int(List(M,M,X,V,I,I))     // 2017



// another example
//=================

// Once upon a time, in a complete fictional country there were Persons...

abstract class Person
case object King extends Person
case class Peer(deg: String, terr: String, succ: Int) extends Person
case class Knight(name: String) extends Person
case class Peasant(name: String) extends Person
case object Clown extends Person

def title(p: Person): String = p match {
  case King => "His Majesty the King"
  case Peer(deg, terr, _) => s"The ${deg} of ${terr}"
  case Knight(name) => s"Sir ${name}"
  case Peasant(name) => name
  case Clown => "My name is Boris Johnson"

}

title(Clown)



def superior(p1: Person, p2: Person): Boolean = (p1, p2) match {
  case (King, _) => true
  case (Peer(_,_,_), Knight(_)) => true
  case (Peer(_,_,_), Peasant(_)) => true
  case (Peer(_,_,_), Clown) => true
  case (Knight(_), Peasant(_)) => true
  case (Knight(_), Clown) => true
  case (Clown, Peasant(_)) => true
  case _ => false
}

val people = List(Knight("David"), 
                  Peer("Duke", "Norfolk", 84), 
                  Peasant("Christian"), 
                  King, 
                  Clown)

println(people.sortWith(superior(_, _)).mkString(", "))




// Tail recursion
//================


def fact(n: Long): Long = 
  if (n == 0) 1 else n * fact(n - 1)

fact(10)              //ok
fact(10000)           // produces a stackoverflow

def factT(n: BigInt, acc: BigInt): BigInt =
  if (n == 0) acc else factT(n - 1, n * acc)

factT(10, 1)
factT(100000, 1)

// there is a flag for ensuring a function is tail recursive
import scala.annotation.tailrec

@tailrec
def factT(n: BigInt, acc: BigInt): BigInt =
  if (n == 0) acc else factT(n - 1, n * acc)



// for tail-recursive functions the Scala compiler
// generates loop-like code, which does not need
// to allocate stack-space in each recursive
// call; Scala can do this only for tail-recursive
// functions



// sudoku again

val game0 = """.14.6.3..
              |62...4..9
              |.8..5.6..
              |.6.2....3
              |.7..1..5.
              |5....9.6.
              |..6.2..3.
              |1..5...92
              |..7.9.41.""".stripMargin.replaceAll("\\n", "")

type Pos = (Int, Int)
val EmptyValue = '.'
val MaxValue = 9

val allValues = "123456789".toList
val indexes = (0 to 8).toList


def empty(game: String) = game.indexOf(EmptyValue)
def isDone(game: String) = empty(game) == -1 
def emptyPosition(game: String) = 
  (empty(game) % MaxValue, empty(game) / MaxValue)


def get_row(game: String, y: Int) = 
  indexes.map(col => game(y * MaxValue + col))
def get_col(game: String, x: Int) = 
  indexes.map(row => game(x + row * MaxValue))

def get_box(game: String, pos: Pos): List[Char] = {
    def base(p: Int): Int = (p / 3) * 3
    val x0 = base(pos._1)
    val y0 = base(pos._2)
    val ys = (y0 until y0 + 3).toList
    (x0 until x0 + 3).toList.flatMap(x => ys.map(y => game(x + y * MaxValue)))
}

// this is not mutable!!
def update(game: String, pos: Int, value: Char): String = 
  game.updated(pos, value)

def toAvoid(game: String, pos: Pos): List[Char] = 
  (get_col(game, pos._1) ++ get_row(game, pos._2) ++ get_box(game, pos))

def candidates(game: String, pos: Pos): List[Char] = 
  allValues.diff(toAvoid(game,pos))

//candidates(game0, (0,0))

def pretty(game: String): String = 
  "\n" + (game sliding (MaxValue, MaxValue) mkString "\n")

/////////////////////
// not tail recursive 
def search(game: String): List[String] = {
  if (isDone(game)) List(game)
  else {
    val cs = candidates(game, emptyPosition(game))
    cs.map(c => search(update(game, empty(game), c))).toList.flatten
  }
}

// tail recursive version that searches 
// for all solutions

def searchT(games: List[String], sols: List[String]): List[String] = games match {
  case Nil => sols
  case game::rest => {
    if (isDone(game)) searchT(rest, game::sols)
    else {
      val cs = candidates(game, emptyPosition(game))
      searchT(cs.map(c => update(game, empty(game), c)) ::: rest, sols)
    }
  }
}

searchT(List(game3), List()).map(pretty)


// tail recursive version that searches 
// for a single solution

def search1T(games: List[String]): Option[String] = games match {
  case Nil => None
  case game::rest => {
    if (isDone(game)) Some(game)
    else {
      val cs = candidates(game, emptyPosition(game))
      search1T(cs.map(c => update(game, empty(game), c)) ::: rest)
    }
  }
}

search1T(List(game3)).map(pretty)

// game with multiple solutions
val game3 = """.8...9743
              |.5...8.1.
              |.1.......
              |8....5...
              |...8.4...
              |...3....6
              |.......7.
              |.3.5...8.
              |9724...5.""".stripMargin.replaceAll("\\n", "")

searchT(List(game3), Nil).map(pretty)
search1T(List(game3)).map(pretty)

// Moral: Whenever a recursive function is resource-critical
// (i.e. works with large recursion depth), then you need to
// write it in tail-recursive fashion.
// 
// Unfortuantely, Scala because of current limitations in 
// the JVM is not as clever as other functional languages. It can 
// only optimise "self-tail calls". This excludes the cases of 
// multiple functions making tail calls to each other. Well,
// nothing is perfect. 




// Polymorphic Types
//===================

// You do not want to write functions like contains, first 
// and so on for every type of lists.


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

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

length_string_list(List("1", "2", "3", "4"))
length_int_list(List(1, 2, 3, 4))

//-----
def length[A](lst: List[A]): Int = lst match {
  case Nil => 0
  case x::xs => 1 + length(xs)
}
length(List("1", "2", "3", "4"))
length(List(King, Knight("foo"), Clown))
length(List(1, 2, 3, 4))

def map[A, B](lst: List[A], f: A => B): List[B] = lst match {
  case Nil => Nil
  case x::xs => f(x)::map_int_list(xs, f) 
}

map_int_list(List(1, 2, 3, 4), square)


// Remember?
def first[A, B](xs: List[A], f: A => Option[B]): Option[B] = ...





// Cool Stuff
//============


// Implicits 
//===========
//
// For example adding your own methods to Strings:
// Imagine you want to increment strings, like
//
//     "HAL".increment
//
// you can avoid ugly fudges, like a MyString, by
// using implicit conversions.


implicit class MyString(s: String) {
  def increment = for (c <- s) yield (c + 1).toChar 
}

"HAL".increment




// Regular expressions - the power of DSLs in Scala
//==================================================

abstract class Rexp
case object ZERO extends Rexp                       // nothing
case object ONE extends Rexp                        // the empty string
case class CHAR(c: Char) extends Rexp               // a character c
case class ALT(r1: Rexp, r2: Rexp) extends Rexp     // alternative  r1 + r2
case class SEQ(r1: Rexp, r2: Rexp) extends Rexp     // sequence     r1 o r2  
case class STAR(r: Rexp) extends Rexp               // star         r*



// (ab)*
val r0 = STAR(SEQ(CHAR('a'), CHAR('b')))


// some convenience for typing in regular expressions
import scala.language.implicitConversions    
import scala.language.reflectiveCalls 

def charlist2rexp(s: List[Char]): Rexp = s match {
  case Nil => ONE
  case c::Nil => CHAR(c)
  case c::s => SEQ(CHAR(c), charlist2rexp(s))
}
implicit def string2rexp(s: String): Rexp = charlist2rexp(s.toList)


val r1 = STAR("ab")
val r2 = STAR(ALT("ab"))
val r3 = STAR(ALT("ab", "baa baa black sheep"))

implicit def RexpOps (r: Rexp) = new {
  def | (s: Rexp) = ALT(r, s)
  def % = STAR(r)
  def ~ (s: Rexp) = SEQ(r, s)
}

implicit def stringOps (s: String) = new {
  def | (r: Rexp) = ALT(s, r)
  def | (r: String) = ALT(s, r)
  def % = STAR(s)
  def ~ (r: Rexp) = SEQ(s, r)
  def ~ (r: String) = SEQ(s, r)
}

//example regular expressions
val digit = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"
val sign = "+" | "-" | ""
val number = sign ~ digit ~ digit.% 





// The End
//=========

// A function should do one thing, and only one thing.

// Make your variables immutable, unless there's a good 
// reason not to.

// You can be productive on Day 1, but the language is deep.
//
// http://scalapuzzlers.com
//
// http://www.latkin.org/blog/2017/05/02/when-the-scala-compiler-doesnt-help/

List(1, 2, 3) contains "your mom"

// I like best about Scala that it lets me often write
// concise, readable code.



// You can define your own while loop


def my_while(condition: => Boolean)(block: => Unit): Unit = 
  if (condition) { block ; my_while(condition) { block } } else { }


var x = 10
my_while (x > 0) { 
  println(s"$x") ; x = x - 1 
}


`symbol
`symbol`
