实现flatMap函数

Question

免责声明:这是家庭作业的一部分。我想实现自定义列表对象的flatMap。我已经成功地实现了map，但我在flatMap上遇到了问题。我不知道如何扁平化从map获得的列表列表。我不知道我是否真的应该使用地图。

trait List[+A] {
  /** The first element */
  def head: A
  /** The rest of the elements */
  def tail: List[A]
  def flatMap[B](f: A => List[B]): List[B]
  def map[B](f: A => B): List[B]

  // Concatenate two lists
  def concat[B >: A](that: List[B]): List[B] = this match {
    case Empty => that
    case NonEmpty(head, tail) => NonEmpty(head, tail concat that)
  }
}

case object Empty extends List[Nothing] {
  def head = throw new UnsupportedOperationException("Empty.head")
  def tail = throw new UnsupportedOperationException("Empty.tail")
  def flatMap[B](f: Nothing => List[B]): List[B] = Empty
  def map[B](f: Nothing => B): List[B] = Empty

  override def toString = "Empty"
}

case class NonEmpty[A](head: A, tail: List[A]) extends List[A] {

  def map[B](f: A => B): List[B] = {

    NonEmpty(f(head), tail.map(f))

  }
def flatMap[B](f: A => List[B]): List[B] = {
    val a = this.map(f)
    for (x <- a; y <- x) yield y
  }
}

Answer 1

你必须为一个长度为n的列表写flatMap。假设你已经为一个长度为n-1的列表解决了这个问题，试着解决它。如果你能做到这一点，那么你已经解决了问题，因为n => n-1 => ... => 1 => 0，并且对于0你已经有了一个解决方案。

这种思想适用于您的列表，因为它是一个递归类型。

您已经对map执行了此操作，对flatMap也执行相同的操作。这两个函数都是从ListA到ListB的转换，唯一的区别是它们可以使用的工具不同，map有一个将A转换为B的函数，而flatMap有一个将A转换为ListB的函数

Answer 2

由于这是一个家庭作业，我不想给你一个完整的解决方案，只是一些提示。

1. 你不需要map来实现flatMap (实际上反过来做起来更容易)
2. 你需要的一切都有了(flatMap接受一个返回List[B]的函数，List有concat首先是D13的flatMap ;-)