0

我需要在 Scala 中实现我自己的 List 类。我已经实现：

trait List[+A] {
  /** The first element */
  def head: A
  /** The rest of the elements */
  def tail: List[A]

  def map[B](f: A => B): List[B]
  def flatMap[B](f: A => List[B]): List[B]
  def filter(f: A => Boolean): List[A]

  // 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)
  }
}

/** The empty list, also known as Nil */
case object Empty extends List[Nothing] {
  def head = throw new UnsupportedOperationException("Empty.head")
  def tail = throw new UnsupportedOperationException("Empty.tail")

  def map[B](f: Nothing => B): List[B] = Empty
  def flatMap[B](f: Nothing => List[B]): List[B] = Empty
  def filter(f: Nothing => Boolean): List[Nothing] = Empty

  override def toString = "Empty"
}

现在我需要实现 filter、flatMap 和 Map 方法：

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


    //def map[B](f: A => B): List[B] = ???
      //def flatMap[B](f: A => List[B]): List[B] = ???
      def filter(predicate: A => Boolean): List[A] = {        
      }

例如方法filter(predicate: A => Boolean): List[A]我如何遍历这个列表中的每个元素？如何检查给定谓词是真还是假？（试过if(predicate(head))- 由于某种原因不起作用。）谢谢你的帮助。

4

2 回答 2

3

您需要使用headand遍历元素tail：

def filter(f: A => Boolean): List[A] = {
  def loop(xs: List[A], ys: List[A]): List[A] =
    if (xs == Empty) ys else loop(xs.tail, if (f(xs.head)) NonEmpty(xs.head, ys) else ys)
  loop(this, Empty).reverse
}

这个实现可以定义在List. 你最不需要的就是reverse方法。您可以以相同的方式实现它filter- 使用内部方法遍历所有元素。

您可以使用非尾递归实现代替reverse，该实现不得反转并且可以在子类中实现：

def filter(f: A => Boolean): List[A] =
  if (f(head)) NonEmpty(head, tail filter f)
  else tail filter f

其他方法可以类似的方式定义。

于 2012-11-09T14:24:05.663 回答
1

通常，当您只是住在 Fairyland并假装（几乎）一切都已经工作时，递归会变得更容易。

假设 filter 已经按照您的要求进行了操作，您将如何使用 filter 使其适用于另一个元素？

好吧，您可以决定是否要包含列表的第一个元素（取决于f），并让过滤器“已经工作”来处理其余部分。然后只需连接列表。

def filter(f: A => Boolean) : List[A] = {
  if (f(head)) NonEmpty(head, tail.filter(f))
  else tail.filter(f)
}
于 2012-11-09T14:32:24.983 回答