Scala Setup and Familiarization

The graded mini-projects will start next week with the design of an interpreter and later a lexer, as we have not yet seen the principles of lexical analysis (the topic of next week).

The goal of this lab is to make sure you can program in Scala on your computer.

Scala setup

Please follow the instructions at the following link, if you have not set up a Scala 3 environment: https://docs.scala-lang.org/scala3/getting-started.html (Links to an external site.)

This is easy to do and should not take very long. Indeed, the coursier tool should be able to take care of installing everything you need with the command cs setup.

Create an SBT project in an empty filter using the command sbt new scala/scala3.g8, and you are all set to go.

IDE Setup

I would recommend using VSCode or IntelliJ. Both can be made to use the latest Metals language server implementation (https://scalameta.org/metals/). Metals can also be used with editors like vim and emacs.

Basic Scala implementations

We will reuse the functional list data structure presented in the lecture and implement a few operations on it. Here I will rename “List” to “Stack” and “Nil” to “Empty” to avoid potential clashes with the standard Scala library.

Paste the basic code into a file named Stack.scala in the src/main/scala folder of the project:

package lab01enum Stack[A]: case Empty() case Cons(head: A, tail: Stack[A])object Stack: extension [A](x: A) def ::(xs: Stack[A]): Stack[A] = Cons(x, xs)

To try out the code, type sbt in the console, and then type console to enter a REPL, where you can type Scala expressions to be evaluated:

sbt:scala3-simple> console

scala> import lab01.*, Stack.*

scala> val ls = 0 :: 1 :: 2 :: Empty()
val ls: lab01.Stack[Int] = Cons(0,Cons(1,Cons(2,Empty())))

Alternatively, create a Scala spreadsheet, which will show you the results of expression evaluations in real time. In VSCode, all you need is to create a file with extension .worksheet.sc in the same src folder (https://scalameta.org/metals/docs/editors/vscode/#worksheets):

import lab01.*, Stack.*

val ls = 0 :: 1 :: 2 :: Empty() // ls: Stack[Int] = Cons(0,Cons(1,Cons(2,Empty())))

Pretty-printing

Change the way lists are printed by overriding the toString method of List instances:

enum Stack[A]:
  case Empty()
  case Cons(head: A, tail: Stack[A])
  
  override def toString = "TODO"

For example, you could make the list 0 :: 1 :: 2 :: Empty() print as [0, 1, 2].

Flat-mapping

Implement a method to perform flat-mapping, meaning that a function passed in parameter is applied on each element of the list, producing new sub-lists, and the result is the concatenation of all these lists.

  def flatMap[B](f: A => Stack[B]): Stack[B] = ??? // TODO

For instance, ("a" :: "b" :: Empty()).flatMap(x => (x + "0") :: (x + "1") :: Empty()) should result in the list "a0" :: "a1" :: "b0" :: "b1" :: Empty().

Folding left and right

Implement a function named “foldr” that folds a list in a left-associative way, meaning that values on the left are processed first. Given an initial value z, and a list ls = (x0 :: x1 :: ... :: xn :: Empty()), then ls.foldl(z, f) should be equivalent to f( ... f(f(z, x0), x1)) ..., xn).

  def foldl[B](z: B, f: (B, A) => B): B = ??? // TODO

The simplest way to implement this uses recursion and no loops or mutation.

Now, implement “foldr”, whose behavior is to fold in a right-associative way. The expression ls.foldr(f) should be equivalent to f(x0, f(x1, ... f(xn, z) ... )).

Advanced question for the courageous

Try to express foldr in terms of foldl, and conversely.

Hint: the trick is to accumulate function values, starting from the identity.

Project 0