Midterm

Topics Covered

• Lists, maps, tuples, Option in Scala
• Recursive functions in Scala
• Left and right folds
• map and flatMap
• Combinator parsers
• Case classes and pattern matching
• SL1

Topics Not Covered

• Functions with variable arguments
• Regular expressions
• Writing SL1 programs
• bash
• Racket/Scheme

Exam Rules

• You may put any files that you like on your laptop, including your and my homework and lab solutions, the slides, and the Scala API (also contains the Scala combinator API—unzip the file in the jars directory).
• You may NOT use the Internet for anything during the exam other than accessing your Git repo.
• You may NOT communicate with anyone other than the exam proctor.
• Immediately before the exam, run git pull to get the starter file into your repo.
• Do all your exam work in the folder called midterm in your repo.
• Put all your work into the files problem1.scala, problem2.scala, and so on, inside the src/main/scala directory.
• You must run git commit every 10 minutes.
• When the exam is over, run git push to push your repo.
• The exam is 70 minutes long.

Practice Exam

• Compute the alternating sum a(0) - a(1) + a(2) - a(3) ... of a list of integers, using recursion and a helper function.
• Compute the alternating sum of a list of integers using a fold. Hint: In the intermediate steps, transform a pair (partial result, ±1).
• Given two lists of integers, produce a list of all their differences using map/flatMap. For example, allDifferences(List(1, 5), List(2, 3, 4)) is List(-1, -2, -3, 3, 2, 1)
• Change the grammar for arithmetic expressions to a grammar for string expressions. Support
  • Concatenating strings s + t
  • Replicating strings by an integer number s * n
  • Extracting substrings s[i, j]
• Modify SL1 so that it supports Boolean values true and false. Make if expect a Boolean value in the condition, not an integer. Add predefined functions and, or, and not. (Make a BoolOp, like in the homework.)

Additional Practice Questions

1. Write a function that takes a list and drops every second element, e.g. (1, 2, 3, 4, 5) -> (1, 3, 5). Use fold.
2. Write a function that takes a list and swaps adjacent elements, e.g. (1, 2, 3, 4, 5) -> (2, 1, 4, 3, 5). Use fold.
3. Write a Scala program that parses Lisp expressions. A Lisp expression has the form ( e₁ e₂ ... ), where e_i is a list, integer, or identifier, or 'e, where e is a list or identifier.
4. Change the arithmetic parser from the lab of lecture 10 so that it handles expressions of the form sqrt e, where e is an expression. (Compute the integer square root.) The sqrt operator should bind more strongly than multiplication—sqrt 4 * 10 is 20.