Discussion 9: Gleam Data

Attendance

Your TA will come around during discussion to check you in. You can start on the worksheet before being checked in; you don't need to wait for your TA to get started.

If you didn't attend for a good reason (such as being sick), fill out this form (within 2 weeks of your discussion): attendance form

Getting Started

Say your name and something you've practiced for a while, such as playing an instrument, juggling, or martial arts. Did you discover any common interests among your group members?

Lists in Gleam

A Gleam list is either empty ([]) or a first element followed by the rest of the list ([first, ..rest]). A case expression can match these patterns to choose between a base case and a recursive case.

For example, here's a function that sums a list of numbers.

/// The sum of the elements of s.
pub fn sum(s: List(Int)) -> Int {
  case s {
    [] -> 0
    [first, ..rest] -> first + sum(rest)
  }
}

Some useful sections from the Gleam appendix of Composing Programs:

• Lists
• List patterns
• List recursion
• Multiple subjects

Q1: Interleave

Implement interleave, which takes two lists s and t and returns a new list that alternates elements from both, starting with s.

If one list is shorter than the other, interleave takes elements from both until the shorter one runs out, then appends the remaining elements of the longer list to the end. If either list is empty, it returns the other.

For example:

assert interleave([1, 2, 3], [4, 5, 6]) == [1, 4, 2, 5, 3, 6]
assert interleave([7, 8, 9, 10], [11, 12]) == [7, 11, 8, 12, 9, 10]

/// A new list that alternates elements from s and t, starting with s.
/// When one list runs out, the remaining elements of the other are appended
/// to the end. If either list is empty, the other is returned.
pub fn interleave(s: List(a), t: List(a)) -> List(a) {
  todo

}

Q2: No Repeats

Implement no_repeats, which takes a list of numbers s and returns a list of all the unique elements of s in the order they first appear, with no repeats. In other words, remove every duplicate while keeping the first occurrence.

For example:

assert no_repeats([5, 4, 5, 4, 2, 2]) == [5, 4, 2]

import gleam/list

/// A list of the unique elements of s in the order of first appearance.
pub fn no_repeats(s: List(Int)) -> List(Int) {
  todo

}

Hint 1: Removing Repeats (at the end)

Results, Dictionaries, and Records

Some more useful sections from the Gleam appendix of Composing Programs:

• Results
• Dict module
• Records
• Record updates

Q3: Find Repeated

A function that might not successfully return a value can return a Result, which is either Ok(value) or an Error. Error(Nil) means there is no additional data about the error (which is common).

Implement find_repeated, which takes a list s and a positive integer n. It returns Ok(x), where x is the first item to appear at least n times, or Error(Nil) if no item appears n or more times.

assert find_repeated([1, 2, 2, 1], 2) == Ok(2)  // 2 appears twice before 1 does
assert find_repeated([1, 2, 3], 2) == Error(Nil)

Its helper finder keeps track of how many times each item has appeared using a Dict. Here are the only functions you need:

• dict.new() returns an empty Dict.
• dict.get(d, key) returns Ok(value) if key is stored in d with value, or Error(Nil) if it isn't.
• dict.insert(d, key, value) returns a new Dict that also stores value for key, replacing any value stored there before. It doesn't change d.

let counts = dict.insert(dict.new(), "a", 1)
assert dict.get(counts, "a") == Ok(1)
assert dict.get(counts, "b") == Error(Nil)

import gleam/dict.{type Dict}

/// Ok of the first item to appear n times in s, or Error(Nil) if no item
/// appears n times, where n is positive.
pub fn find_repeated(s: List(a), n: Int) -> Result(a, Nil) {
  finder(s, n, dict.new())
}

/// counts holds the number of times that each item has already appeared.
pub fn finder(s: List(a), n: Int, counts: Dict(a, Int)) -> Result(a, Nil) {
  todo

}

Hint 2: Template (at the end)

Q4: Email

An email system has one server, which stores each person's inbox and a list of emails it could not deliver. Gleam values are immutable, so sending an email can't change an inbox. Instead, each function below takes a Server and returns a new Server.

pub type Email {
  Email(msg: String, from: String, to: String)
}

pub type Inbox {
  Inbox(owner: String, emails: List(Email))
}

pub type Server {
  Server(boxes: Dict(String, Inbox), undelivered: List(Email))
}

A record update creates a new record that copies an existing record's fields, except the ones it names. For example, Inbox(..inbox, emails: []) is an Inbox with the same owner as inbox and no emails. Use record updates in add_inbox and send.

let server = Server(dict.new(), [])
let server = add_inbox(server, "eumaeus")
let server = add_inbox(server, "odysseus")

let ask = Email("Bringing vengeance?", "eumaeus", "odysseus")
let server = send(server, ask)
assert dict.get(server.boxes, "odysseus") == Ok(Inbox("odysseus", [ask]))

let server = respond(server, ask, "Bringing it all!")
let reply = Email("Bringing it all!", "odysseus", "eumaeus")
assert dict.get(server.boxes, "eumaeus") == Ok(Inbox("eumaeus", [reply]))

let plea = Email("Vengeance, father!", "polyphemus", "poseidon")
let server = send(server, plea)
assert server.undelivered == [plea]

/// Add an empty inbox for this owner to the server.
pub fn add_inbox(s: Server, owner: String) -> Server {
  todo

}

/// Add the email to the front of the inbox of the person it is to. If that
/// person has no inbox, add the email to the front of the undelivered list.
pub fn send(s: Server, email: Email) -> Server {
  case dict.get(s.boxes, email.to) {
    Ok(inbox) -> todo

    Error(Nil) -> Server(..s, undelivered: [email, ..s.undelivered])
  }
}

/// Send a reply to the email with the given message. The reply is from the
/// person the email was to, and it is to the person the email was from.
pub fn respond(s: Server, email: Email, message: String) -> Server {
  todo

}

Hint 3: add_inbox (at the end)

Hint 4: send (at the end)

Hint 5: respond (at the end)

pub fn finder(s: List(a), n: Int, counts: Dict(a, Int)) -> Result(a, Nil) {
  case s {
    [] -> ...
    [x, ..rest] -> {
      let k = case dict.get(counts, x) {
        ...
      }
      case k == n {
        True -> ...
        False -> finder(rest, n, ...)
      }
    }
  }
}

pub fn add_inbox(s: Server, owner: String) -> Server {
  Server(..s, boxes: dict.insert(_, _, _))
}

Ok(inbox) -> {
  let updated = Inbox(..inbox, emails: [_, .._])
  Server(..s, boxes: dict.insert(_, _, _))
}

pub fn respond(s: Server, email: Email, message: String) -> Server {
  send(s, Email(_, _, _))
}