MyList - step 5

Concat and Flatmap

We will add two new methods to MyList

• ++ (concatenation)
• flatMap

Exercise

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

Solution Concatenation

Empty

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

Another list added to an empty list gives the other list

Cons

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

We could also write this as

Cons(head, tail ++ other)

A recursion example flow

[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 => B): MyList[B] = Empty[B]()

Like the map method flatMap returns an Empty list

Cons

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

With the implementation of concatenation (++) flatMap becomes simple
The function call f(head) returns a MyList
which is concatenated with the recursive call of flatMap on the tail

A recursion example flow

[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]

main

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

  println( myList ++ otherList )

  println( myList.flatMap(a => MyList(a, a + 1)) )

// MyList(1, 2, 3, 4, 5)
// MyList(1, 2, 2, 3, 3, 4)