MyList - step 5

Combine and expand lists with concatenation and flatMap. These two operations unlock expressive transformations and composition.

• ++ (concatenation) glues two lists together.
• flatMap maps each element to a list and flattens the results.

Exercise: add ++ and flatMap

trait MyList[A]:
  ...
  infix def ++(other: MyList[A]): MyList[A]
  def flatMap[B](f: A => MyList[B]): MyList[B]

Hints:

• For ++, think in terms of rebuilding the left list while pointing the last node to the right list.
• For flatMap, use ++ to combine the list produced from the head with the recursively flatMapped tail.

Solution: concatenation (++)

Empty

override infix def ++(other: MyList[A]): MyList[A] = other

Appending anything to an empty list returns the other list unchanged.

Cons

override infix def ++(other: MyList[A]): MyList[A] =
  Cons(head, tail ++ other)

Rebuild the left list node by node, and when you reach the end (Empty), hook it up to other.

Walk-through:

[1,2,3] ++ [4,5,6]
Cons(1, [2,3] ++ [4,5,6])
Cons(1, Cons(2, [3] ++ [4,5,6]))
Cons(1, Cons(2, Cons(3, [] ++ [4,5,6])))
Cons(1, Cons(2, Cons(3, [4,5,6])))
[1,2,3,4,5,6]

Solution: flatMap

Empty

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

Flat-mapping an empty list yields an empty list (regardless of f).

Cons

override def flatMap[B](f: A => MyList[B]): MyList[B] =
  f(head) ++ tail.flatMap(f)

• Transform head into a list with f(head).
• Concatenate it with the flat-mapped tail.

Walk-through:

[1,2,3].flatMap(a => [a, a + 1])
[1,2] ++ [2,3].flatMap(f)
[1,2] ++ [2,3] ++ [3].flatMap(f)
[1,2] ++ [2,3] ++ [3,4] ++ [].flatMap(f)
[1,2] ++ [2,3] ++ [3,4] ++ []
[1,2,2,3,3,4]

Try it out

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

  println(myList ++ otherList)                      // MyList(1, 2, 3, 4, 5)
  println(myList.flatMap(a => MyList(a, a + 1)))    // MyList(1, 2, 2, 3, 3, 4)

Key ideas

• ++ structurally rebuilds the left list and attaches the right list at the end.
• flatMap is “map then flatten,” and becomes simple once ++ is available.