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

とで要素をトラバースする必要がありheadます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 に答える