--- 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