Example9.4

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

Example9.4 - (2010/10/23 (土) 12:00:42) の１つ前との変更点

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

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

#co(){
9.4 Definition of class List II: Higher-Order Methods 

The examples encountered so far show that functions over lists often have similar structures. We can identify several patterns of computation over lists, like: 
- transforming every element of a list in some way. 
- extracting from a list all elements satisfying a criterion. 
- combine the elements of a list using some operator. 
}

** 9.4 リストクラスの定義Ⅱ:高階メソッド

ここまでに見た例が示すことは、リストに対する関数はしばしば似た構造をしているということです。リストに対する計算パターンをいくつか見ることができます。たとえば、

- ある方法で全ての要素を変換する
- 条件を満たす全ての要素を取り出す。
- ある演算子を用いて全ての要素を結合する

#co(){
Functional programming languages enable programmers to write general functions which implement patterns like this by means of higher order functions. We now discuss a set of commonly used higher-order functions, which are implemented as methods in class List. 
}

関数型プログラミング言語では高階関数を使うことで、パターンを実装する汎用的な関数を書けます。よく使われる高階関数について議論しますが、それらはクラス List のメソッドとして実装されています。

#co(){
Mapping over lists. A common operation is to transform each element of a list and then return the lists of results. For instance, to scale each element of a list by a given factor. 
}

&b(){リストのマッピング　} リストの各要素を変換して結果のリストを得ることは、よくある操作です。たとえば、リストの各要素を与えられた数だけ倍するのは、

 def scaleList(xs: List[Double], factor: Double): List[Double] = xs match { 
   case Nil => xs 
   case x :: xs1 => x * factor :: scaleList(xs1, factor) 
 } 

#co(){
This pattern can be generalized to the map method of class List: 
}

このパターンは、クラス List の map メソッドとして一般化できます。

 abstract class List[A] { ... 
   def map[B](f: A => B): List[B] = this match { 
   case Nil => this 
   case x :: xs => f(x) :: xs.map(f) 
 }

#co(){
Using map, scaleList can be more concisely written as follows. 
}

map を用いると、scaleList は次のように簡潔になります。

 def scaleList(xs: List[Double], factor: Double) = 
   xs map (x => x * factor) 

#co(){
As another example, consider the problem of returning a given column of a matrix which is represented as a list of rows, where each row is again a list. This is done by the following function column. 
}

ほかの例として、行のリストとして表現されている行列の、指定された列を返す問題、ただし各行もまたリストである、を考えましょう。これは次の関数 column で与えられます。

 def column[A](xs: List[List[A]], index: Int): List[A] = 
   xs map (row => row(index)) 

#co(){
Closely related to map is the foreach method, which applies a given function to all elements of a list, but does not construct a list of results. The function is thus applied only for its side effect. foreach is defined as follows.
}

map と近い関係にあるのは foreach メソッドで、リストの全要素に関数を適用しますが、結果のリストを組み立てません。この関数はですから、副作用のためだけのものです。foreach は次のように定義されています。

 def foreach(f: A => Unit) { 
   this match { 
     case Nil => () 
     case x :: xs => f(x); xs.foreach(f) 
   } 
 } 

#co(){
This function can be used for printing all elements of a list, for instance:} 

たとえば、この関数はリストの要素すべてを表示するのに使えます。

 xs foreach (x => println(x)) 

#co(){
Exercise 9.4.1 Consider a function which squares all elements of a list and returns a list with the results. Complete the following two equivalent definitions of squareList. 
}

&b(){演習 9.4.1　} リストの要素すべてを２乗して、結果のリストを返す関数について考察しなさい。次の２つの等価な定義を完成させなさい。

 def squareList(xs: List[Int]): List[Int] = xs match { 
   case List() => ?? 
   case y :: ys => ?? 
 } 
 def squareList(xs: List[Int]): List[Int] = 
   xs map ?? 

#co(){
Filtering Lists. Another common operation selects from a list all elements fulfilling a given criterion. For instance, to return a list of all positive elements in some given lists of integers: 
}

&b(){リストのフィルタリング　} 他のよくある操作は、リストの、与えられた条件を満たすすべての要素を取り出す操作です。たとえば整数リスト中の正の要素からなるリストを返すには、

 def posElems(xs: List[Int]): List[Int] = xs match { 
   case Nil => xs 
   case x :: xs1 => if (x > 0) x :: posElems(xs1) else posElems(xs1) 
 }
 
#co(){
This pattern is generalized to the filter method of class List: 
}

このパターンは、クラス List の filter メソッドへ一般化できます。

 def filter(p: A => Boolean): List[A] = this match { 
   case Nil => this 
   case x :: xs => if (p(x)) x :: xs.filter(p) else xs.filter(p) 
 } 

#co(){
Using filter, posElems can be more concisely written as follows. 
}

filter を使うと、posElems は次のように簡潔に書けます。

 def posElems(xs: List[Int]): List[Int] = 
   xs filter (x => x > 0) 

#co(){
An operation related to filtering is testing whether all elements of a list satisfy a certain condition. Dually, one might also be interested in the question whether there exists an element in a list that satisfies a certain condition. These operations are embodied in the higher-order functions forall and exists of class List. 
}

フィルタに関係した操作として、リストのすべての要素が、ある条件を満たすかをテストするものがあります。対を成すものとして、リストに、ある条件を満たす要素があるか否か、という問題にも興味があるかもしれません。これらの操作はクラス List の forall と exists という高階関数として具体化されます。

 def forall(p: A => Boolean): Boolean = 
   isEmpty || (p(head) && (tail forall p)) 
 def exists(p: A => Boolean): Boolean = 
   !isEmpty && (p(head) || (tail exists p)) 

#co(){
To illustrate the use of forall, consider the question of whether a number if prime. Remember that a number n is prime of it can be divided without remainder only by one and itself. The most direct translation of this definition would test that n divided by all numbers from 2 up to and excluding itself gives a non-zero remainder. This list of numbers can be generated using a function List.range which is defined in object List as follows. 
}

forall の使い方を示すために、ある数が素数であるか否かという問題を考えましょう。数 n が素数であるとは、１と自分自身でのみ割り切れるということを思い出して下さい。最も直接的にこの定義を翻訳すると、２以上 n 未満のすべての数で割った余りが非ゼロであることをテストすることです。数のリストは、次のようにオブジェクト List で定義されている List.range 関数で生成できます。

 package scala 
 object List { ... 
   def range(from: Int, end: Int): List[Int] = 
     if (from >= end) Nil else from :: range(from + 1, end) 

#co(){
For example, List.range(2, n) generates the list of all integers from 2 up to and excluding n. The function isPrime can now simply be defined as follows. 
}

たとえば List.range(2,n) は２以上 n 未満の全整数からなるリストを生成します。関数 isPrime は次のように簡単に定義できます。

 def isPrime(n: Int) = 
   List.range(2, n) forall (x => n % x != 0) 

#co(){
We see that the mathematical definition of prime-ness has been translated directly into Scala code. 

Exercise: Define forall and exists in terms of filter. 
}

素数性の数学的定義が直接 Scala コードに翻訳されています。

演習 : filter を使って forall と exists を定義しなさい。

#co(){
Folding and Reducing Lists. Another common operation is to combine the elements of a list with some operator. For instance: 
}

&b(){リストの畳み込み　} 他のよくある操作は、リストの要素をある演算子で結合することです。たとえば

 sum(List(x1, ..., xn )) = 0 + x1 + ... + xn 
 product(List(x1, ..., xn )) = 1 * x1 * ... * xn 

#co(){
Of course, we can implement both functions with a recursive scheme: 
}

もちろん、どちらの関数も再帰的スキームで実装できます。

 def sum(xs: List[Int]): Int = xs match { 
   case Nil => 0 
   case y :: ys => y + sum(ys) 
 } 
 def product(xs: List[Int]): Int = xs match { 
   case Nil => 1 
   case y :: ys => y * product(ys) 
 }

#co(){
But we can also use the generalization of this program scheme embodied in the reduceLeft method of class List. This method inserts a given binary operator between adjacent elements of a given list. E.g. 
}

しかし、このプログラムスキームの一般化、具体的にはクラス List の reduceLeft メソッド、を利用しても実装できます。このメソッドは与えられた二項演算子を、与えられたリストの隣りあう要素の間に挿入します。たとえば

 List(x1, ..., xn ).reduceLeft(op) = (...(x1 op x2 ) op ... ) op xn 

#co(){
Using reduceLeft, we can make the common pattern in sum and product apparent: 
}

reduceLeft を使って、sum と product の共通パターンを明らかにできます。

 def sum(xs: List[Int]) = (0 :: xs) reduceLeft {(x, y) => x + y} 
 def product(xs: List[Int]) = (1 :: xs) reduceLeft {(x, y) => x * y} 

#co(){
Here is the implementation of reduceLeft. 
}

次が reduceLeft の実装です。

 def reduceLeft(op: (A, A) => A): A = this match { 
   case Nil => error("Nil.reduceLeft") 
   case x :: xs => (xs foldLeft x)(op) 
 } 
 def foldLeft[B](z: B)(op: (B, A) => B): B = this match { 
   case Nil => z 
   case x :: xs => (xs foldLeft op(z, x))(op) 
 }

#co(){
We see that the reduceLeft method is defined in terms of another generally useful method, foldLeft. The latter takes as additional parameter an accumulator z, which is returned when foldLeft is applied on an empty list. That is,} 

reduceLeft メソッドは、一般的で役に立つ別のメソッド foldLeft を使って定義されていることがわかります。後者は、追加の引数として&bold(){積算器} z をとり、foldLeft が空リストに適用された時は、その値が返ります。つまり、

 (List(x1, ..., xn ) foldLeft z)(op) = (...(z op x1 ) op ... ) op xn 

#co(){
The sum and product methods can be defined alternatively using foldLeft: 
}
メソッド sum と product は foldLeft を使って、次のようにも定義できます。

 def sum(xs: List[Int]) = (xs foldLeft 0) {(x, y) => x + y} 
 def product(xs: List[Int]) = (xs foldLeft 1) {(x, y) => x * y} 

#co(){
FoldRight and ReduceRight. Applications of foldLeft and reduceLeft expand to left-leaning trees. . They have duals foldRight and reduceRight, which produce right-leaning trees. 
}

&b(){右畳み込み　} foldLeft と reduceLeft を適用すると、左に傾いた木(left-leaning tree)ができます。双対的な foldRight と reduceRight では、右に傾いた木ができます。

 List(x1, ..., xn ).reduceRight(op) = x1 op ( ... (xn−1 op xn )...) 
 (List(x1, ..., xn ) foldRight acc)(op) = x1 op ( ... (xn op acc)...) 

#co(){
These are defined as follows. 
}

それらは次のように定義されます。

 def reduceRight(op: (A, A) => A): A = this match { 
   case Nil => error("Nil.reduceRight") 
   case x :: Nil => x 
   case x :: xs => op(x, xs.reduceRight(op))
 } 
 def foldRight[B](z: B)(op: (A, B) => B): B = this match { 
   case Nil => z 
   case x :: xs => op(x, (xs foldRight z)(op)) 
 }

#co(){
Class List defines also two symbolic abbreviations for foldLeft and foldRight: 
}

クラス List では、foldLeft と foldRight の省略形記号も定義しています。

 def /:[B](z: B)(f: (B, A) => B): B = foldLeft(z)(f) 
 def :\[B](z: B)(f: (A, B) => B): B = foldRight(z)(f) 

#co(){
The method names picture the left/right leaning trees of the fold operations by forward or backward slashes. The : points in each case to the list argument whereas the end of the slash points to the accumulator (or: zero) argument z. That is, 
}

このメソッド名(記号)は、順スラッシュあるいは逆スラッシュによって、畳み込み操作の木を左/右に傾いた木の絵で表しています。それぞれの : はリスト引数を指し示し、スラッシュは積算器 (あるいはゼロ) 引数 z を指し示します。つまり

 (z /: List(x1, ..., xn ))(op) = (...(z op x1 ) op ... ) op xn 
 (List(x1, ..., xn ) :\ z)(op) = x1 op ( ... (xn op acc)...) 

#co(){
For associative and commutative operators, /: and :\ are equivalent (even though there may be a difference in efficiency). 
}

結合則および交換則をみたす演算子(op)に対しては、/: と :\ は等価です (ただし、効率には違いがありますが)。

#co(){
Exercise 9.4.2 Consider the problem of writing a function flatten, which takes a list of element lists as arguments. The result of flatten should be the concatenation of all element lists into a single list. Here is an implementation of this method in terms of :\. 
}

&b(){演習 9.4.2　} リストを要素とするリストを引数とする関数 flatten を書く問題を考察しなさい。flatten の結果は、すべての要素リストを一つのリストへと連結したものです。次は :\ を用いた、このメソッドの実装です。

 def flatten[A](xs: List[List[A]]): List[A] = 
   (xs :\ (Nil: List[A])) {(x, xs) => x ::: xs} 

#co(){
Consider replacing the body of flatten by 
}

flatten の本体を次のように置き換えた場合を考察しなさい。

 ((Nil: List[A]) /: xs) ((xs, x) => xs ::: x) 

#co(){
What would be the difference in asymptotic complexity between the two versions of flatten? In fact flatten is predefined together with a set of other userful function in an object called List in the standatd Scala library. It can be accessed from user program by calling List.flatten. Note that flatten is not a method of class List - it would not make sense there, since it applies only to lists of lists, not to all lists in general. 
}

flatten の２つのバージョンでの漸近的計算量の違いはどうなりますか？ 実際には、flatten は他の有用な関数と共に Scala ライブラリの List オブジェクトで定義されています。ユーザープログラムからは List.flatten でアクセスできます。flatten はクラス List のメソッドでないことに注意してください --- それでは意味がありません。なぜならそれは一般のリストにではなく、リストのリストにしか適用できないからです。

#co(){
List Reversal Again. We have seen in Section 9.2 an implementation of method reverse whose run-time was quadratic in the length of the list to be reversed. We now develop a new implementation of reverse, which has linear cost. The idea is to use a foldLeft operation based on the following program scheme. 
}

&b(){リストの逆転 再考　} 9.2 節で、メソッド reverse の実装と、その実行時間がリストの長さの二次式になることを見ました。ここで、線形なコストをもつ reverse の新しい実装を考えましょう。アイデアは、次のようなプログラムスキームに基づく foldLeft 操作を用いることです。

 class List[+A] { ...
   def reverse: List[A] = (z? /: this)(op?)

#co(){
It only remains to fill in the z? and op? parts. Let's try to deduce them from examples. 
}

あとは z? と op? 部分を埋めるだけです。例から推測してみましょう。

    Nil 
 = Nil.reverse // by specification 
 = (z /: Nil)(op) // by the template for reverse 
 = (Nil foldLeft z)(op) // by the definition of /: 
 = z // by definition of foldLeft 

    Nil 
 = Nil.reverse // 仕様より 
 = (z /: Nil)(op) // reverse のテンプレートより
 = (Nil foldLeft z)(op) // /: の定義より 
 = z // foldLeft の定義より 

#co(){
Hence, z? must be Nil. To deduce the second operand, let's study reversal of a list of length one. 
}

したがって z? は Nil でなくてはなりません。二つ目のオペランドを推測するために、長さが１のリストを考えます。

   List(x) 
 = List(x).reverse // by specification 
 = (Nil /: List(x))(op) // by the template for reverse, with z = Nil 
 = (List(x) foldLeft Nil)(op) // by the definition of /: 
 = op(Nil, x) // by definition of foldLeft 

   List(x) 
 = List(x).reverse // 仕様より 
 = (Nil /: List(x))(op) // reverse のテンプレートと z = Nil より
 = (List(x) foldLeft Nil)(op) // /: の定義より
 = op(Nil, x) // foldLeft の定義より 

#co(){
Hence, op(Nil, x) equals List(x), which is the same as x :: Nil. This suggests to take as op the :: operator with its operands exchanged. Hence, we arrive at the following implementation for reverse, which has linear complexity.} 

したがって op(Nil, x) は List(x) に等しく、それは x :: Nil と等しい。これから op は :: で、オペランドを交換したものだと分かります。以上から、次のような、線形な計算量をもつ reverse の実装を得ます。

 def reverse: List[A] = 
   ((Nil: List[A]) /: this) {(xs, x) => x :: xs} 

#co(){
(Remark: The type annotation of Nil is necessary to make the type inferencer work.) 
}

(注釈 : Nil の型アノテーションは、型推論させるために必要です)

#co(){
Exercise 9.4.3 Fill in the missing expressions to complete the following definitions of some basic list-manipulation operations as fold operations. 
}

&b(){演習 9.4.3　} 書かれていない式を埋めて、次の基本的なリスト操作定義を畳み込み操作として完成しなさい。

 def mapFun[A, B](xs: List[A], f: A => B): List[B] = 
   (xs :\ List[B]()){ ?? } 
 def lengthFun[A](xs: List[A]): int = 
   (0 /: xs){ ?? } 

#co(){
Nested Mappings. We can employ higher-order list processing functions to express many computations that are normally expressed as nested loops in imperative languages. 
}

&b(){ネストしたマップ　} 命令型言語において通常、ループのネストで書かれる多くの計算を、高階リスト操作関数を使って書くことができます。

#co(){
As an example, consider the following problem: Given a positive integer n, find all pairs of positive integers i and j , where 1 ≤ j < i < n such that i + j is prime. For instance, if n = 7, the pairs are 
}

例として次のような問題を考えましょう。与えられた正整数 n に対し、正整数 i と j のすべての組 (ただし 1 <= j < i < n で、i+j が素数)を求めなさい。たとえば n = 7 であれば対は、

 i      2 3 4 4 5 6 6 
 j      1 2 1 3 2 1 5 
 i + j 3 5 5 7 7 7 11 

#co(){
A natural way to solve this problem consists of two steps. In a first step, one generates the sequence of all pairs (i , j ) of integers such that 1 ≤ j < i < n. In a second step one then filters from this sequence all pairs (i , j ) such that i + j is prime. 
}

問題を解く自然な方法は２つのステップからなります。最初のステップでは、1<=j < i < n を満たす整数の対 (i,j) の列を作ります。第二のステップでは、すべての対 (i,j) の列から、i+j が素数であるものをフィルタします。

#co(){
Looking at the first step in more detail, a natural way to generate the sequence of pairs consists of three sub-steps. First, generate all integers between 1 and n for i.

Second, for each integer i between 1 and n, generate the list of pairs (i , 1) up to (i , i − 1). This can be achieved by a combination of range and map: 
}

最初のステップをより詳細に見ましょう。対の列を生成する自然な方法は３つのサブステップからなります。最初に、1 以上 n未満の整数を i のために作ります。

次に、1 以上 n 未満の各 i に対して、(i,1) から (i,i-1) までの対のリストを作ります。これは range と map の組み合わせによって可能です。

 List.range(1, i) map (x => (i, x)) 

#co(){
Finally, combine all sublists using foldRight with :::. Putting everything together gives the following expression: 
}

最後に、すべてのサブリストを foldright と ::: を使って連結します。すべてを組み合わせると次の式が得られます。

 List.range(1, n) 
   .map(i => List.range(1, i).map(x => (i, x))) 
   .foldRight(List[(Int, Int)]()) {(xs, ys) => xs ::: ys} 
   .filter(pair => isPrime(pair._1 + pair._2)) 

#co(){
Flattening Maps. The combination of mapping and then concatenating sublists resulting from the map is so common that we there is a special method for it in class List: 
}

&b(){マップの平坦化　} マッピングと、マップで得られたサブリストの連結という組み合わせは、非常によく使うので、クラス List には特別なメソッドがあります。

 abstract class List[+A] { ... 
   def flatMap[B](f: A => List[B]): List[B] = this match { 
     case Nil => Nil 
     case x :: xs => f(x) ::: (xs flatMap f) 
   } 
 } 

#co(){
With flatMap, the pairs-whose-sum-is-prime expression could have been written more concisely as follows. 
}

flatMap を使うと「和が素数となる対」の式は、次のようにさらに簡潔に書けます。
 List.range(1, n) 
   .flatMap(i => List.range(1, i).map(x => (i, x))) 
   .filter(pair => isPrime(pair._1 + pair._2))

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

----
#comment

#co(){
9.4 Definition of class List II: Higher-Order Methods 

The examples encountered so far show that functions over lists often have similar structures. We can identify several patterns of computation over lists, like: 
- transforming every element of a list in some way. 
- extracting from a list all elements satisfying a criterion. 
- combine the elements of a list using some operator. 
}

** 9.4 リストクラスの定義Ⅱ:高階メソッド

ここまでに見た例が示すことは、リストに対する関数はしばしば似た構造をしているということです。リストに対する計算パターンをいくつか見ることができます。たとえば、

- ある方法で全ての要素を変換する
- 条件を満たす全ての要素を取り出す。
- ある演算子を用いて全ての要素を結合する

#co(){
Functional programming languages enable programmers to write general functions which implement patterns like this by means of higher order functions. We now discuss a set of commonly used higher-order functions, which are implemented as methods in class List. 
}

関数型プログラミング言語では高階関数を使うことで、パターンを実装する汎用的な関数を書けます。よく使われる高階関数について議論しますが、それらはクラス List のメソッドとして実装されています。

#co(){
Mapping over lists. A common operation is to transform each element of a list and then return the lists of results. For instance, to scale each element of a list by a given factor. 
}

&b(){リストのマッピング　} リストの各要素を変換して結果のリストを得ることは、よくある操作です。たとえば、リストの各要素を与えられた数だけ倍するのは、

 def scaleList(xs: List[Double], factor: Double): List[Double] = xs match { 
   case Nil => xs 
   case x :: xs1 => x * factor :: scaleList(xs1, factor) 
 } 

#co(){
This pattern can be generalized to the map method of class List: 
}

このパターンは、クラス List の map メソッドとして一般化できます。

 abstract class List[A] { ... 
   def map[B](f: A => B): List[B] = this match { 
   case Nil => this 
   case x :: xs => f(x) :: xs.map(f) 
 }

#co(){
Using map, scaleList can be more concisely written as follows. 
}

map を用いると、scaleList は次のように簡潔になります。

 def scaleList(xs: List[Double], factor: Double) = 
   xs map (x => x * factor) 

#co(){
As another example, consider the problem of returning a given column of a matrix which is represented as a list of rows, where each row is again a list. This is done by the following function column. 
}

ほかの例として、行のリストとして表現されている行列の、指定された列を返す問題、ただし各行もまたリストである、を考えましょう。これは次の関数 column で与えられます。

 def column[A](xs: List[List[A]], index: Int): List[A] = 
   xs map (row => row(index)) 

#co(){
Closely related to map is the foreach method, which applies a given function to all elements of a list, but does not construct a list of results. The function is thus applied only for its side effect. foreach is defined as follows.
}

map と近い関係にあるのは foreach メソッドで、リストの全要素に関数を適用しますが、結果のリストを組み立てません。この関数はですから、副作用のためだけのものです。foreach は次のように定義されています。

 def foreach(f: A => Unit) { 
   this match { 
     case Nil => () 
     case x :: xs => f(x); xs.foreach(f) 
   } 
 } 

#co(){
This function can be used for printing all elements of a list, for instance:} 

たとえば、この関数はリストの要素すべてを表示するのに使えます。

 xs foreach (x => println(x)) 

#co(){
Exercise 9.4.1 Consider a function which squares all elements of a list and returns a list with the results. Complete the following two equivalent definitions of squareList. 
}

&b(){演習 9.4.1　} リストの要素すべてを２乗して、結果のリストを返す関数について考察しなさい。次の２つの等価な定義を完成させなさい。

 def squareList(xs: List[Int]): List[Int] = xs match { 
   case List() => ?? 
   case y :: ys => ?? 
 } 
 def squareList(xs: List[Int]): List[Int] = 
   xs map ?? 

#co(){
Filtering Lists. Another common operation selects from a list all elements fulfilling a given criterion. For instance, to return a list of all positive elements in some given lists of integers: 
}

&b(){リストのフィルタリング　} 他のよくある操作は、リストの、与えられた条件を満たすすべての要素を取り出す操作です。たとえば整数リスト中の正の要素からなるリストを返すには、

 def posElems(xs: List[Int]): List[Int] = xs match { 
   case Nil => xs 
   case x :: xs1 => if (x > 0) x :: posElems(xs1) else posElems(xs1) 
 }
 
#co(){
This pattern is generalized to the filter method of class List: 
}

このパターンは、クラス List の filter メソッドへ一般化できます。

 def filter(p: A => Boolean): List[A] = this match { 
   case Nil => this 
   case x :: xs => if (p(x)) x :: xs.filter(p) else xs.filter(p) 
 } 

#co(){
Using filter, posElems can be more concisely written as follows. 
}

filter を使うと、posElems は次のように簡潔に書けます。

 def posElems(xs: List[Int]): List[Int] = 
   xs filter (x => x > 0) 

#co(){
An operation related to filtering is testing whether all elements of a list satisfy a certain condition. Dually, one might also be interested in the question whether there exists an element in a list that satisfies a certain condition. These operations are embodied in the higher-order functions forall and exists of class List. 
}

フィルタに関係した操作として、リストのすべての要素が、ある条件を満たすかをテストするものがあります。対を成すものとして、リストに、ある条件を満たす要素があるか否か、という問題にも興味があるかもしれません。これらの操作はクラス List の forall と exists という高階関数として具体化されます。

 def forall(p: A => Boolean): Boolean = 
   isEmpty || (p(head) && (tail forall p)) 
 def exists(p: A => Boolean): Boolean = 
   !isEmpty && (p(head) || (tail exists p)) 

#co(){
To illustrate the use of forall, consider the question of whether a number if prime. Remember that a number n is prime of it can be divided without remainder only by one and itself. The most direct translation of this definition would test that n divided by all numbers from 2 up to and excluding itself gives a non-zero remainder. This list of numbers can be generated using a function List.range which is defined in object List as follows. 
}

forall の使い方を示すために、ある数が素数であるか否かという問題を考えましょう。数 n が素数であるとは、１と自分自身でのみ割り切れるということを思い出して下さい。最も直接的にこの定義を翻訳すると、２以上 n 未満のすべての数で割った余りが非ゼロであることをテストすることです。数のリストは、次のようにオブジェクト List で定義されている List.range 関数で生成できます。

 package scala 
 object List { ... 
   def range(from: Int, end: Int): List[Int] = 
     if (from >= end) Nil else from :: range(from + 1, end) 

#co(){
For example, List.range(2, n) generates the list of all integers from 2 up to and excluding n. The function isPrime can now simply be defined as follows. 
}

たとえば List.range(2,n) は２以上 n 未満の全整数からなるリストを生成します。関数 isPrime は次のように簡単に定義できます。

 def isPrime(n: Int) = 
   List.range(2, n) forall (x => n % x != 0) 

#co(){
We see that the mathematical definition of prime-ness has been translated directly into Scala code. 

Exercise: Define forall and exists in terms of filter. 
}

素数性の数学的定義が直接 Scala コードに翻訳されています。

演習 : filter を使って forall と exists を定義しなさい。

#co(){
Folding and Reducing Lists. Another common operation is to combine the elements of a list with some operator. For instance: 
}

&b(){リストの畳み込み　} 他のよくある操作は、リストの要素をある演算子で結合することです。たとえば

 sum(List(x1, ..., xn )) = 0 + x1 + ... + xn 
 product(List(x1, ..., xn )) = 1 * x1 * ... * xn 

#co(){
Of course, we can implement both functions with a recursive scheme: 
}

もちろん、どちらの関数も再帰的スキームで実装できます。

 def sum(xs: List[Int]): Int = xs match { 
   case Nil => 0 
   case y :: ys => y + sum(ys) 
 } 
 def product(xs: List[Int]): Int = xs match { 
   case Nil => 1 
   case y :: ys => y * product(ys) 
 }

#co(){
But we can also use the generalization of this program scheme embodied in the reduceLeft method of class List. This method inserts a given binary operator between adjacent elements of a given list. E.g. 
}

しかし、このプログラムスキームの一般化、具体的にはクラス List の reduceLeft メソッドを利用しても実装できます。このメソッドは与えられた二項演算子を、与えられたリストの隣りあう要素の間に挿入します。たとえば

 List(x1, ..., xn ).reduceLeft(op) = (...(x1 op x2 ) op ... ) op xn 

#co(){
Using reduceLeft, we can make the common pattern in sum and product apparent: 
}

reduceLeft を使って、sum と product の共通パターンを明らかにできます。

 def sum(xs: List[Int]) = (0 :: xs) reduceLeft {(x, y) => x + y} 
 def product(xs: List[Int]) = (1 :: xs) reduceLeft {(x, y) => x * y} 

#co(){
Here is the implementation of reduceLeft. 
}

次が reduceLeft の実装です。

 def reduceLeft(op: (A, A) => A): A = this match { 
   case Nil => error("Nil.reduceLeft") 
   case x :: xs => (xs foldLeft x)(op) 
 } 
 def foldLeft[B](z: B)(op: (B, A) => B): B = this match { 
   case Nil => z 
   case x :: xs => (xs foldLeft op(z, x))(op) 
 }

#co(){
We see that the reduceLeft method is defined in terms of another generally useful method, foldLeft. The latter takes as additional parameter an accumulator z, which is returned when foldLeft is applied on an empty list. That is,} 

reduceLeft メソッドは、一般的で役に立つ別のメソッド foldLeft を使って定義されていることがわかります。後者は、追加の引数として&bold(){積算器} z をとり、foldLeft が空リストに適用された時は、その値が返ります。つまり、

 (List(x1, ..., xn ) foldLeft z)(op) = (...(z op x1 ) op ... ) op xn 

#co(){
The sum and product methods can be defined alternatively using foldLeft: 
}
メソッド sum と product は foldLeft を使って、次のようにも定義できます。

 def sum(xs: List[Int]) = (xs foldLeft 0) {(x, y) => x + y} 
 def product(xs: List[Int]) = (xs foldLeft 1) {(x, y) => x * y} 

#co(){
FoldRight and ReduceRight. Applications of foldLeft and reduceLeft expand to left-leaning trees. . They have duals foldRight and reduceRight, which produce right-leaning trees. 
}

&b(){右畳み込み　} foldLeft と reduceLeft を適用すると、左に傾いた木(left-leaning tree)ができます。双対的な foldRight と reduceRight では、右に傾いた木ができます。

 List(x1, ..., xn ).reduceRight(op) = x1 op ( ... (xn−1 op xn )...) 
 (List(x1, ..., xn ) foldRight acc)(op) = x1 op ( ... (xn op acc)...) 

#co(){
These are defined as follows. 
}

それらは次のように定義されます。

 def reduceRight(op: (A, A) => A): A = this match { 
   case Nil => error("Nil.reduceRight") 
   case x :: Nil => x 
   case x :: xs => op(x, xs.reduceRight(op))
 } 
 def foldRight[B](z: B)(op: (A, B) => B): B = this match { 
   case Nil => z 
   case x :: xs => op(x, (xs foldRight z)(op)) 
 }

#co(){
Class List defines also two symbolic abbreviations for foldLeft and foldRight: 
}

クラス List では、foldLeft と foldRight の省略形記号も定義しています。

 def /:[B](z: B)(f: (B, A) => B): B = foldLeft(z)(f) 
 def :\[B](z: B)(f: (A, B) => B): B = foldRight(z)(f) 

#co(){
The method names picture the left/right leaning trees of the fold operations by forward or backward slashes. The : points in each case to the list argument whereas the end of the slash points to the accumulator (or: zero) argument z. That is, 
}

このメソッド名(記号)は、順スラッシュあるいは逆スラッシュによって、畳み込み操作の木を左/右に傾いた木の絵で表しています。それぞれの : はリスト引数を指し示し、スラッシュは積算器 (あるいはゼロ) 引数 z を指し示します。つまり

 (z /: List(x1, ..., xn ))(op) = (...(z op x1 ) op ... ) op xn 
 (List(x1, ..., xn ) :\ z)(op) = x1 op ( ... (xn op acc)...) 

#co(){
For associative and commutative operators, /: and :\ are equivalent (even though there may be a difference in efficiency). 
}

結合則および交換則をみたす演算子(op)に対しては、/: と :\ は等価です (ただし、効率には違いがありますが)。

#co(){
Exercise 9.4.2 Consider the problem of writing a function flatten, which takes a list of element lists as arguments. The result of flatten should be the concatenation of all element lists into a single list. Here is an implementation of this method in terms of :\. 
}

&b(){演習 9.4.2　} リストを要素とするリストを引数とする関数 flatten を書く問題を考察しなさい。flatten の結果は、すべての要素リストを一つのリストへと連結したものです。次は :\ を用いた、このメソッドの実装です。

 def flatten[A](xs: List[List[A]]): List[A] = 
   (xs :\ (Nil: List[A])) {(x, xs) => x ::: xs} 

#co(){
Consider replacing the body of flatten by 
}

flatten の本体を次のように置き換えた場合を考察しなさい。

 ((Nil: List[A]) /: xs) ((xs, x) => xs ::: x) 

#co(){
What would be the difference in asymptotic complexity between the two versions of flatten? In fact flatten is predefined together with a set of other userful function in an object called List in the standatd Scala library. It can be accessed from user program by calling List.flatten. Note that flatten is not a method of class List - it would not make sense there, since it applies only to lists of lists, not to all lists in general. 
}

flatten の２つのバージョンでの漸近的計算量の違いはどうなりますか？ 実際には、flatten は他の有用な関数と共に Scala ライブラリの List オブジェクトで定義されています。ユーザープログラムからは List.flatten でアクセスできます。flatten はクラス List のメソッドでないことに注意してください --- それでは意味がありません。なぜならそれは一般のリストにではなく、リストのリストにしか適用できないからです。

#co(){
List Reversal Again. We have seen in Section 9.2 an implementation of method reverse whose run-time was quadratic in the length of the list to be reversed. We now develop a new implementation of reverse, which has linear cost. The idea is to use a foldLeft operation based on the following program scheme. 
}

&b(){リストの逆転 再考　} 9.2 節で、メソッド reverse の実装と、その実行時間がリストの長さの二次式になることを見ました。ここで、線形なコストをもつ reverse の新しい実装を考えましょう。アイデアは、次のようなプログラムスキームに基づく foldLeft 操作を用いることです。

 class List[+A] { ...
   def reverse: List[A] = (z? /: this)(op?)

#co(){
It only remains to fill in the z? and op? parts. Let's try to deduce them from examples. 
}

あとは z? と op? 部分を埋めるだけです。例から推測してみましょう。

    Nil 
 = Nil.reverse // by specification 
 = (z /: Nil)(op) // by the template for reverse 
 = (Nil foldLeft z)(op) // by the definition of /: 
 = z // by definition of foldLeft 

    Nil 
 = Nil.reverse // 仕様より 
 = (z /: Nil)(op) // reverse のテンプレートより
 = (Nil foldLeft z)(op) // /: の定義より 
 = z // foldLeft の定義より 

#co(){
Hence, z? must be Nil. To deduce the second operand, let's study reversal of a list of length one. 
}

したがって z? は Nil でなくてはなりません。二つ目のオペランドを推測するために、長さが１のリストを考えます。

   List(x) 
 = List(x).reverse // by specification 
 = (Nil /: List(x))(op) // by the template for reverse, with z = Nil 
 = (List(x) foldLeft Nil)(op) // by the definition of /: 
 = op(Nil, x) // by definition of foldLeft 

   List(x) 
 = List(x).reverse // 仕様より 
 = (Nil /: List(x))(op) // reverse のテンプレートと z = Nil より
 = (List(x) foldLeft Nil)(op) // /: の定義より
 = op(Nil, x) // foldLeft の定義より 

#co(){
Hence, op(Nil, x) equals List(x), which is the same as x :: Nil. This suggests to take as op the :: operator with its operands exchanged. Hence, we arrive at the following implementation for reverse, which has linear complexity.} 

したがって op(Nil, x) は List(x) に等しく、それは x :: Nil と等しい。これから op は :: で、オペランドを交換したものだと分かります。以上から、次のような、線形な計算量をもつ reverse の実装を得ます。

 def reverse: List[A] = 
   ((Nil: List[A]) /: this) {(xs, x) => x :: xs} 

#co(){
(Remark: The type annotation of Nil is necessary to make the type inferencer work.) 
}

(注釈 : Nil の型アノテーションは、型推論させるために必要です)

#co(){
Exercise 9.4.3 Fill in the missing expressions to complete the following definitions of some basic list-manipulation operations as fold operations. 
}

&b(){演習 9.4.3　} 書かれていない式を埋めて、次の基本的なリスト操作定義を畳み込み操作として完成しなさい。

 def mapFun[A, B](xs: List[A], f: A => B): List[B] = 
   (xs :\ List[B]()){ ?? } 
 def lengthFun[A](xs: List[A]): int = 
   (0 /: xs){ ?? } 

#co(){
Nested Mappings. We can employ higher-order list processing functions to express many computations that are normally expressed as nested loops in imperative languages. 
}

&b(){ネストしたマップ　} 命令型言語において通常、ループのネストで書かれる多くの計算を、高階リスト操作関数を使って書くことができます。

#co(){
As an example, consider the following problem: Given a positive integer n, find all pairs of positive integers i and j , where 1 ≤ j < i < n such that i + j is prime. For instance, if n = 7, the pairs are 
}

例として次のような問題を考えましょう。与えられた正整数 n に対し、正整数 i と j のすべての組 (ただし 1 <= j < i < n で、i+j が素数)を求めなさい。たとえば n = 7 であれば対は、

 i      2 3 4 4 5 6 6 
 j      1 2 1 3 2 1 5 
 i + j 3 5 5 7 7 7 11 

#co(){
A natural way to solve this problem consists of two steps. In a first step, one generates the sequence of all pairs (i , j ) of integers such that 1 ≤ j < i < n. In a second step one then filters from this sequence all pairs (i , j ) such that i + j is prime. 
}

問題を解く自然な方法は２つのステップからなります。最初のステップでは、1<=j < i < n を満たす整数の対 (i,j) の列を作ります。第二のステップでは、すべての対 (i,j) の列から、i+j が素数であるものをフィルタします。

#co(){
Looking at the first step in more detail, a natural way to generate the sequence of pairs consists of three sub-steps. First, generate all integers between 1 and n for i.

Second, for each integer i between 1 and n, generate the list of pairs (i , 1) up to (i , i − 1). This can be achieved by a combination of range and map: 
}

最初のステップをより詳細に見ましょう。対の列を生成する自然な方法は３つのサブステップからなります。最初に、1 以上 n未満の整数を i のために作ります。

次に、1 以上 n 未満の各 i に対して、(i,1) から (i,i-1) までの対のリストを作ります。これは range と map の組み合わせによって可能です。

 List.range(1, i) map (x => (i, x)) 

#co(){
Finally, combine all sublists using foldRight with :::. Putting everything together gives the following expression: 
}

最後に、すべてのサブリストを foldright と ::: を使って連結します。すべてを組み合わせると次の式が得られます。

 List.range(1, n) 
   .map(i => List.range(1, i).map(x => (i, x))) 
   .foldRight(List[(Int, Int)]()) {(xs, ys) => xs ::: ys} 
   .filter(pair => isPrime(pair._1 + pair._2)) 

#co(){
Flattening Maps. The combination of mapping and then concatenating sublists resulting from the map is so common that we there is a special method for it in class List: 
}

&b(){マップの平坦化　} マッピングと、マップで得られたサブリストの連結という組み合わせは、非常によく使うので、クラス List には特別なメソッドがあります。

 abstract class List[+A] { ... 
   def flatMap[B](f: A => List[B]): List[B] = this match { 
     case Nil => Nil 
     case x :: xs => f(x) ::: (xs flatMap f) 
   } 
 } 

#co(){
With flatMap, the pairs-whose-sum-is-prime expression could have been written more concisely as follows. 
}

flatMap を使うと「和が素数となる対」の式は、次のようにさらに簡潔に書けます。
 List.range(1, n) 
   .flatMap(i => List.range(1, i).map(x => (i, x))) 
   .filter(pair => isPrime(pair._1 + pair._2))

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

----
#comment