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