--- a/progs/lecture3.scala Fri Nov 30 03:44:27 2018 +0000
+++ b/progs/lecture3.scala Fri Nov 30 07:54:49 2018 +0000
@@ -515,70 +515,5 @@
-// Polymorphic Types
-//===================
-
-// You do not want to write functions like contains, first
-// and so on for every type of lists.
-def length_string_list(lst: List[String]): Int = lst match {
- case Nil => 0
- case x::xs => 1 + length_string_list(xs)
-}
-
-def length_int_list(lst: List[Int]): Int = lst match {
- case Nil => 0
- case x::xs => 1 + length_int_list(xs)
-}
-
-length_string_list(List("1", "2", "3", "4"))
-length_int_list(List(1, 2, 3, 4))
-
-//-----
-def length[A](lst: List[A]): Int = lst match {
- case Nil => 0
- case x::xs => 1 + length(xs)
-}
-length(List("1", "2", "3", "4"))
-length(List(1, 2, 3, 4))
-
-def map[A, B](lst: List[A], f: A => B): List[B] = lst match {
- case Nil => Nil
- case x::xs => f(x)::map_int_list(xs, f)
-}
-
-map_int_list(List(1, 2, 3, 4), square)
-
-
-
-
-
-
-// Cool Stuff
-//============
-
-
-// Implicits
-//===========
-//
-// For example adding your own methods to Strings:
-// Imagine you want to increment strings, like
-//
-// "HAL".increment
-//
-// you can avoid ugly fudges, like a MyString, by
-// using implicit conversions.
-
-
-implicit class MyString(s: String) {
- def increment = for (c <- s) yield (c + 1).toChar
-}
-
-"HAL".increment
-
-
-
-
-
-
--- a/progs/lecture4.scala Fri Nov 30 03:44:27 2018 +0000
+++ b/progs/lecture4.scala Fri Nov 30 07:54:49 2018 +0000
@@ -49,15 +49,19 @@
ls.distinct
-def distinctBy[B, C](xs: List[B], f: B => C, acc: List[C] = Nil): List[B] = xs match {
+def distinctBy[B, C](xs: List[B],
+ f: B => C,
+ acc: List[C] = Nil): List[B] = xs match {
case Nil => Nil
- case (x::xs) => {
+ case x::xs => {
val res = f(x)
if (acc.contains(res)) distinctBy(xs, f, acc)
else x::distinctBy(xs, f, res::acc)
}
}
+// distinctBy with the identity function is
+// just distinct
distinctBy(ls, (x: Int) => x)
@@ -71,7 +75,6 @@
def id[T](x: T) : T = x
-
val x = id(322) // Int
val y = id("hey") // String
val z = id(Set(1,2,3,4)) // Set[Int]
@@ -85,11 +88,12 @@
// - quantification
// Java has issues with this too: Java allows
-// to write the following, but raises an exception
-// at runtime
+// to write the following incorrect code, and
+// only recovers by raising an exception
+// at runtime.
-//Object[] arr = new Integer[10];
-//arr[0] = "Hello World";
+// Object[] arr = new Integer[10];
+// arr[0] = "Hello World";
// Scala gives you a compile-time error
@@ -112,7 +116,7 @@
case class Mammal(name: String) extends Animal
case class Reptile(name: String) extends Animal
-println(new Bird("Sparrow"))
+println(Bird("Sparrow"))
println(Bird("Sparrow").toString)
@@ -138,8 +142,9 @@
half.denom
-// in mandelbrot.scala I used complex (imaginary) numbers and implemented
-// the usual arithmetic operations for complex numbers
+// In mandelbrot.scala I used complex (imaginary) numbers
+// and implemented the usual arithmetic operations for complex
+// numbers.
case class Complex(re: Double, im: Double) {
// represents the complex number re + im * i
@@ -163,8 +168,9 @@
List(5, 2, 3, 4) sorted
-// to allow the notation n + m * i
+// ...to allow the notation n + m * i
import scala.language.implicitConversions
+
object i extends Complex(0, 1)
implicit def double2complex(re: Double) = Complex(re, 0)
@@ -174,9 +180,9 @@
-// all is public by default....so no public
-// you can have the usual restrictions about private values
-// and methods, if you are MUTABLE(!!!)
+// All is public by default....so no public is needed.
+// You can have the usual restrictions about private
+// values and methods, if you are MUTABLE !!!
case class BankAccount(init: Int) {
@@ -193,8 +199,8 @@
} else throw new Error("insufficient funds")
}
-// BUT since we are IMMUTABLE, this is virtually of not
-// concern to us.
+// BUT since we are completely IMMUTABLE, this is
+// virtually of not concern to us.
@@ -207,9 +213,9 @@
// A is the state type
// C is the input (usually characters)
-case class DFA[A, C](start: A, // starting state
- delta: (A, C) => A, // transition function
- fins: A => Boolean) { // final states
+case class DFA[A, C](start: A, // starting state
+ delta: (A, C) => A, // transition function
+ fins: A => Boolean) { // final states (Set)
def deltas(q: A, s: List[C]) : A = s match {
case Nil => q
@@ -248,7 +254,7 @@
dfa.accepts("baba".toList) // false
dfa.accepts("abc".toList) // false
-// another DFA test with a Sink state
+// another DFA with a Sink state
abstract class S
case object S0 extends S
case object S1 extends S
@@ -256,7 +262,7 @@
case object Sink extends S
// transition function with a sink state
-val sigma : (S, Char) :=> S =
+val sigma : (S, Char) => S =
{ case (S0, 'a') => S1
case (S1, 'a') => S2
case _ => Sink
@@ -268,24 +274,34 @@
dfa2.accepts("".toList) // false
dfa2.accepts("ab".toList) // false
+// we could also have a dfa for numbers
+val sigmai : (S, Int) => S =
+ { case (S0, 1) => S1
+ case (S1, 1) => S2
+ case _ => Sink
+ }
+
+val dfa3 = DFA(S0, sigmai, Set[S](S2))
+
+dfa3.accepts(List(1, 1)) // true
+dfa3.accepts(Nil) // false
+dfa3.accepts(List(1, 2)) // false
+
// NFAs (Nondeterministic Finite Automata)
-case class NFA[A, C](starts: Set[A], // starting states
- delta: (A, C) => Set[A], // transition function
- fins: A => Boolean) { // final states
+case class NFA[A, C](starts: Set[A], // starting states
+ delta: (A, C) => Set[A], // transition function
+ fins: A => Boolean) { // final states
// given a state and a character, what is the set of
// next states? if there is none => empty set
def next(q: A, c: C) : Set[A] =
Try(delta(q, c)) getOrElse Set[A]()
- def nexts(qs: Set[A], c: C) : Set[A] =
- qs.flatMap(next(_, c))
-
// depth-first version of accepts
def search(q: A, s: List[C]) : Boolean = s match {
case Nil => fins(q)
@@ -316,7 +332,7 @@
nfa.accepts("ac".toList) // false
-// Q: Why the kerfuffle about the polymorphic types in DFAs/NFAs
+// Q: Why the kerfuffle about the polymorphic types in DFAs/NFAs?
// A: Subset construction
def subset[A, C](nfa: NFA[A, C]) : DFA[Set[A], C] = {