java.lang.IndexOutOfBoundsException: 3 scala.collection.LinearSeqOps.apply(LinearSeq.scala:117) scala.collection.LinearSeqOps.apply$(LinearSeq.scala:114) scala.collection.immutable.List.apply(List.scala:79) ammonite.$sess.cmd1$Helper.<init>(cmd1.sc:6) ammonite.$sess.cmd1$.<clinit>(cmd1.sc:7)
Meeting 04 - Data Types
In-Class Slides
In-Class Jupyter
In-Class Jupyter of Homework 1
Book Chapter
Reminders
- Recitation sections are lab sections — bring your laptop!
- This Week: Finishing HW1
Announcements
- HW 1 + Quiz 1 due
FridayMonday 6pm (with the 24-hour grace period for when “stuff happens”)
Announcements
- Bug in the
filterPairsByBound(and thefilterPairsByBoundLinearTime)"test1".- We’ll look at the fix in a moment and learn something from it.
- If you accepted the assignment to create your homework repo after 12am this morning, you have the updated version.
- If you have the old version, the easiest way to update is to download the new version from https://github.com/csci3155-f24/pppl-hw1 and then copy the cells that you’ve edited so far.
- If you want to get experience merging with git, there are some details on Piazza.
Today
- Triage Your Questions
- Finish Chapter 4 Binding and Scope: A Scala crash course.
- Chapter 5 Data Types: A Scala crash course.
Your Questions?
- Review:
- What is static type checking? What is static versus dynamic?
- What is a value environment?
Your Questions?
Lists
Nil and Cons
empty: List[Int] = List() nil: List[Int] = List() numbers: List[Int] = List(1, 2, 3) consZero: List[Int] = List(0, 1, 2, 3)
Note that there is no imperative update here. A List is an immutable, functional data structure. Prepending to numbers does not change it. Rather consZero is bound to a new list.
Nil and Cons
consTen: List[Int] = List(10, 1, 2, 3) numbersHead: Int = 1 consZeroHead: Int = 0 consTenHead: Int = 10
Because Lists are immutable, prepending is still a constant-time operation (i.e., \(O(1)\)). The consZero and consTen can share the same tail (i.e., numbers).
How many nodes are needed total to represent the lists numbers, consZero, and consTen? 5
Immutability and Efficiency
consZeroTail: List[Int] = List(1, 2, 3) consTenTail: List[Int] = List(1, 2, 3) res7_2: Boolean = true res7_3: Boolean = true res7_4: Boolean = false res7_5: Boolean = true
where in Scala, eq is the reference equality operator, while == is structural equality.
This is the essence of hash consing.
Lists and Pattern Matching
numbers: List[Int] = List(1, 2, 3)
Lists and Pattern Matching
defined function isEmpty res11_1: Boolean = false
Linear-Time Append
numbers: List[Int] = List(1, 2, 3) res13_1: List[Int] = List(1, 2, 3, 4, 5, 6)
Why must append ::: be a linear-time operation?
Iterators
1
2
3
1
2
3
1
2
3
1
2
3awaitingCallback: Int => Unit => Unit = ammonite.$sess.cmd15$Helper$$Lambda$2088/0x0000000800b1e840@473a27d0
Imperative Sum
defined function sum res16_1: Int = 6
Functional Sum
defined function sum res18_1: Int = 6 l: List[Int] = List(1, 2, 3, 4, 5, 6) res18_3: Int = 12 res18_4: Int = 12
Not only does the sum definition become a one-liner, but it decouples the scheduling of work on each element of the list and lets the library implement that (e.g., sequentially left-to-right, concurrently, or even distributed!).
We will consider in subsequent chapters how to effectively use such higher-order methods. For the moment, simply recognize that such higher-order methods exist and is the idiomatic way to work with Lists. Furthermore, this API design is particularly powerful and becoming commonplace in almost all languages (even in Java!). For example, in big-data applications, this design enables streaming where the data can be consumed in an online manner as a stream.
Options
res20_0: Option[Int] = None res20_1: Some[Int] = Some(value = 42) defined function div
Options and Error Handling
java.util.NoSuchElementException: head of empty list scala.collection.immutable.Nil$.head(List.scala:629) scala.collection.immutable.Nil$.head(List.scala:628) ammonite.$sess.cmd22$Helper.<init>(cmd22.sc:2) ammonite.$sess.cmd22$.<clinit>(cmd22.sc:7)
Option is a collection
42We can think of an Option value as a 0-or-1 element list and thus all of the higher-order iteration methods are available.
Maps
Maps are particularly useful data structures for storing associations between keys and values.
defined type Env env: Env = Map("nOranges" -> 4, "nApples" -> 7, "nPears" -> 10)
java.util.NoSuchElementException: key not found: nDogs scala.collection.immutable.Map$Map3.apply(Map.scala:399) ammonite.$sess.cmd28$Helper.<init>(cmd28.sc:2) ammonite.$sess.cmd28$.<clinit>(cmd28.sc:7)
For example, we describe value environments for a programming language as maps from variables to values.
Extending Maps
env_: Map[String, Int] = Map( "nOranges" -> 4, "nApples" -> 7, "nPears" -> 10, "nBananas" -> 17 ) res30_1: Env = Map("nOranges" -> 4, "nApples" -> 7, "nPears" -> 10) res30_2: Map[String, Int] = Map( "nOranges" -> 4, "nApples" -> 7, "nPears" -> 10, "nBananas" -> 17 )
A functional update is sometimes where one might want to intentionally shadow to prevent referencing the unextended env in a particular scope.
Data Classes
defined class Dog samuel: Dog = Dog(name = "Samuel", breed = "Alsatian", age = 11) res32_2: String = "Samuel" breed: String = "Alsatian"
Defining Option
defined trait MyOption defined object MyNone defined class MySome none: MyOption = MyNone some: MyOption = MySome(i = 42) defined function getOrElse res34_6: Int = 0 res34_7: Int = 42
Parametric Polymorphism
defined trait MyOption defined object MyNone defined class MySome none: MyOption = MyNone some: MyOption = MySome(i = 42) defined function getOrElse res36_6: Int = 0 res36_7: Int = 42
Observe that getOrElse (as well as the MyNone and MySome constructors) have a type parameter list (written brackets []) and a value parameter list (written in parentheses ()).
The getOrElse function is generic in the parametrized type A. Being generic, the getOrElse function is also called parametric polymorphic.