实现flatMap函数

Question

免责声明:这是家庭作业的一部分。我想为自定义List对象实现flatMap。我已经成功地实现了地图，但我有问题与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

因为这是一个作业，我不想给你们一个完整的解决方案，只是一些提示。

1. 你不需要map来实现flatMap(实际上，相反的方式更容易做到)
2. 你有你需要的一切(flatMap需要一个函数，返回List[B]和List有concat定义)
3. 先实现Empty的flatMap;-)

Answer 2

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

这种想法适合你的List，因为它是递归类型。

你已经对map做了这个，对flatMap做同样的事情。两个函数都是从List[a]到List[B]的转换，唯一的区别是它们可以使用的工具，map有一个将a转换为B的函数，而flatMap有一个将a转换为List[B]的函数