--- a/progs/lecture2.scala Sun Nov 16 12:26:31 2025 +0000
+++ b/progs/lecture2.scala Thu Nov 27 18:24:07 2025 +0000
@@ -7,6 +7,35 @@
// - Pattern-Matching
// - Recursion
+
+// Function Definitions
+//======================
+
+// The general scheme for a function: you have to give a
+// type to each argument and a return type of the function
+//
+// def fname(arg1: ty1, arg2: ty2,..., argn: tyn): rty = {
+// ....
+// }
+
+def incr(x: Int) : Int = x + 1
+incr(42)
+
+def add(x: Int, y: Int) : Int = x + y
+
+
+def average(ls: List[Int]) : Option[Int] = {
+ val s = ls.sum
+ val l = ls.length
+ if (l == 0) None else Some(s / l)
+}
+
+average(List(1,2,3,4))
+average(List())
+
+
+
+
// The Option Type
//=================
@@ -45,8 +74,8 @@
safe_div(10 + 5, 3)
List(1,2,3,4,5,6).indexOf(7)
-List[Int](3,4,5).min
-List[Int]().minOption
+List[Int]().min
+List[Int](1,2,3).minOption
@@ -58,42 +87,45 @@
import scala.util._ // Try,...
import io.Source // fromURL
-val my_url = "https://nms.kcl.ac.uk/christian.urban/"
+//val my_url = "https://nms.kcl.ac.uk/christian.urban/"
+val my_url = "https://urbanchr.github.io/"
+
+println(Try(Source.fromURL(my_url)(using "ISO-8859-1").mkString).toOption)
-Source.fromURL(my_url)("ISO-8859-1").mkString
-Source.fromURL(my_url)("ISO-8859-1").getLines().toList
+.mkString
+Source.fromURL(my_url)(using "ISO-8859-1").getLines().toList
-Try(Source.fromURL(my_url)("ISO-8859-1").mkString).getOrElse("")
+Try(Source.fromURL(my_url)(using "ISO-8859-1").mkString).getOrElse("")
-Try(Some(Source.fromURL(my_url)("ISO-8859-1").mkString)).getOrElse(None)
+Try(Some(Source.fromURL(my_url)(using "ISO-8859-1").mkString)).getOrElse(None)
// the same for files
-Try(Some(Source.fromFile("test.txt")("ISO-8859-1").mkString)).getOrElse(None)
+Try(Some(Source.fromFile("test.txt")(using "ISO-8859-1").mkString)).getOrElse(None)
-Try(Source.fromFile("test.txt")("ISO-8859-1").mkString).toOption
+Try(Source.fromFile("test.txt")(using "ISO-8859-1").mkString).toOption
-Using(Source.fromFile("test.txt")("ISO-8859-1"))(_.mkString).toOption
+Using(Source.fromFile("test.txt")(using "ISO-8859-1"))(_.mkString).toOption
// how to implement a function for reading
// (lines) from files...
//
def get_contents(name: String) : List[String] =
- Source.fromFile(name)("ISO-8859-1").getLines().toList
+ Source.fromFile(name)(using "ISO-8859-1").getLines().toList
get_contents("text.txt")
get_contents("test.txt")
// slightly better - return Nil
def get_contents(name: String) : List[String] =
- Try(Source.fromFile(name)("ISO-8859-1").getLines.toList).getOrElse(List())
+ Try(Source.fromFile(name)(using "ISO-8859-1").getLines.toList).getOrElse(List())
get_contents("text.txt")
// much better - you record in the type that things can go wrong
def get_contents(name: String) : Option[List[String]] =
- Try(Some(Source.fromFile(name)("ISO-8859-1").getLines().toList)).getOrElse(None)
+ Try(Some(Source.fromFile(name)(using "ISO-8859-1").getLines().toList)).getOrElse(None)
get_contents("text.txt")
get_contents("test.txt")
@@ -175,20 +207,55 @@
// minByOption
// maxByOption
+def altproduct(xs: List[Int]) : List[Int] = xs match {
+ case Nil => Nil
+ case (x::y::xs) => x * y :: altproduct(y::xs)
+ case (x::Nil) => List(x)
+}
+
+altproduct(List(1,2,3,4,5))
+
+def powerset(xs: Set[Int]) : Set[Set[Int]] = {
+ if (xs == Set()) Set(Set())
+ else {
+ powerset(xs.tail) ++ powerset(xs.tail).map(_ + xs.head)
+ }
+}
+
+powerset(Set(1,2,3)).mkString("\n")
+
// Higher-Order Functions
//========================
// functions can take functions as arguments
// and produce functions as result
+val foo = for (n <- (1 to 10).toList) yield n * n
+
+
def even(x: Int) : Boolean = x % 2 == 0
+
+even(2)
+even(3)
+
+def even(x: Int) : Boolean = x % 2 == 1
+
+val foo_fun = even
+
+foo_fun(2)
+foo_fun(3)
+
+
def odd(x: Int) : Boolean = x % 2 == 1
def inc(x: Int) : Int = x + 1
val lst = (1 to 10).toList
lst.filter(odd)
-lst.exists(even)
+lst.find(even)
+lst.find(_ % 2 == 0)
+lst.sortWith(_ < _) // (x,y) => x < y
+lst.find(_ > 4)
lst.count(odd)
lst.filter(_ % 2 == 0)
@@ -466,13 +533,59 @@
-
+
+// Recursion
+//===========
+
+// my_length
+
+def my_length(xs: List[Int]) : Int = {
+ if (xs == Nil) 0 else 1 + my_length(xs.tail)
+}
+
+def my_sum(xs: List[Int]) : Int = {
+ if (xs == Nil) 0 else xs.head + my_sum(xs.tail)
+}
+
+my_sum((1 to 100).toList)
+my_length(List())
+
+/* my_map */
+for (n <- List[Int](1,2,3)) yield n * n
+
+List(1,2,3) ::: List(3,4,5)
+3 :: List(3,4,5)
+
+def my_map(xs: List[Int], f : Int => Int ) : List[Int] = {
+ if (xs == Nil) Nil
+ else f(xs.head) :: my_map(xs.tail, f)
+}
+
+def square(n: Int) : Int = n * n
+
+
+my_map(List(1,2,3), square)
-// Recursion
-//===========
+/* powerset */
+
+def powerset(xs: Set[Int]) : Set[Set[Int]] = {
+ if (xs == Set()) Set(Set())
+ else powerset(xs.tail) ++ powerset(xs.tail).map(_ + xs.head)
+}
+
+
+
+
+
+/* on lists */
+def powerset(xs: List[Int]) : List[List[Int]] = {
+ if (xs == Nil) List(Nil)
+ else powerset(xs.tail) ::: powerset(xs.tail).map(xs.head :: _)
+}
+
/* Say you have characters a, b, c.
@@ -525,7 +638,7 @@
// gets the first 10K of a web-page
def get_page(url: String) : String = {
- Try(Source.fromURL(url)("ISO-8859-1").take(10000).mkString).
+ Try(Source.fromURL(url)(using "ISO-8859-1").take(10000).mkString).
getOrElse { println(s" Problem with: $url"); ""}
}
@@ -555,7 +668,9 @@
}
// some starting URLs for the crawler
-val startURL = """https://nms.kcl.ac.uk/christian.urban/"""
+//val startURL = """https://nms.kcl.ac.uk/christian.urban/"""
+val startURL = """https://urbanchr.github.io/"""
+
crawl(startURL, 2)
@@ -582,7 +697,166 @@
+def powerset(xs: Set[Int]) : Set[Set[Int]] = {
+ if (xs == Set()) Set(Set())
+ else {
+ val ps = powerset(xs.tail)
+ ps ++ ps.map(_ + xs.head)
+ }
+}
+def psubsets(xs: Set[Int]) =
+ powerset(xs) -- Set(Set(), xs)
+
+//def psubsets(xs: Set[Int]) =
+// xs.subsets.toList -- Set(Set(), xs)
+
+def splits(xs: Set[Int]) : Set[(Set[Int], Set[Int])] =
+ psubsets(xs).map(s => (s, xs -- s))
+
+
+
+enum Tree {
+ case Num(i: Int)
+ case Add(l: Tree, r: Tree)
+ case Sub(l: Tree, r: Tree)
+ case Mul(l: Tree, r: Tree)
+ case Div(l: Tree, r: Tree)
+}
+import Tree._
+
+def pp(tr: Tree) : String = tr match {
+ case Num(n) => s"$n"
+ case Add(l, r) => s"(${pp(l)} + ${pp(r)})"
+ case Sub(l, r) => s"(${pp(l)} - ${pp(r)})"
+ case Mul(l, r) => s"(${pp(l)} * ${pp(r)})"
+ case Div(l, r) => s"(${pp(l)} / ${pp(r)})"
+}
+
+def search(nums: Set[Int]) : Set[Tree] = nums.size match {
+ case 0 => Set()
+ case 1 => Set(Num(nums.head))
+ case 2 => {
+ val l = nums.head
+ val r = nums.tail.head
+ Set(Add(Num(l), Num(r)),
+ Mul(Num(l), Num(r)))
+ ++ Option.when(l <= r)(Sub(Num(r), Num(l)))
+ ++ Option.when(l > r)(Sub(Num(l), Num(r)))
+ ++ Option.when(r > 0 && l % r == 0)(Div(Num(l), Num(r)))
+ ++ Option.when(l > 0 && r % l == 0)(Div(Num(r), Num(l)))
+ }
+ case xs => {
+ val spls = splits(nums)
+ val subtrs =
+ for ((lspls, rspls) <- spls;
+ lt <- search(lspls);
+ rt <- search(rspls)) yield {
+ Set(Add(lt, rt), Sub(lt, rt),
+ Mul(lt, rt), Div(lt, rt))
+ }
+ subtrs.flatten
+ }
+}
+
+println(search(Set(1,2,3,4)).mkString("\n"))
+
+def eval(tr: Tree) : Option[Int] = tr match {
+ case Num(n) => Some(n)
+ case Add(l, r) =>
+ for (rl <- eval(l); rr <- eval(r)) yield rl + rr
+ case Mul(l, r) =>
+ for (rl <- eval(l); rr <- eval(r)) yield rl * rr
+ case Sub(l, r) =>
+ for (rl <- eval(l); rr <- eval(r);
+ if 0 <= rl - rr) yield rl - rr
+ case Div(l, r) =>
+ for (rl <- eval(l); rr <- eval(r);
+ if rr > 0 && rl % rr == 0) yield rl / rr
+}
+
+eval(Add(Num(1), Num(2)))
+eval(Mul(Add(Num(1), Num(2)), Num(4)))
+eval(Sub(Num(3), Num(2)))
+eval(Sub(Num(3), Num(6)))
+eval(Div(Num(6), Num(2)))
+eval(Div(Num(6), Num(4)))
+
+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
+}
+
+
+import scala.collection.parallel.CollectionConverters._
+
+def check(xs: Set[Int], target: Int) =
+ search(xs).find(eval(_) == Some(target))
+
+for (sol <- check(Set(50, 5, 4, 9, 10, 8), 560)) {
+ println(s"${pp(sol)} => ${eval(sol)}")
+}
+
+
+
+time_needed(1, check(Set(50, 5, 4, 9, 10, 8), 560))
+
+
+println(check(Set(25, 5, 2, 10, 7, 1), 986).mkString("\n"))
+
+for (sol <- check(Set(25, 5, 2, 10, 7, 1), 986)) {
+ println(s"${pp(sol)} => ${eval(sol)}")
+}
+
+for (sol <- check(Set(25, 5, 2, 10, 7, 1), -1)) {
+ println(s"${pp(sol)} => ${eval(sol)}")
+}
+
+for (sol <- check(Set(100, 25, 75, 50, 7, 10), 360)) {
+ println(s"${pp(sol)} => ${eval(sol)}")
+}
+time_needed(1, check(Set(100, 25, 75, 50, 7, 10), 360))
+
+
+
+time_needed(1, check(Set(25, 5, 2, 10, 7, 1), 986))
+time_needed(1, check(Set(25, 5, 2, 10, 7, 1), -1))
+
+
+def generate(nums: Set[Int]) : Set[(Tree, Int)] = nums.size match {
+ case 0 => Set()
+ case 1 => Set((Num(nums.head), nums.head))
+ case xs => {
+ val spls = splits(nums)
+ val subtrs =
+ for ((lspls, rspls) <- spls;
+ (lt, ln) <- generate(lspls);
+ (rt, rn) <- generate(rspls)) yield {
+ Set((Add(lt, rt), ln + rn),
+ (Mul(lt, rt), ln * rn))
+ ++ Option.when(ln <= rn)((Sub(rt, lt), rn - ln))
+ ++ Option.when(ln > rn)((Sub(lt, rt), ln - rn))
+ ++ Option.when(rn > 0 && ln % rn == 0)((Div(lt, rt), ln / rn))
+ ++ Option.when(ln > 0 && rn % ln == 0)((Div(rt, lt), rn / ln))
+ }
+ subtrs.flatten
+ }
+}
+
+def check2(xs: Set[Int], target: Int) =
+ generate(xs).find(_._2 == target)
+
+for ((sol, ev) <- check2(Set(50, 5, 4, 9, 10, 8), 560)) {
+ println(s"${pp(sol)} => ${eval(sol)} / $ev")
+}
+
+time_needed(1, check(Set(50, 5, 4, 9, 10, 8), 560))
+time_needed(1, check2(Set(50, 5, 4, 9, 10, 8), 560))
+
+time_needed(1, check(Set(50, 5, 4, 9, 10, 8), -1))
+time_needed(1, check2(Set(50, 5, 4, 9, 10, 8), -1))
// Jumping Towers
//================
