Проблема в том, как flatMap устраняет ноль элементов

Question

Я работаю над книгой «Функциональное программирование в Scala», и в конце главы о структурах данных вас просят реализовать метод filter в терминах flatMap. Вот необходимые функции и реализации:

sealed trait List[+A]

case object Nil extends List[Nothing]

case class Cons[+A](head: A, tail: List[A]) extends List[A]

object List {
  def apply[A](as: A*): List[A] = {
    if (as.isEmpty) Nil
    else Cons(as.head, apply(as.tail: _*))
  }

  def append[A](l1: List[A], l2: List[A]): List[A] = {
    foldRight(l1, l2)((elem, acc) => Cons(elem, acc))
  }

  def concat[A](ls: List[List[A]]): List[A] = {
    foldLeft(ls, Nil: List[A])(append)
  }

  def map[A, B](l: List[A])(f: A => B): List[B] = {
    foldRight(l, Nil: List[B])((elem, acc) => Cons(f(elem), acc))
  }

  def filter[A](l: List[A])(f: A => Boolean): List[A] = {
    List.flatMap(l)(a => if (f(a)) List(a) else Nil)
  }

  def flatMap[A, B](l: List[A])(f: A => List[B]): List[B] = {
    concat(map(l)(f))
  }

  def foldRight[A, B](l: List[A], z: B)(f: (A, B) => B): B = {
    l match {
      case Nil => z
      case Cons(h, t) => f(h, foldRight(t, z)(f))
    }
  }

  def foldLeft[A, B](l: List[A], z: B)(f: (B, A) => B): B = {
    l match {
      case Nil => z
      case Cons(h, t) => foldLeft(t, f(z, h))(f)
    }
  }
}

Фактический вызов функции здесь:

val x = List(1, 2, 3, 4, 5)

List.filter(x)(_ < 3)

Насколько я могу понять, после шага карты у вас будет список, который выглядит следующим образом: Cons(Cons(1, Nil), Cons(2, Nil), Cons(Nil, Nil)...

У меня проблемы с просмотром, где элементы, которые Nil отфильтрованы из конечного результата.

Answer 1

Они не "отфильтрованы". Они просто исчезают после применения concat в списке списков, потому что конкатенация с пустым списком ничего не делает.