# HG changeset patch # User Christian Urban # Date 1671280969 0 # Node ID 557d18cce0f0d3e62ce0ceff668053ff4ee8e076 # Parent 289b85843ffd13c99186413f9da03943148505e4 updated diff -r 289b85843ffd -r 557d18cce0f0 main_solution4/knight1.scala --- a/main_solution4/knight1.scala Thu Dec 08 22:19:21 2022 +0000 +++ b/main_solution4/knight1.scala Sat Dec 17 12:42:49 2022 +0000 @@ -150,8 +150,8 @@ */ // 15 secs for 8 x 8 -//val ts1 = time_needed(0,first_tour(8, List((0, 0))).get) -//??val ts1 = time_needed(0,first_tour(8, List((1, 1))).get) +//val ts1 = time_needed(first_tour(8, List((0, 0))).get) +//??val ts1 = time_needed(first_tour(8, List((7, 7))).get) // no result for 4 x 4 //val ts2 = time_needed(0, first_tour(4, List((0, 0)))) diff -r 289b85843ffd -r 557d18cce0f0 main_testing2/wordle_test.sh --- a/main_testing2/wordle_test.sh Thu Dec 08 22:19:21 2022 +0000 +++ b/main_testing2/wordle_test.sh Sat Dec 17 12:42:49 2022 +0000 @@ -170,7 +170,7 @@ echo " evil(secrets, \"stent\").length == 1907" >> $out echo " evil(secrets, \"hexes\").length == 2966" >> $out echo " evil(secrets, \"horse\").length == 1203" >> $out - echo " evil(secrets, \"hoise\").length == 901" >> $out + echo " evil(secrets, \"hoise\").length == 971" >> $out echo " evil(secrets, \"house\").length == 1228" >> $out if (scala_assert "wordle.scala" "wordle_test5.scala") diff -r 289b85843ffd -r 557d18cce0f0 main_testing3/re.scala --- a/main_testing3/re.scala Thu Dec 08 22:19:21 2022 +0000 +++ b/main_testing3/re.scala Sat Dec 17 12:42:49 2022 +0000 @@ -189,5 +189,25 @@ */ +assert(simp(ZERO | ONE) == ONE) +assert(simp(STAR(ZERO | ONE)) == STAR(ZERO | ONE)) +assert(simp(ONE ~ (ONE ~ (ONE ~ CHAR('a')))) == CHAR('a')) +assert(simp(((ONE ~ ONE) ~ ONE) ~ CHAR('a')) == CHAR('a')) +assert(simp(((ONE | ONE) ~ ONE) ~ CHAR('a')) == CHAR('a')) +assert(simp(ONE ~ (ONE ~ (ONE ~ ZERO))) == ZERO) +assert(simp(ALT(ONE ~ (ONE ~ (ONE ~ ZERO)), CHAR('a'))) == CHAR('a')) +assert(simp(CHAR('a') | CHAR('a')) == CHAR('a')) +assert(simp(CHAR('a') ~ CHAR('a')) == CHAR('a') ~ CHAR('a')) +assert(simp(ONE | CHAR('a')) == (ONE | CHAR('a'))) +assert(simp(ALT((CHAR('a') | ZERO) ~ ONE, + ((ONE | CHAR('b')) | CHAR('c')) ~ (CHAR('d') ~ ZERO))) == CHAR('a')) +assert(simp((ZERO | ((ZERO | ZERO) | (ZERO | ZERO))) ~ ((ONE | ZERO) | ONE ) ~ (CHAR('a'))) == ZERO) +assert(simp(ALT(ONE | ONE, ONE | ONE)) == ONE) +assert(simp(ALT(ZERO | CHAR('a'), CHAR('a') | ZERO)) == CHAR('a')) +assert(simp(ALT(ONE | CHAR('a'), CHAR('a') | ONE)) == ALT(ONE, CHAR('a'))) +assert(simp(ALTs(Nil)) == ZERO) +assert(simp(SEQs(List(CHAR('a')))) == CHAR('a')) + + } diff -r 289b85843ffd -r 557d18cce0f0 main_testing3/re_test.sh --- a/main_testing3/re_test.sh Thu Dec 08 22:19:21 2022 +0000 +++ b/main_testing3/re_test.sh Sat Dec 17 12:42:49 2022 +0000 @@ -138,7 +138,7 @@ echo -e " simp(ALT(ZERO | CHAR('a'), CHAR('a') | ZERO)) == CHAR('a')" >> $out echo -e " simp(ALT(ONE | CHAR('a'), CHAR('a') | ONE)) == ALT(ONE, CHAR('a'))" >> $out echo -e " simp(ALTs(Nil)) == ZERO" >> $out - echo -e " simp(SEQs(CHAR('a'))) == CHAR('a')" >> $out + echo -e " simp(SEQs(List(CHAR('a')))) == CHAR('a')" >> $out if (scala_assert "re.scala" "re_test3.scala") then echo -e " --> success" >> $out diff -r 289b85843ffd -r 557d18cce0f0 pics/haojili.png Binary file pics/haojili.png has changed diff -r 289b85843ffd -r 557d18cce0f0 progs/lecture4.scala --- a/progs/lecture4.scala Thu Dec 08 22:19:21 2022 +0000 +++ b/progs/lecture4.scala Sat Dec 17 12:42:49 2022 +0000 @@ -124,7 +124,7 @@ def length_int_list(lst: List[Int]): Int = lst match { case Nil => 0 - case x::xs => 1 + length_int_list(xs) + case _::xs => 1 + length_int_list(xs) } length_int_list(List(1, 2, 3, 4)) @@ -146,7 +146,8 @@ length(List("1", "2", "3", "4")) length(List(1, 2, 3, 4)) -length[Int](List(1, 2, 3, 4)) + +length[String](List(1, 2, 3, 4)) def map[A, B](lst: List[A], f: A => B): List[B] = lst match { @@ -541,12 +542,14 @@ // you can avoid ugly fudges, like a MyString, by // using implicit conversions. +print("\n") +print("""\n""") implicit class MyString(s: String) { def increment = s.map(c => (c + 1).toChar) } -"HAL".increment.map(_.toInt) +"HAL".increment // Abstract idea: diff -r 289b85843ffd -r 557d18cce0f0 progs/lecture5.scala --- a/progs/lecture5.scala Thu Dec 08 22:19:21 2022 +0000 +++ b/progs/lecture5.scala Sat Dec 17 12:42:49 2022 +0000 @@ -1,215 +1,6 @@ // Scala Lecture 5 //================= -// Questions at -// -// pollev.com/cfltutoratki576 - -(n, m) match { - case Pat1 => - case _ => -} - -val delta : (State, Char) => State = - { case (Q0, 'a') => Q1 - case (Q0, 'b') => Q2 - case (Q1, 'a') => Q4 - case (Q1, 'b') => Q2 - case (Q2, 'a') => Q3 - case (Q2, 'b') => Q2 - case (Q3, 'a') => Q4 - case (Q3, 'b') => Q0 - case (Q4, 'a') => Q4 - case (Q4, 'b') => Q4 - case _ => throw new Exception("Undefined") } - - -class Foo(i: Int) - -val v = new Foo(10) - -case class Bar(i: Int) - -val v = Bar(10) - - - - - - - - - - - - -// Laziness with style -//===================== - -// The concept of lazy evaluation doesn’t really -// exist in non-functional languages. C-like languages -// are (sort of) strict. To see the difference, consider - -def square(x: Int) = x * x - -square(42 + 8) - -// This is called "strict evaluation". - -// On the contrary, say we have a pretty expensive operation: - -def peop(n: BigInt): Boolean = peop(n + 1) - -val a = "foo" -val b = "foo" - -if (a == b || peop(0)) println("true") else println("false") - -// This is called "lazy evaluation": -// you delay compuation until it is really -// needed. Once calculated though, the result -// does not need to be re-calculated. - -// A useful example is - -def time_needed[T](i: Int, code: => T) = { - val start = System.nanoTime() - for (j <- 1 to i) code - val end = System.nanoTime() - f"${(end - start) / (i * 1.0e9)}%.6f secs" -} - -// A slightly less obvious example: Prime Numbers. -// (I do not care how many) primes: 2, 3, 5, 7, 9, 11, 13 .... - -def generatePrimes (s: LazyList[Int]): LazyList[Int] = - s.head #:: generatePrimes(s.tail.filter(_ % s.head != 0)) - -val primes = generatePrimes(LazyList.from(2)) - -// the first 10 primes -primes.take(100).toList - -time_needed(1, primes.filter(_ > 100).take(3000).toList) -time_needed(1, primes.filter(_ > 100).take(3000).toList) - -// A Stream (LazyList) of successive numbers: - -LazyList.from(2).take(10) -LazyList.from(2).take(10).force - -// An Iterative version of the Fibonacci numbers -def fibIter(a: BigInt, b: BigInt): LazyList[BigInt] = - a #:: fibIter(b, a + b) - - -fibIter(1, 1).take(10).force -fibIter(8, 13).take(10).force - -fibIter(1, 1).drop(10000).take(1) -fibIter(1, 1).drop(10000).take(1).force - - -// LazyLists are good for testing - - -// Regular expressions - the power of DSLs in Scala -// and Laziness -//================================================== - -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 . r2 -case class STAR(r: Rexp) extends Rexp // star r* - - -// 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) - -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.% - -// Task: enumerate exhaustively regular expressions -// starting from small ones towards bigger ones. - -// 1st idea: enumerate them all in a Set -// up to a level - -def enuml(l: Int, s: String) : Set[Rexp] = l match { - case 0 => Set(ZERO, ONE) ++ s.map(CHAR).toSet - case n => - val rs = enuml(n - 1, s) - rs ++ - (for (r1 <- rs; r2 <- rs) yield ALT(r1, r2)) ++ - (for (r1 <- rs; r2 <- rs) yield SEQ(r1, r2)) ++ - (for (r1 <- rs) yield STAR(r1)) -} - -enuml(1, "a") -enuml(1, "a").size -enuml(2, "a").size -enuml(3, "a").size // out of heap space - - - -def enum(rs: LazyList[Rexp]) : LazyList[Rexp] = - rs #::: enum( (for (r1 <- rs; r2 <- rs) yield ALT(r1, r2)) #::: - (for (r1 <- rs; r2 <- rs) yield SEQ(r1, r2)) #::: - (for (r1 <- rs) yield STAR(r1)) ) - - -enum(LazyList(ZERO, ONE, CHAR('a'), CHAR('b'))).take(200).force -enum(LazyList(ZERO, ONE, CHAR('a'), CHAR('b'))).take(5_000_000).force - - -def depth(r: Rexp) : Int = r match { - case ZERO => 0 - case ONE => 0 - case CHAR(_) => 0 - case ALT(r1, r2) => Math.max(depth(r1), depth(r2)) + 1 - case SEQ(r1, r2) => Math.max(depth(r1), depth(r2)) + 1 - case STAR(r1) => depth(r1) + 1 -} - - -val is = - (enum(LazyList(ZERO, ONE, CHAR('a'), CHAR('b'))) - .dropWhile(depth(_) < 3) - .take(10).foreach(println)) - - - // (Immutable) // Object Oriented Programming in Scala // ===================================== @@ -264,7 +55,7 @@ case class Complex(re: Double, im: Double) { // represents the complex number re + im * i - def +(that: Complex) = Complex(this.re + that.re, this.im + that.im) + def foo(that: Complex) = Complex(this.re + that.re, this.im + that.im) def -(that: Complex) = Complex(this.re - that.re, this.im - that.im) def *(that: Complex) = Complex(this.re * that.re - this.im * that.im, this.re * that.im + that.re * this.im) @@ -272,10 +63,12 @@ def abs = Math.sqrt(this.re * this.re + this.im * this.im) } +object.method(....) + val test = Complex(1, 2) + Complex (3, 4) import scala.language.postfixOps -List(5,4,3,2,1).sorted.reverse +(List(5,4,3,2,1) sorted) reverse // this could have equally been written as val test = Complex(1, 2).+(Complex (3, 4)) @@ -465,6 +258,172 @@ import scala.math.pow +// Laziness with style +//===================== + +// The concept of lazy evaluation doesn’t really +// exist in non-functional languages. C-like languages +// are (sort of) strict. To see the difference, consider + +def square(x: Int) = x * x + +square(42 + 8) + +// This is called "strict evaluation". + +// On the contrary, say we have a pretty expensive operation: + +def peop(n: BigInt): Boolean = peop(n + 1) + +val a = "foo" +val b = "foo" + +if (a == b || peop(0)) println("true") else println("false") + +// This is called "lazy evaluation": +// you delay compuation until it is really +// needed. Once calculated though, the result +// does not need to be re-calculated. + +// A useful example is + +def time_needed[T](i: Int, code: => T) = { + val start = System.nanoTime() + for (j <- 1 to i) code + val end = System.nanoTime() + f"${(end - start) / (i * 1.0e9)}%.6f secs" +} + +// A slightly less obvious example: Prime Numbers. +// (I do not care how many) primes: 2, 3, 5, 7, 9, 11, 13 .... + +def generatePrimes (s: LazyList[Int]): LazyList[Int] = + s.head #:: generatePrimes(s.tail.filter(_ % s.head != 0)) + +val primes = generatePrimes(LazyList.from(2)) + +// the first 10 primes +primes.take(100).toList + +time_needed(1, primes.filter(_ > 100).take(3000).toList) +time_needed(1, primes.filter(_ > 100).take(3000).toList) + +// A Stream (LazyList) of successive numbers: + +LazyList.from(2).take(10) +LazyList.from(2).take(10).force + +// An Iterative version of the Fibonacci numbers +def fibIter(a: BigInt, b: BigInt): LazyList[BigInt] = + a #:: fibIter(b, a + b) + + +fibIter(1, 1).take(10).force +fibIter(8, 13).take(10).force + +fibIter(1, 1).drop(10000).take(1) +fibIter(1, 1).drop(10000).take(1).force + + +// LazyLists are good for testing + + +// Regular expressions - the power of DSLs in Scala +// and Laziness +//================================================== + +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 . r2 +case class STAR(r: Rexp) extends Rexp // star r* + + +// 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) + +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.% + +// Task: enumerate exhaustively regular expressions +// starting from small ones towards bigger ones. + +// 1st idea: enumerate them all in a Set +// up to a level + +def enuml(l: Int, s: String) : Set[Rexp] = l match { + case 0 => Set(ZERO, ONE) ++ s.map(CHAR).toSet + case n => + val rs = enuml(n - 1, s) + rs ++ + (for (r1 <- rs; r2 <- rs) yield ALT(r1, r2)) ++ + (for (r1 <- rs; r2 <- rs) yield SEQ(r1, r2)) ++ + (for (r1 <- rs) yield STAR(r1)) +} + +enuml(1, "a") +enuml(1, "a").size +enuml(2, "a").size +enuml(3, "a").size // out of heap space + + + +def enum(rs: LazyList[Rexp]) : LazyList[Rexp] = + rs #::: enum( (for (r1 <- rs; r2 <- rs) yield ALT(r1, r2)) #::: + (for (r1 <- rs; r2 <- rs) yield SEQ(r1, r2)) #::: + (for (r1 <- rs) yield STAR(r1)) ) + + +enum(LazyList(ZERO, ONE, CHAR('a'), CHAR('b'))).take(200).force +enum(LazyList(ZERO, ONE, CHAR('a'), CHAR('b'))).take(5_000_000).force + + +def depth(r: Rexp) : Int = r match { + case ZERO => 0 + case ONE => 0 + case CHAR(_) => 0 + case ALT(r1, r2) => Math.max(depth(r1), depth(r2)) + 1 + case SEQ(r1, r2) => Math.max(depth(r1), depth(r2)) + 1 + case STAR(r1) => depth(r1) + 1 +} + + +val is = + (enum(LazyList(ZERO, ONE, CHAR('a'), CHAR('b'))) + .dropWhile(depth(_) < 3) + .take(10).foreach(println)) + + @@ -525,59 +484,4 @@ List(1, 2, 3) == Vector(1, 2, 3) // again should not compile, but returns true -// I like best about Scala that it lets me often write -// concise, readable code. And it hooks up with the -// Isabelle theorem prover. - -// Puzzlers - -val month = 12 -val day = 24 -val (hour, min, sec) = (12, 0, 0) - -// use lowercase names for variable - - -//================== -val oneTwo = Seq(1, 2, 3).permutations - -if (oneTwo.length > 0) { - println("Permutations of 1,2 and 3:") - oneTwo.foreach(println) -} - -val threeFour = Seq(3, 4, 5).permutations - -if (!threeFour.isEmpty) { - println("Permutations of 3, 4 and 5:") - threeFour.foreach(println) -} - -//================== -val (a, b, c) = - if (4 < 5) { - "bar" - } else { - Some(10) - } - -//Because when an expression has multiple return branches, Scala tries to -//be helpful, by picking the first common ancestor type of all the -//branches as the type of the whole expression. -// -//In this case, one branch has type String and the other has type -//Option[Int], so the compiler decides that what the developer really -//wants is for the whole if/else expression to have type Serializable, -//since that’s the most specific type to claim both String and Option as -//descendants. -// -//And guess what, Tuple3[A, B, C] is also Serializable, so as far as the -//compiler is concerned, the assignment of the whole mess to (a, b, c) -//can’t be proven invalid. So it gets through with a warning, -//destined to fail at runtime. - - -//================ -// does not work anymore in 2.13.0 -val numbers = List("1", "2").toSet + "3" diff -r 289b85843ffd -r 557d18cce0f0 slides/slides05.pdf Binary file slides/slides05.pdf has changed diff -r 289b85843ffd -r 557d18cce0f0 slides/slides05.tex --- a/slides/slides05.tex Thu Dec 08 22:19:21 2022 +0000 +++ b/slides/slides05.tex Sat Dec 17 12:42:49 2022 +0000 @@ -3,6 +3,7 @@ \usepackage{../styles/slides} \usepackage{../styles/mygraphs} \usepackage{../styles/langs} +\usepackage{chessboard} %%\usepackage{../data} %%\usepackage[export]{adjustbox} \usetikzlibrary{shapes,arrows,shadows} @@ -182,7 +183,7 @@ \begin{minipage}{1.2\textwidth} \begin{itemize} \item SGTs still ongoing next week -\item LGT next week online Ask-Me-Anything (will be recorded, TEAMS link will be emailed and published on KEATS) +\item LGT next week online: Ask-Me-Anything (will be recorded, TEAMS link will be emailed and published on KEATS) \item tests might break over Christmas \end{itemize}\bigskip @@ -195,6 +196,16 @@ \end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] +\frametitle{Main 4: \knight-Tour} + +\begin{center} +\Large\bf hint +\end{center} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}[c] @@ -305,10 +316,10 @@ \frametitle{Plan for Today} \begin{itemize} +\item Polymorphic Types \item Implicits -\item Polymorphic Types \item Immutable OOP -\item Making Fun about Scala +%%\item Making Fun about Scala \end{itemize} \end{frame} @@ -480,12 +491,16 @@ \begin{itemize} \item Martin Odersky (EPFL) developed now Scala 3\medskip -\item I use Ammonite by Haoji Li\medskip +\item I use Ammonite by Haoyi Li\medskip \item Elm (\url{http://elm-lang.org})\ldots web applications with style\medskip \item Haskell, Ocaml, Standard ML, Scheme, \ldots \end{itemize} + +\begin{textblock}{5}(12,9) +\includegraphics[scale=0.15]{../pics/haojili.png} +\end{textblock} \end{frame} @@ -548,6 +563,11 @@ \end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}<1-10>[c,fragile] + + +\end{frame} + %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \end{document}