Last updated on Friday, January 10, 2025

Purely functional data structures

Welcome to the data structure exercises of CS-214!

Data structures are vital in programming: well-designed data structures make the retrieval and storage of information efficient.

In this exercise set, you will implement several data structures and use them in practice.

As before, exercises or questions marked ⭐️ are the most important.

We strongly encourage you to solve the exercises on paper first, in groups. After completing a first draft on paper, you may want to check your solutions on your computer. To do so, you can download the scaffold code (ZIP).

The data structure zoo

You are going to implement a few data structures on your own. For each data structure, we will provide you with its definition, an interface for the behavior of the data structure, and tests. You should read and understand the definition and complete your implementation according to the provided interface. Start on paper before writing code!

Warm-up: Lists as stacks

A stack is a container that stores items in a first-in-last-out (FILO) manner. It supports two operations: push and pop. push adds an item onto the top of a stack, and pop removes an item from the top. The earliest item that was pushed into a stack lies at the bottom of it; the most-recently pushed item is at the top. When popping items, the later an item comes, the earlier it is popped. That’s why stacks are FILO.

A stack is simply a list in disguise!

• An empty stack is an empty list Nil;
• Like the push operation of stack, new items are always added to the head of a list. For instance, after adding 42 to List(1, 2, 3) (which is the list 1 :: 2 :: 3 :: Nil) we get List(42, 1, 2, 3) (which is 42 :: 1 :: 2 :: 3 :: Nil).
• To access an element in a list, one also needs to first pop out all items that were added afterwards. For instance, to get 3 from List(1, 2, 3), we need to remove both 1 and 2 from the head of the list. This is like the pop operation of a stack.

Your task is to implement a stack that conforms to the following interface:

abstract class Stack[X]:
  /** Push an element into the stack. */
  def push(elem: X): Stack[X]

  /** Pop an element from the stack. Return None if the stack is empty. */
  def pop: Option[(X, Stack[X])]

  /** Check whether the stack is empty. */
  def isEmpty: Boolean

The methods are quite self-explanatory. We provide you with the following scaffold:

case class StackImpl[X](data: List[X]) extends Stack[X]:
  def push(elem: X): Stack[X] = ???
  def pop: Option[(X, Stack[X])] = ???
  def isEmpty: Boolean = ???

Additionally, you have to implement the apply method for the Stack object, which returns an empty stack.

object Stack:
  /** Create an empty stack. */
  def apply[X](): Stack[X] =
    ???

To test your implementation, run testOnly -- "*stack:*" in sbt console.

Double-ended queues ⭐

A Queue is a first-in-first-out (FIFO) container. In contrary to a stack, the earlier an item is pushed into a queue, the earlier it comes out of the queue.

A Double-Ended Queue (deque) is a more generalised queue that allows adding and removing elements from both ends.

A deque is typically implemented by two stacks, back-to-back. One stack stores elements from the front and the other from the back. For instance, the following deque:

    Front             Back
    1  ->  2  ->  3  ->  4

can be represented as (1 :: 2 :: Nil, 4 :: 3 :: Nil), if we use lists to implement stacks.

To understand how this deque works, let’s walk through an example of constructing it from an empty deque:

1. Start with an empty deque: (Nil, Nil).
2. After pushFirst(2): (2 :: Nil, Nil).
3. After pushFirst(1): (1 :: 2 :: Nil, Nil).
4. After pushLast(3): (1 :: 2 :: Nil, 3 :: Nil).
5. After pushLast(4): (1 :: 2 :: Nil, 4 :: 3 :: Nil).

Now we have the deque shown in the diagram above. When popping from either end, if that end’s list is non-empty, it’s straightforward:

For popFirst() when the front list is non-empty (x :: xs, back):

• Return element x.
• New state is (xs, back).

For popLast() when the back list is non-empty (front, x :: xs):

• Return element x.
• New state is (front, xs).

For example, starting with (1 :: 2 :: Nil, 4 :: 3 :: Nil):

1. After popFirst(): Returns 1, the new state is (2 :: Nil, 4 :: 3 :: Nil).
2. After popLast(): Returns 4, the new state is (2 :: Nil, 3 :: Nil).

The interesting part comes when we try to pop from an end that’s empty. If we try to popFirst() when the front list is empty, we need to restructure the deque by:

• Reversing the back list.
• Making it the new front list.
• Setting the back list to empty.

For example, starting with (Nil, 4 :: 3 :: 2 :: 1 :: Nil):

1. Reverse the back list: 1 :: 2 :: 3 :: 4 :: Nil.
2. Make it the new front list: (1 :: 2 :: 3 :: 4 :: Nil, Nil).
3. Then, popFirst() returns 1, and the new state is (2 :: 3 :: 4 :: Nil, Nil).

It is similar for popLast() when the back list is empty.

Now, your task is to implement the Deque data structure according to the following interface:

abstract class Deque[X]:
  /** Push an element to the front. */
  def pushFirst(elem: X): Deque[X]

  /** Pop an element from the front. */
  def popFirst: Option[(X, Deque[X])]

  /** Push an element to the back. */
  def pushLast(elem: X): Deque[X]

  /** Pop an element from the back. */
  def popLast: Option[(X, Deque[X])]

  /** Check whether the deque is empty. */
  def isEmpty: Boolean

pushFirst and pushLast push an item to the front-end and back-end of the queue respectively. popFirst and popLast remove an item from the respective ends. When the deque is empty, both popFirst and popLast return None. Otherwise, they return the removed item and the resulting deque.

We have provided you with a scaffold:

case class DequeImpl[X](front: List[X], back: List[X]) extends Deque[X]:
  def pushFirst(elem: X): Deque[X] = ???
  def popFirst: Option[(X, Deque[X])] = ???
  def pushLast(elem: X): Deque[X] = ???
  def popLast: Option[(X, Deque[X])] = ???
  def isEmpty: Boolean = ???

You should also complete the apply method of the Deque object which creates an empty deque:

object Deque:
  /** Create an empty deque. */
  def apply[X](): Deque[X] =
    ???

To test your implementation, implement it on the computer, fire up an sbt console and run testOnly -- "*deque:*".

Quadtrees

In this exercise, you will implement a quadtree, a hierarchical data structure used to partition a 2D space into smaller regions. Quadtrees are particularly useful for spatial indexing, such as efficiently managing points in a large map or image.

We have seen quad trees many times during the semester. This time, it’s your turn to implement them! You can read up about them on Wikipedia.

In this exercise, your task is to first understand quadtrees on your own, then implement them according to our requirements.

You need to implement a quadtree that stores a set of points on a 2D space. The definition of Point is:

case class Point(x: Int, y: Int)

We have also set up the Boundary class for you: it represents a rectangle region in 2D space.

case class Boundary(bottomLeft: Point, topRight: Point):
  /** Check whether this boundary is empty. */
  def isEmpty: Boolean =
    !(bottomLeft.x < topRight.x && bottomLeft.y < topRight.y)

  /** Check whether this boundary contains a point. */
  def contains(p: Point): Boolean =
    (p.x >= bottomLeft.x && p.x < topRight.x) && (p.y >= bottomLeft.y && p.y < topRight.y)

  /** Intersect this boundary with another. */
  def intersect(other: Boundary): Boundary =
    val startX = bottomLeft.x `max` other.bottomLeft.x
    val endX = topRight.x `min` other.topRight.x
    val startY = bottomLeft.y `max` other.bottomLeft.y
    val endY = topRight.y `min` other.topRight.y
    Boundary(Point(startX, startY), Point(endX, endY))

This time, we will implement the data structure in a style where data and logic are separated. Specifically:

• We have some data types to represent the data of the data structure: the tree nodes, the stored points, the connections, etc.
• Then, we define a set of operations on this data type, which manipulates the data: inserting, querying, etc.

The first step is to define the data type:

// hint: define tree nodes as a enum?
type QuadTree = Nothing

Then comes the logic part: we want you to define the following operations on a quadtree:

trait QuadTreeOps[T]:
  /** Create an empty quadtree on a `boundary` with a `capacity`. */
  def empty(boundary: Boundary, capacity: Int): T

  /** Insert a point into a quadtree. */
  def insert(tree: T, p: Point): T

  /** Return the points that fall within a boundary. */
  def query(tree: T, boundary: Boundary): List[Point]

Specifically, you have to complete this scaffold:

object QuadTreeImpl extends QuadTreeOps[QuadTree]:
  def empty(boundary: Boundary, capacity: Int): QuadTree = ???
  def insert(tree: QuadTree, p: Point): QuadTree = ???
  def query(tree: QuadTree, boundary: Boundary): List[Point] = ???

Here,

• the empty function creates an empty tree;
• the insert function inserts a point into the quadtree;
• and the query function queries the quadtree for points within a given boundary.

To test your implementation on the computer, run testOnly -- "*quadtree:*".

A little spellchecker ⭐

In this section, we will first implement a Trie data structure, and then use it to implement a spell checker.

Tries

Trie is a data structure for efficient string lookup.

Your first task is to understand how trie works on your own, and then implement this data structure according to the following interface:

abstract class Trie[X]:
  def find(key: String): Option[X]
  def delete(key: String): Trie[X]
  def insert(key: String, value: X): Trie[X]

The methods are self-explanatory.

We have provided you with a scaffold:

case class TrieImpl[X](next: Map[Char, TrieImpl[X]], value: Option[X]) extends Trie[X]:
  def find(key: String): Option[X] = None
  def delete(key: String): TrieImpl[X] = this
  def insert(key: String, value: X): TrieImpl[X] = this

In addition, you should complete the following method which returns an empty trie tree:

object TrieImpl:
  def apply[X](): TrieImpl[X] =
    ???

You can test your trie implementation on the computer with testOnly -- "*trie:*".

Spellchecking with tries ⭐

Now you will use the trie you just implemented in practice–building a spell checker!

The spell checker takes a text as input and returns a list of misspelled words:

trait SpellChecker:
  /** Spell-check the input text. Return a list of misspelled words. */
  def checkText(text: String): List[String] =
    tokenize(text).filterNot(checkWord)

  /** Check whether the `word` is in `dict`. */
  def checkWord(word: String): Boolean

We have set up the utility functions for splitting the text into words and normalizing them. Your main task is to implement the checkWord function, which determines whether the input word is well spelled.

The TrieSpellChecker is an implementation of this spell-checking interface using tries. You should complete the following scaffold:

class TrieSpellChecker(dict: Dict) extends SpellChecker:
  val trie: Trie[Unit] = build(dict)
  private def build(dict: Dict): Trie[Unit] = ???

  def checkWord(word: String): Boolean =
    // now this spell-checker is ALWAYS sound, though quite not complete :)
    false

The Dict is simply a List of strings:

type Dict = List[String]

Therefore, in checkWord you need to check whether the input word is inside the dictionary. Use a trie tree to do that. DO NOT use List.contains!

To test your implmentation, run testOnly -- "*spellcheck:*" in the sbt console.

© 2023, 2024 EPFL. All rights reserved.