Example9.2

「Example9.2」の編集履歴（バックアップ）一覧はこちら

Example9.2 - (2011/02/24 (木) 08:46:19) の１つ前との変更点

追加された行は緑色になります。

削除された行は赤色になります。

#co(){
9.2 Definition of class List I: First Order Methods 

Lists are not built in in Scala; they are defined by an abstract class List, which comes with two subclasses for :: and Nil. In the following we present a tour through class List. 
}

** 9.2 リストクラスの定義Ⅰ:一階メソッド

リストは Scala では組み込み型ではありません。抽象クラス List として定義され、２つのサブクラス :: と Nil があります。以降では、クラス List のツアーに出かけます。

 package scala 
 abstract class List[+A] {

#co(){
List is an abstract class, so one cannot define elements by calling the empty List constructor (e.g. by new List). The class has a type parameter a. It is co-variant in this parameter, which means that List[S] <: List[T] for all types S and T such that S <: T. The class is situated in the package scala. This is a package containing the most important standard classes of Scala. List defines a number of methods, which are explained in the following. 
}

List は抽象クラスであり、空の List コンストラクタを呼び出して (たとえば new List )、要素を定義することはできません。クラスには型パラメータ A があります。このパラメータについて共変、つまり S <: T であるような型 S と T について、List[S] <: List[T] です。クラスはパッケージ scala にあります。このパッケージは Scala の最も重要で標準的なクラスを含んでいます。List は多くのメソッドを定義しており、以下でそれを説明します。

#co(){
Decomposing lists. First, there are the three basic methods isEmpty, head, tail. Their implementation in terms of pattern matching is straightforward: 
}

&b(){リストの分解　} 最初に、３つの基本的なメソッド isEmpty, head, tail があります。パターンマッチングによるそれらの実装は簡単です。

 def isEmpty: Boolean = this match { 
   case Nil => true 
   case x :: xs => false 
 } 
 def head: A = this match { 
   case Nil => error("Nil.head") 
   case x :: xs => x 
 } 
 def tail: List[A] = this match {
   case Nil => error("Nil.tail") 
   case x :: xs => xs 
 }

#co(){
The next function computes the length of a list. 
}

次の関数はリストの長さを計算します。

 def length: Int = this match { 
   case Nil => 0 
   case x :: xs => 1 + xs.length 
 }

#co(){
Exercise 9.2.1 Design a tail-recursive version of length. 

The next two functions are the complements of head and tail. 
}

&b(){演習 9.2.1　} length の末尾再帰版を設計しなさい。

次の２つの関数は head と tail を補完するものです。

 def last: A 
 def init: List[A] 

#co(){
xs.last returns the last element of list xs, whereas xs.init returns all elements of xs except the last. Both functions have to traverse the entire list, and are thus less efficient than their head and tail analogues. Here is the implementation of last. 
}

xs.last はリスト xs の最後の要素を返し、一方で xs.init は最後以外の xs の全要素を返します。両関数ともリスト全体をたどる必要があるので、類似の head や tail より効率的ではありません。次は last の実装です。

 def last: A = this match { 
   case Nil => error("Nil.last") 
   case x :: Nil => x 
   case x :: xs => xs.last 
 } 

#co(){
The implementation of init is analogous. 

The next three functions return a prefix of the list, or a suffix, or both. }

init の実装も似ています。

次の３つの関数は、リストの先頭部、末尾部、あるいはその両方を返します。

 def take(n: Int): List[A] = 
   if (n == 0 || isEmpty) Nil else head :: tail.take(n-1) 
 def drop(n: Int): List[A] = 
   if (n == 0 || isEmpty) this else tail.drop(n-1) 
 def split(n: Int): (List[A], List[A]) = (take(n), drop(n)) 

#co(){
(xs take n) returns the first n elements of list xs, or the whole list, if its length is smaller than n. (xs drop n) returns all elements of xs except the n first ones. Finally, (xs split n) returns a pair consisting of the lists resulting from xs take n and xs drop n. 
}

(xs take n) は、リスト xs の最初の n 要素、あるいは長さが n 未満の場合はリスト全体を返します。(xs drop n) は、最初の n 要素を除いた xs の全要素を返します。最後に (xs split n) は、xs take n と xs drop n からなるリストのペアを返します。

#co(){
The next function returns an element at a given index in a list. It is thus analogous to array subscripting. Indices start at 0.
}

次の関数はリストの、与えられたインデックス要素を返します。つまり配列の添字と似ています。インデックスは 0 から始まります。

 def apply(n: Int): A = drop(n).head 

#co(){
The apply method has a special meaning in Scala. An object with an apply method can be applied to arguments as if it was a function. For instance, to pick the 3'rd element of a list xs, one can write either xs.apply(3) or xs(3) - the latter expression expands into the first. 
}

apply メソッドは Scala では特別な意味を持ちます。apply メソッドを持つオブジェクトはあたかも関数のように引数へ適用されます。たとえば、リスト xs の第 3 要素を選び出すには xs.apply(3) とも xs(3) とも書けます --- 後の式は前の式に展開されます。

#co(){
With take and drop, we can extract sublists consisting of consecutive elements of the original list. To extract the sublist x sm , . . . , x sn−1 of a list xs, use: 
}

take と drop を使って、元のリストの連続した要素からなるサブリストを取り出せます。リスト xs のサブリスト xsm,...,xsn-1 を取り出すには、

 xs.drop(m).take(n - m) 

#co(){
Zipping lists. The next function combines two lists into a list of pairs. Given two lists 
}

&b(){リストの ZIP　} 次の関数は２つのリストを組み合わせて、ペアからなる一つのリストを作ります。２つのリスト

 xs = List(x1, ..., xn ) , and 
 ys = List(y1, ..., yn ) , 

#co(){
xs zip ys constructs the list List((x1 , y1 ), ..., (xn , yn )). If the two lists have different lengths, the longer one of the two is truncated. Here is the definition of zip - note that it is a polymorphic method. 
}

に対して、xs zip ys はリスト List((x1,y1),...(xn,yn)) を作ります。もし２つのリストの長さが違う場合は、長い方が切り捨てられます。次は zip の定義です。多相的メソッドであることに注意してください。

 def zip[B](that: List[B]): List[(A,B)] = 
   if (this.isEmpty || that.isEmpty) Nil 
   else (this.head, that.head) :: (this.tail zip that.tail) 

#co(){
Consing lists.. Like any infix operator, :: is also implemented as a method of an object. In this case, the object is the list that is extended. This is possible, because operators ending with a ':' character are treated specially in Scala. All such operators are treated as methods of their right operand. E.g., 

 x :: y = y.::(x) whereas x + y = x.+(y) 
}

&b(){リストの CONS　} すべての中置演算子と同じように、:: もオブジェクトのメソッドとして実装されています。この場合、そのオブジェクトは拡張されるリストです。Scala では、文字 ':' で終わる演算子は特別に扱われるため、それが可能です。そのような演算子は、右オペランドのメソッドとして扱われます。たとえば

 x :: y = y.::(x) 一方 x + y = x.+(y) 

#co(){{
Note, however, that operands of a binary operation are in each case evaluated from left to right. So, if D and E are expressions with possible side-effects, D :: E is translated to {val x = D; E.::(x)} in order to maintain the left-to-right order of operand evaluation. 
}}

しかし、どちらの場合も二項演算のオペランドは左から右に評価されることに注意して下さい。もし D と E が副作用の可能性のある式なら、D :: E は オペランド評価において、左から右への順序を維持するために、{val x = D; E.::(x)} と変換されます。

#co(){
Another difference between operators ending in a ':' and other operators concerns their associativity. Operators ending in ':' are right-associative, whereas other operators are left-associative. E.g., 

 x :: y :: z = x :: (y :: z) whereas x + y + z = (x + y) + z 
}

':' で終わる演算子と他の演算子とのもう一つの違いは、結合性に関するものです。':' で終わる演算子は右結合で、他の演算子は左結合です。たとえば、

 x :: y :: z = x :: (y :: z) 一方 x + y + z = (x + y) + z 

#co(){
The definition of :: as a method in class List is as follows:
}

クラス List のメソッドとしての :: の定義は、次のようです。

 def ::[B >: A](x: B): List[B] = new scala.::(x, this) 

#co(){
Note that :: is defined for all elements x of type B and lists of type List[A] such that the type B of x is a supertype of the list's element type A. The result is in this case a list of B's. This is expressed by the type parameter B with lower bound A in the signature of ::. 
}

:: は、x の型 B がリストの要素型 A のスーパータイプであるような、型 B のすべての要素 x と、List[A] 型のリストに対して定義されていることに注意して下さい。この場合、結果は要素型 B のリストになります。このことは :: のシグネチャにおいて、下限境界 A を持つ型パラメータ B、として表現されています。

#co(){
Concatenating lists. An operation similar to :: is list concatenation, written ':::'. The result of (xs ::: ys) is a list consisting of all elements of xs, followed by all elements of ys. Because it ends in a colon, ::: is right-associative and is considered as a method of its right-hand operand. Therefore, 
}

&b(){リストの連結　} :: と似た操作はリストの連結で、':::' と書きます。(xs ::: ys) の結果は xs の全要素に ys の全要素が続いたリストです。コロンで終わるため、::: は右結合であり右オペランドのメソッドとみなされます。したがって、

 xs ::: ys ::: zs = xs ::: (ys ::: zs) 
               = zs.:::(ys).:::(xs) 

#co(){
Here is the implementation of the ::: method: 
}

以下は ::: メソッドの実装です。

 def :::[B >: A](prefix: List[B]): List[B] = prefix match { 
   case Nil => this 
   case p :: ps => this.:::(ps).::(p) 
 } 

#co(){
Reversing lists. Another useful operation is list reversal. There is a method reverse in List to that effect. Let's try to give its implementation: 
}

&b(){リストの逆転　} ほかにも有用な操作として、リストの逆転があります。List にはそのためのメソッド reverse があります。実装を与えてみましょう。

 def reverse[A](xs: List[A]): List[A] = xs match { 
   case Nil => Nil 
   case x :: xs => reverse(xs) ::: List(x) 
 } 

#co(){
This implementation has the advantage of being simple, but it is not very efficient. Indeed, one concatenation is executed for every element in the list. List concatenation takes time proportional to the length of its first operand. Therefore, the complexity of reverse(xs) is 
}

この実装には単純であるという利点がありますが、あまり効率的とは言えません。実際のところ、リストの各要素に対して１回の連結が実行されます。List の連結は、最初のオペランドの長さに比例する時間がかかります。したがって reverse(xs) の計算量は

 n + (n − 1) + ... + 1 = n(n + 1)/2 

#co(){
where n is the length of xs. Can reverse be implemented more efficiently? We will see later that there exists another implementation which has only linear complexity. 
}

ただし n は xs の長さです。reverse をもっと効率的に実装できますか？線形な計算量しか持たない異なる実装をあとで見ます。

#center(){[[前ページ>Example9.1]]　[[ 9 章>Chapter 9 Lists]]　[[目次>ScalaByExample和訳]]　[[次ページ>Example9.3]]}

----
- s/split/splitAt/g  -- murase_syuka  (2008-10-08 01:15:57)
#comment

#co(){
9.2 Definition of class List I: First Order Methods 

Lists are not built in in Scala; they are defined by an abstract class List, which comes with two subclasses for :: and Nil. In the following we present a tour through class List. 
}


#setmenu2(ex-r-menu)
** 9.2 リストクラスの定義Ⅰ:一階メソッド

リストは Scala では組み込み型ではありません。抽象クラス List として定義され、２つのサブクラス :: と Nil があります。以降では、クラス List のツアーに出かけます。

 package scala 
 abstract class List[+A] {

#co(){
List is an abstract class, so one cannot define elements by calling the empty List constructor (e.g. by new List). The class has a type parameter a. It is co-variant in this parameter, which means that List[S] <: List[T] for all types S and T such that S <: T. The class is situated in the package scala. This is a package containing the most important standard classes of Scala. List defines a number of methods, which are explained in the following. 
}

List は抽象クラスであり、空の List コンストラクタを呼び出して (たとえば new List )、要素を定義することはできません。クラスには型パラメータ a があります。このパラメータについて共変、つまり S <: T であるような型 S と T について、List[S] <: List[T] です。クラスはパッケージ scala にあります。このパッケージは Scala の最も重要で標準的なクラスを含んでいます。List は多くのメソッドを定義しており、以下でそれを説明します。

#co(){
Decomposing lists. First, there are the three basic methods isEmpty, head, tail. Their implementation in terms of pattern matching is straightforward: 
}

&b(){リストの分解　} 最初に、３つの基本的なメソッド isEmpty, head, tail があります。パターンマッチングによるそれらの実装は簡単です。

 def isEmpty: Boolean = this match { 
   case Nil => true 
   case x :: xs => false 
 } 
 def head: A = this match { 
   case Nil => error("Nil.head") 
   case x :: xs => x 
 } 
 def tail: List[A] = this match {
   case Nil => error("Nil.tail") 
   case x :: xs => xs 
 }

#co(){
The next function computes the length of a list. 
}

次の関数はリストの長さを計算します。

 def length: Int = this match { 
   case Nil => 0 
   case x :: xs => 1 + xs.length 
 }

#co(){
Exercise 9.2.1 Design a tail-recursive version of length. 

The next two functions are the complements of head and tail. 
}

&b(){演習 9.2.1　} length の末尾再帰版を設計しなさい。

次の２つの関数は head と tail を補完するものです。

 def last: A 
 def init: List[A] 

#co(){
xs.last returns the last element of list xs, whereas xs.init returns all elements of xs except the last. Both functions have to traverse the entire list, and are thus less efficient than their head and tail analogues. Here is the implementation of last. 
}

xs.last はリスト xs の最後の要素を返し、一方で xs.init は最後以外の xs の全要素を返します。両関数ともリスト全体をたどる必要があるので、類似の head や tail より効率的ではありません。次は last の実装です。

 def last: A = this match { 
   case Nil => error("Nil.last") 
   case x :: Nil => x 
   case x :: xs => xs.last 
 } 

#co(){
The implementation of init is analogous. 

The next three functions return a prefix of the list, or a suffix, or both. }

init の実装も似ています。

次の３つの関数は、リストの先頭部、末尾部、あるいはその両方を返します。

 def take(n: Int): List[A] = 
   if (n == 0 || isEmpty) Nil else head :: tail.take(n-1) 
 def drop(n: Int): List[A] = 
   if (n == 0 || isEmpty) this else tail.drop(n-1) 
 def split(n: Int): (List[A], List[A]) = (take(n), drop(n)) 

#co(){
(xs take n) returns the first n elements of list xs, or the whole list, if its length is smaller than n. (xs drop n) returns all elements of xs except the n first ones. Finally, (xs split n) returns a pair consisting of the lists resulting from xs take n and xs drop n. 
}

(xs take n) は、リスト xs の最初の n 要素、あるいは長さが n 未満の場合はリスト全体を返します。(xs drop n) は、最初の n 要素を除いた xs の全要素を返します。最後に (xs split n) は、xs take n と xs drop n からなるリストのペアを返します。

#co(){
The next function returns an element at a given index in a list. It is thus analogous to array subscripting. Indices start at 0.
}

次の関数はリストの、与えられたインデックス要素を返します。つまり配列の添字と似ています。インデックスは 0 から始まります。

 def apply(n: Int): A = drop(n).head 

#co(){
The apply method has a special meaning in Scala. An object with an apply method can be applied to arguments as if it was a function. For instance, to pick the 3'rd element of a list xs, one can write either xs.apply(3) or xs(3) - the latter expression expands into the first. 
}

apply メソッドは Scala では特別な意味を持ちます。apply メソッドを持つオブジェクトはあたかも関数のように引数へ適用されます。たとえば、リスト xs の第 3 要素を選び出すには xs.apply(3) とも xs(3) とも書けます --- 後の式は前の式に展開されます。

#co(){
With take and drop, we can extract sublists consisting of consecutive elements of the original list. To extract the sublist x sm , . . . , x sn−1 of a list xs, use: 
}

take と drop を使って、元のリストの連続した要素からなるサブリストを取り出せます。リスト xs のサブリスト xsm,...,xsn-1 を取り出すには、

 xs.drop(m).take(n - m) 

#co(){
Zipping lists. The next function combines two lists into a list of pairs. Given two lists 
}

&b(){リストの ZIP　} 次の関数は２つのリストを組み合わせて、ペアからなる一つのリストを作ります。２つのリスト

 xs = List(x1, ..., xn ) , and 
 ys = List(y1, ..., yn ) , 

#co(){
xs zip ys constructs the list List((x1 , y1 ), ..., (xn , yn )). If the two lists have different lengths, the longer one of the two is truncated. Here is the definition of zip - note that it is a polymorphic method. 
}

に対して、xs zip ys はリスト List((x1,y1),...(xn,yn)) を作ります。もし２つのリストの長さが違う場合は、長い方が切り捨てられます。次は zip の定義です。多相的メソッドであることに注意してください。

 def zip[B](that: List[B]): List[(A,B)] = 
   if (this.isEmpty || that.isEmpty) Nil 
   else (this.head, that.head) :: (this.tail zip that.tail) 

#co(){
Consing lists.. Like any infix operator, :: is also implemented as a method of an object. In this case, the object is the list that is extended. This is possible, because operators ending with a ':' character are treated specially in Scala. All such operators are treated as methods of their right operand. E.g., 

 x :: y = y.::(x) whereas x + y = x.+(y) 
}

&b(){リストの CONS　} すべての中置演算子と同じように、:: もオブジェクトのメソッドとして実装されています。この場合、そのオブジェクトは拡張されるリストです。Scala では、文字 ':' で終わる演算子は特別に扱われるため、それが可能です。そのような演算子は、右オペランドのメソッドとして扱われます。たとえば

 x :: y = y.::(x) 一方 x + y = x.+(y) 

#co(){{
Note, however, that operands of a binary operation are in each case evaluated from left to right. So, if D and E are expressions with possible side-effects, D :: E is translated to {val x = D; E.::(x)} in order to maintain the left-to-right order of operand evaluation. 
}}

しかし、どちらの場合も二項演算のオペランドは左から右に評価されることに注意して下さい。もし D と E が副作用の可能性のある式なら、D :: E は オペランド評価において、左から右への順序を維持するために、{val x = D; E.::(x)} と変換されます。

#co(){
Another difference between operators ending in a ':' and other operators concerns their associativity. Operators ending in ':' are right-associative, whereas other operators are left-associative. E.g., 

 x :: y :: z = x :: (y :: z) whereas x + y + z = (x + y) + z 
}

':' で終わる演算子と他の演算子とのもう一つの違いは、結合性に関するものです。':' で終わる演算子は右結合で、他の演算子は左結合です。たとえば、

 x :: y :: z = x :: (y :: z) 一方 x + y + z = (x + y) + z 

#co(){
The definition of :: as a method in class List is as follows:
}

クラス List のメソッドとしての :: の定義は、次のようです。

 def ::[B >: A](x: B): List[B] = new scala.::(x, this) 

#co(){
Note that :: is defined for all elements x of type B and lists of type List[A] such that the type B of x is a supertype of the list's element type A. The result is in this case a list of B's. This is expressed by the type parameter B with lower bound A in the signature of ::. 
}

:: は、x の型 B がリストの要素型 A のスーパータイプであるような、型 B のすべての要素 x と、List[A] 型のリストに対して定義されていることに注意して下さい。この場合、結果は要素型 B のリストになります。このことは :: のシグネチャにおいて、下限境界 A を持つ型パラメータ B、として表現されています。

#co(){
Concatenating lists. An operation similar to :: is list concatenation, written ':::'. The result of (xs ::: ys) is a list consisting of all elements of xs, followed by all elements of ys. Because it ends in a colon, ::: is right-associative and is considered as a method of its right-hand operand. Therefore, 
}

&b(){リストの連結　} :: と似た操作はリストの連結で、':::' と書きます。(xs ::: ys) の結果は xs の全要素に ys の全要素が続いたリストです。コロンで終わるため、::: は右結合であり右オペランドのメソッドとみなされます。したがって、

 xs ::: ys ::: zs = xs ::: (ys ::: zs) 
               = zs.:::(ys).:::(xs) 

#co(){
Here is the implementation of the ::: method: 
}

以下は ::: メソッドの実装です。

 def :::[B >: A](prefix: List[B]): List[B] = prefix match { 
   case Nil => this 
   case p :: ps => this.:::(ps).::(p) 
 } 

#co(){
Reversing lists. Another useful operation is list reversal. There is a method reverse in List to that effect. Let's try to give its implementation: 
}

&b(){リストの逆転　} ほかにも有用な操作として、リストの逆転があります。List にはそのためのメソッド reverse があります。実装を与えてみましょう。

 def reverse[A](xs: List[A]): List[A] = xs match { 
   case Nil => Nil 
   case x :: xs => reverse(xs) ::: List(x) 
 } 

#co(){
This implementation has the advantage of being simple, but it is not very efficient. Indeed, one concatenation is executed for every element in the list. List concatenation takes time proportional to the length of its first operand. Therefore, the complexity of reverse(xs) is 
}

この実装には単純であるという利点がありますが、あまり効率的とは言えません。実際のところ、リストの各要素に対して１回の連結が実行されます。List の連結は、最初のオペランドの長さに比例する時間がかかります。したがって reverse(xs) の計算量は

 n + (n − 1) + ... + 1 = n(n + 1)/2 

#co(){
where n is the length of xs. Can reverse be implemented more efficiently? We will see later that there exists another implementation which has only linear complexity. 
}

ただし n は xs の長さです。reverse をもっと効率的に実装できますか？線形な計算量しか持たない異なる実装をあとで見ます。

#center(){[[前ページ>Example9.1]]　[[ 9 章>Chapter 9 Lists]]　[[目次>ScalaByExample和訳]]　[[次ページ>Example9.3]]}

----
- s/split/splitAt/g  -- murase_syuka  (2008-10-08 01:15:57)
#comment