MyList - step 4

Add behavior: foreach, map, and filter. These are the bread-and-butter operations of functional collections. We’ll implement them recursively on our immutable, singly linked list.

• foreach visits each element and runs a side-effecting function (like printing).
• map transforms every element and returns a new list of the results.
• filter keeps only the elements that satisfy a predicate.

Exercise: add methods to MyList

trait MyList[A]:
  ...
  def foreach(f: A => Unit): Unit
  def map[B](f: A => B): MyList[B]
  def filter(p: A => Boolean): MyList[A]

Hints:

• Use structural recursion: handle Empty as the base case; for Cons, do work on head, then recurse on tail.
• Keep everything immutable. Construct new Cons nodes rather than mutating.

Solution: foreach

Empty

override def foreach(f: A => Unit): Unit = ()

Doing nothing for the empty list makes sense and returns Unit (written as ()).

Cons

override def foreach(f: A => Unit): Unit =
  f(head)
  tail.foreach(f)

Apply f to head, then recurse into the tail.

Solution: map

Empty

override def map[B](f: A => B): MyList[B] = Empty[B]()

Mapping over an empty list yields an empty list of the new type B.

Note: If Empty were declared as case object Empty extends MyList[Nothing], we could avoid specifying [B] here thanks to variance. We keep it simple for now and stay with EmptyB.

Cons

override def map[B](f: A => B): MyList[B] =
  Cons[B](f(head), tail.map(f))

Transform the head, then recursively map the tail, and rebuild a new list. You can omit [B] in Cons because the type is inferred from the return type: Cons(f(head), tail.map(f))

Solution: filter

Empty

override def filter(p: A => Boolean): MyList[A] = this

Filtering an empty list is still empty.

Cons

override def filter(p: A => Boolean): MyList[A] =
  if p(head) then Cons(head, tail.filter(p))
  else tail.filter(p)

Keep head if it matches the predicate p; otherwise drop it and continue with the tail.

Try it out

@main
def main(): Unit =
  val myList: MyList[Int] = MyList(1, 2, 3)

  myList.foreach(x => println(x + 2))         // prints 3, 4, 5
  println(myList.map(x => x * 2))             // MyList(2, 4, 6)
  println(myList.filter(x => x < 2))          // MyList(1)

Key ideas

• Recursion mirrors the list’s structure: Empty is the base case; Cons does work and recurses on tail.
• Immutability makes it natural to “return a new list” rather than modify in place.