Meeting 04 - Data Types

Bor-Yuh Evan Chang

Thursday, September 5, 2024

\(\newcommand{\TirName}[1]{\text{#1}} \newcommand{\inferrule}[3][]{ \let\and\qquad \begin{array}{@{}l@{}} \TirName{#1} \\ \displaystyle \frac{#2}{#3} \end{array} } \newcommand{\infer}[3][]{\inferrule[#1]{#2}{#3}} \)

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 Friday Monday 6pm (with the 24-hour grace period for when “stuff happens”)

Announcements

• Bug in the filterPairsByBound (and the filterPairsByBoundLinearTime) "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

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)

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
3

awaitingCallback: 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

42

We 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.