2

以下のScalaメソッドでは、リストはメソッドによってどのようにxsトラバースされnthますか？は再帰的に呼び出されますが、トレイトではパラメーター化されたタイプのリストが返されるだけなxs.tailので、テールが常に同じ値であるとは限らないのはなぜですか？def tailList

object nth {

  def nth[T](n: Int, xs: List[T]): T =
    if (xs.isEmpty) throw new IndexOutOfBoundsException
    else if (n == 0) xs.head
    else {
        nth(n - 1, xs.tail)
        }                                 //> nth: [T](n: Int, xs: week4.List[T])T
  val list = new Cons(1, new Cons(2, new Cons(3, new Nil)))
  nth(2 , list)   > res0: Int=3   
}

trait List[T] {
  def isEmpty: Boolean
  def head: T
  def tail: List[T]
}
class Cons[T](val head: T, val tail: List[T]) extends List[T]{
  def isEmpty = false
}
class Nil[T] extends List[T]{
  def isEmpty = true
  def head : Nothing = throw new NoSuchElementException("Nil.head")
  def tail : Nothing = throw new NoSuchElementException("Nil.tail")
}
4

2 に答える 2

7

はList再帰的な構造です。短所に関するウィキペディアの記事を参照してください。これはその記事からです：

ここに画像の説明を入力してください

最初に使用する構造はですnew Cons(42, new Cons(69, new Cons(613, new Nil)))。このtailメソッドはのインスタンスも返しますが、これは同じリストList[Int]ではなく、右向きの矢印の1つに続くサブリストです。

したがって、あなたの例で、から始める場合は、とCons(1, Cons(2, Cons(3, Nil)))しnます2。

  • 関数の最初の反復では、次のnthように尋ねます。Cons(1, Cons(2, Cons(3, Nil)))空ですか？いいえ！ですかn == 0？いいえ。尾を使って繰り返し、nデクリメントします。
  • この2回目の反復では、次のように質問します。Cons(2, Cons(3, Nil))空ですか（これもList[Int]）？いいえ、ですかn == 0？いいえ（1今です）。次の再帰に進みます。
  • 3回目の反復では、次のように質問します。空Cons(3, Nil)ですか？いいえ、ですn == 0。はい！したがって、頭が。であるものを返しCons(3, Nil)ます3。
于 2013-01-08T17:18:59.783 に答える
3

リストタイプを再帰的に定義しました。これは、新しいリストを作成するために別のリストを使用していることを意味します。当然、どういうわけか最初のリストを作成する必要があります。そのため、Nilを定義しました。

したがって、他のリストなしで空のリストを作成できます。

val empty = new Nil[Int]                  //> empty  : Nil[Int] = Nil@1f93f8

すでに作成されたリストを使用して空ではないリストを作成できます。n-1サイズのリストがある場合は、新しいリストが古いリスト（テール）に加えて新しいリストと同じであると言って、nサイズのリストを作成できます。エレム（頭）：

val oneSize = new Cons(1, empty)          //> oneSize  : Cons[Int] = Cons@b159eb

oneSizeの尻尾を調べると、それはと同じオブジェクトであることがわかります。empty

oneSize.tail                              //> res0: List[Int] = Nil@1f93f8

oneSizeリストを使用して、2つの要素を持つリストを定義しましょう。

val twoSize = new Cons(2, oneSize)        //> twoSize  : Cons[Int] = Cons@18654ae

テールを調べると、oneSizeリストが得られます。

twoSize.tail                              //> res1: List[Int] = Cons@b159eb

したがって、tailを再度使用すると、以前と同じように空のリストを再度取得する必要があります。実際、次のようになります。

twoSize.tail.tail                         //> res2: List[Int] = Nil@1f93f8

出来上がりです。n番目の関数と同じように、リストを繰り返し処理しました。

于 2013-01-08T18:36:51.410 に答える