# HG changeset patch # User Christian Urban # Date 1510927836 0 # Node ID 9a2f2a1de42b75ba9120547999a961e5b6c54351 # Parent 3a6f51bc6121dd8ffdb9b862b6b57c6f133fc062 updated diff -r 3a6f51bc6121 -r 9a2f2a1de42b cws/cw02.pdf Binary file cws/cw02.pdf has changed diff -r 3a6f51bc6121 -r 9a2f2a1de42b cws/cw02.tex --- a/cws/cw02.tex Fri Nov 17 09:24:34 2017 +0000 +++ b/cws/cw02.tex Fri Nov 17 14:10:36 2017 +0000 @@ -301,7 +301,7 @@ \end{itemize} \noindent -\textbf{Testing} The first tour function will be called with board +\textbf{Testing:} The first tour function will be called with board sizes of up to $8 \times 8$. \bigskip diff -r 3a6f51bc6121 -r 9a2f2a1de42b progs/lecture2.scala --- a/progs/lecture2.scala Fri Nov 17 09:24:34 2017 +0000 +++ b/progs/lecture2.scala Fri Nov 17 14:10:36 2017 +0000 @@ -39,7 +39,7 @@ // this is just so prone to off-by-one errors; // write instead -for (e <- lst) yield square(e) +for (e <- lst; if (e % 2) == 0; if (e != 4)) yield square(e) //this works for sets as well @@ -55,7 +55,7 @@ //============== // with only a side-effect (no list is produced), -// has no "yield" +// for has no "yield" for (n <- (1 to 10)) println(n) @@ -71,7 +71,9 @@ // know when to use yield and when not: -for (e <- Set(1, 2, 3, 4, 5, 6, 7, 8, 9); if e < 5) yield square(e) +val test = + for (e <- Set(1, 2, 3, 4, 5, 6, 7, 8, 9); if e < 5) yield square(e) + // Option type @@ -83,9 +85,10 @@ // - if no value is present, you use None -List(7,2,3,4,5,6).find(_ < 4) +List(7,24,3,4,5,6).find(_ < 4) List(5,6,7,8,9).find(_ < 4) +List(7,2,3,4,5,6).filter(_ < 4) // some operations on Option's @@ -93,7 +96,8 @@ lst.flatten -Some(1).get +Some(10).get +None.get Some(1).isDefined None.isDefined @@ -131,6 +135,7 @@ import io.Source val my_url = """https://nms.kcl.ac.uk/christian.urban""" +//val my_url = """https://nms.kcl.ac.uk/christan.urban""" // misspelled Source.fromURL(my_url).mkString @@ -167,9 +172,10 @@ // even Scala is not immune to problems like this: -List(5,6,7,8,9).indexOf(7) +List(5,6,7,8,9).indexOf(42) +// ... how are we supposed to know that this returns -1 // Higher-Order Functions @@ -182,9 +188,9 @@ def even(x: Int) : Boolean = x % 2 == 0 def odd(x: Int) : Boolean = x % 2 == 1 -lst.filter(x => even(x)) +lst.filter(x => even(x) && odd(x)) lst.filter(even(_)) -lst.filter(even) +lst.filter(odd && even) lst.find(_ > 8) @@ -192,6 +198,7 @@ def square(x: Int): Int = x * x +val lst = (1 to 10).toList lst.map(square) lst.map(square).filter(_ > 4) @@ -199,10 +206,15 @@ lst.map(square).filter(_ > 4).map(square) // map works for most collection types, including sets -Set(1, 3, 6).map(square) +Set(1, 3, 6).map(square).filter(_ > 4) -// Why could functions as arguments be useful? +val l = List((1, 3),(2, 4),(4, 1),(6, 2)) + +l.map(square(_._1)) + + +// Why are functions as arguments useful? // // Consider the sum between a and b: @@ -210,7 +222,7 @@ if (a > b) 0 else a + sumInts(a + 1, b) -sumInt(10, 16) +sumInts(10, 16) // sum squares def square(n: Int) : Int = n * n @@ -232,7 +244,7 @@ -// You can see the pattern....can we simplify out work? +// You can see the pattern....can we simplify our work? // The type of functions from ints to ints: Int => Int def sum(f: Int => Int, a: Int, b: Int) : Int = { @@ -249,6 +261,7 @@ def id(n: Int) : Int = n def sumInts(a: Int, b: Int) : Int = sum(id, a, b) +sumInts(10, 12) // Anonymous Functions: You can also write: @@ -268,18 +281,24 @@ // an aside: partial application def add(a: Int)(b: Int) : Int = a + b +def add_abc(a: Int)(b: Int)(c: Int) : Int = a + b + c + +val add2 : Int => Int = add(2) +add2(5) + +val add2_bc : Int => Int => Int = add_abc(2) +val add2_9_c : Int => Int = add2_bc(9) + +add2_9_c(10) sum(add(2), 0, 2) sum(add(10), 0, 2) -def add2(a: Int, b: Int) : Int = a + b -sum(x => add2(2, x), 0, 2) -sum(x => add2(10, x), 0, 2) // Function Composition //====================== -// How could Higher-Order Functions and Options be helpful? +// How can be Higher-Order Functions and Options be helpful? def add_footer(msg: String) : String = msg ++ " - Sent from iOS" @@ -287,11 +306,12 @@ def duplicate(s: String) : String = s ++ s -// they compose nicely +// they compose very nicely, e.g + valid_msg(add_footer("Hello World")) -valid_msg(duplicate(add_footer("Hello World"))) +valid_msg(duplicate(duplicate(add_footer("Helloooooooooooooooooo World")))) - +// but not all functions do // first_word: let's first do it the ugly Java way using null: def first_word(msg: String) : String = { @@ -307,6 +327,9 @@ extended_duplicate(first_word("")) +// but this is against the rules of the game: we do not want +// to change duplicate, because first_word might return null + // Avoid always null! def better_first_word(msg: String) : Option[String] = { @@ -315,14 +338,175 @@ } better_first_word("Hello World").map(duplicate) -better_first_word("Hello World").map(duplicate).map(duplicate).map(valid_msg) + +better_first_word("Hello World").map(duplicate) +better_first_word("").map(duplicate).map(duplicate).map(valid_msg) better_first_word("").map(duplicate) better_first_word("").map(duplicate).map(valid_msg) +// 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 ;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] = { + ...? +} + + + + + +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) +} + + +// 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(0) + +// 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")) + + +// User-defined Datatypes +//======================== + +abstract class Colour +case class Red() extends Colour +case class Green() extends Colour +case class Blue() extends Colour + +def fav_colour(c: Colour) : Boolean = c match { + case Red() => false + case Green() => true + case Blue() => false +} + + +// actually colors can be written with "object", +// because they do not take any arguments +// another example +//================= + +// Once upon a time, in a complete fictional country there were persons... + +abstract class Person +case class 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 + + +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 +} + + +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(", ")) + + + + + +// Problems with mutability and parallel computations +//==================================================== + +def count_intersection(A: Set[Int], B: Set[Int]) : Int = { + var count = 0 + for (x <- A; if (B contains x)) count += 1 + count +} + +val A = (1 to 1000).toSet +val B = (1 to 1000 by 4).toSet + +count_intersection(A, B) + +// but do not try to add .par to the for-loop above, +// otherwise you will be caught in race-condition hell. + + +//propper parallel version +def count_intersection2(A: Set[Int], B: Set[Int]) : Int = + A.par.count(x => B contains x) + +count_intersection2(A, B) + + +//for measuring time +def time_needed[T](n: Int, code: => T) = { + val start = System.nanoTime() + for (i <- (0 to n)) code + val end = System.nanoTime() + (end - start) / 1.0e9 +} + +val A = (1 to 1000000).toSet +val B = (1 to 1000000 by 4).toSet + +time_needed(10, count_intersection(A, B)) +time_needed(10, count_intersection2(A, B)) // Implicits (Cool Feature) @@ -373,166 +557,6 @@ -// 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 ;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] = { - ... -} - - - - - -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) -} - - -// another example -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(0) - -// 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")) - - -// User-defined Datatypes -//======================== - -abstract class Colour -case class Red() extends Colour -case class Green() extends Colour -case class Blue() extends Colour - -def fav_colour(c: Colour) : Boolean = c match { - case Red() => false - case Green() => true - case Blue() => false -} - - -// actually this can be written with "object" - - -// another example -//================= - -abstract class Person -case class 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 - - -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 -} - - -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(", ")) - - - - - - -// Problems with mutability and parallel computations -//==================================================== - -def count_intersection(A: Set[Int], B: Set[Int]) : Int = { - var count = 0 - for (x <- A; if (B contains x)) count += 1 - count -} - -val A = (1 to 1000).toSet -val B = (1 to 1000 by 4).toSet - -count_intersection(A, B) - -// but do not try to add .par to the for-loop above - - -//propper parallel version -def count_intersection2(A: Set[Int], B: Set[Int]) : Int = - A.par.count(x => B contains x) - -count_intersection2(A, B) - - -//for measuring time -def time_needed[T](n: Int, code: => T) = { - val start = System.nanoTime() - for (i <- (0 to n)) code - val end = System.nanoTime() - (end - start) / 1.0e9 -} - -val A = (1 to 1000000).toSet -val B = (1 to 1000000 by 4).toSet - -time_needed(10, count_intersection(A, B)) -time_needed(10, count_intersection2(A, B)) - - // Type abbreviations //==================== @@ -544,8 +568,8 @@ -// Sudoku -//======== +// Sudoku in Scala +//================= // THE POINT OF THIS CODE IS NOT TO BE SUPER // EFFICIENT AND FAST, just explaining exhaustive @@ -572,11 +596,14 @@ 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 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_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)) get_row(game0, 3) get_col(game0, 0) @@ -594,12 +621,14 @@ get_box(game0, (2, 1)) // this is not mutable!! -def update(game: String, pos: Int, value: Char): String = game.updated(pos, value) +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)) +def candidates(game: String, pos: Pos): List[Char] = + allValues.diff(toAvoid(game,pos)) //candidates(game0, (0,0)) @@ -610,7 +639,7 @@ if (isDone(game)) List(game) else { val cs = candidates(game, emptyPosition(game)) - cs.map(c => search(update(game, empty(game), c))).toList.flatten + cs.par.map(c => search(update(game, empty(game), c))).toList.flatten } } @@ -670,4 +699,5 @@ - +//=================== +// the end for today