MyList - step 3

Build up lists by adding elements and make construction ergonomic. In this step we will:

• Add an add method that prepends an element.
• Provide a + operator as a friendly alias.
• Create a MyList companion object with an apply method so you can write MyList(1,2,3).

Why prepend? Our MyList is immutable and singly linked. Prepending is O(1) (make one new node that points to the rest), while appending would be O(n) because you’d have to walk to the end first.

Exercise 1: add

Goal: give all MyList instances a method to add a new head in front of the list.

trait MyList[A]:
  ...
  def add(element: A): MyList[A]

• Implement add in Empty and Cons.
• Try it: Empty().add(1).add(2).add(3)
• Hint: adding to either Empty or Cons returns a new Cons with element as head and the current list as tail.

Exercise 2: + operator

Let’s make the same operation feel natural with an operator.

trait MyList[A]:
  ...
  def +(element: A): MyList[A]

• Implement + as an alias for add.
• Try it: Empty() + 1 + 2 + 3
• Hint: in Scala, symbols like + are valid method names. Using the infix modifier lets you omit dots and parentheses when calling it.

Exercise 3: companion object apply

Build lists from a variable number of arguments.

object MyList:
  def apply[A](elements: A*): MyList[A]

• Implement apply so that MyList(1,2,3) creates a list 1 -> 2 -> 3.
• Hint: a small tail-recursive helper that accumulates using + works well. Remember that + prepends, so you’ll probably want to process elements in reverse order to preserve the original left-to-right order.

Solution: add

Empty

override def add(element: A): MyList[A] = Cons(element, this)

Adding to Empty yields a new Cons whose tail is this (the empty list).

Cons

override def add(element: A): MyList[A] = Cons(element, this)

Adding to a non-empty list simply creates a new head and points its tail at the current list.

Put it in the trait

The implementations are identical, so we can provide a default on the trait and remove the duplicates in the cases:

trait MyList[A]:
  ...
  def add(element: A): MyList[A] = Cons(element, this)

Try it

@main
def main(): Unit =
  val myList: MyList[Int] = Empty().add(1).add(2).add(3)
  println(myList) // MyList(3, 2, 1) once we add pretty printing in step 2

Note the reverse order: because we always prepend, the last added element ends up at the front.

Solution: + operator

trait MyList[A]:
  ...
  def add(element: A): MyList[A] = Cons(element, this)
  infix def +(element: A): MyList[A] = add(element)

• • is just a method name.
• With infix, you can write Empty() + 1 instead of Empty().+(1).

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

Solution: companion object apply

object MyList:
  def apply[A](elements: A*): MyList[A] =
    def build(rem: Seq[A], acc: MyList[A]): MyList[A] =
      if rem.isEmpty then acc
      else build(rem.tail, acc + rem.head)

    build(elements.reverse, Empty())

• elements: A* declares a varargs parameter.
• We accumulate using our + method.
• Because + prepends, we reverse the incoming sequence first to preserve the original order.

Try it

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

Key ideas

• Prepending to a singly linked immutable list is O(1) and natural.
• Providing an operator and a companion object makes APIs ergonomic without changing the underlying model.