9.4 リストクラスの定義Ⅱ:高階メソッド
ここまでに見た例が示すことは、リストに対する関数はしばしば似た構造をしているということです。リストに対する計算パターンをいくつか見ることができます。たとえば、
ある方法で全ての要素を変換する
条件を満たす全ての要素を取り出す。
ある演算子を用いて全ての要素を結合する
関数型プログラミング言語では高階関数を使うことで、パターンを実装する汎用的な関数を書けます。よく使われる高階関数について議論しますが、それらはクラス List のメソッドとして実装されています。
リストのマッピング リストの各要素を変換して結果のリストを得ることは、よくある操作です。たとえば、リストの各要素を与えられた数だけ倍するのは、
def scaleList(xs: List[Double], factor: Double): List[Double] = xs match { case Nil => xs case x :: xs1 => x * factor :: scaleList(xs1, factor) }
このパターンは、クラス 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) }
map を用いると、scaleList は次のように簡潔になります。
def scaleList(xs: List[Double], factor: Double) = xs map (x => x * factor)
ほかの例として、行のリストとして表現されている行列の、指定された列を返す問題、ただし各行もまたリストである、を考えましょう。これは次の関数 column で与えられます。
def column[A](xs: List[List[A]], index: Int): List[A] = xs map (row => row(index))
map と近い関係にあるのは foreach メソッドで、リストの全要素に関数を適用しますが、結果のリストを組み立てません。この関数はですから、副作用のためだけのものです。foreach は次のように定義されています。
def foreach(f: A => Unit) { this match { case Nil => () case x :: xs => f(x); xs.foreach(f) } }
たとえば、この関数はリストの要素すべてを表示するのに使えます。
xs foreach (x => println(x))
演習 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 ??
リストのフィルタリング 他のよくある操作は、リストの、与えられた条件を満たすすべての要素を取り出す操作です。たとえば整数リスト中の正の要素からなるリストを返すには、
def posElems(xs: List[Int]): List[Int] = xs match { case Nil => xs case x :: xs1 => if (x > 0) x :: posElems(xs1) else posElems(xs1) }
このパターンは、クラス 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) }
filter を使うと、posElems は次のように簡潔に書けます。
def posElems(xs: List[Int]): List[Int] = xs filter (x => x > 0)
フィルタに関係した操作として、リストのすべての要素が、ある条件を満たすかをテストするものがあります。対を成すものとして、リストに、ある条件を満たす要素があるか否か、という問題にも興味があるかもしれません。これらの操作はクラス 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))
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)
たとえば List.range(2,n) は２以上 n 未満の全整数からなるリストを生成します。関数 isPrime は次のように簡単に定義できます。
def isPrime(n: Int) = List.range(2, n) forall (x => n % x != 0)
素数性の数学的定義が直接 Scala コードに翻訳されています。
演習 : filter を使って forall と exists を定義しなさい。
リストの畳み込み 他のよくある操作は、リストの要素をある演算子で結合することです。たとえば
sum(List(x1, ..., xn )) = 0 + x1 + ... + xn product(List(x1, ..., xn )) = 1 * x1 * ... * xn
もちろん、どちらの関数も再帰的スキームで実装できます。
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) }
しかし、このプログラムスキームの一般化、具体的にはクラス List の reduceLeft メソッドを利用しても実装できます。このメソッドは与えられた二項演算子を、与えられたリストの隣りあう要素の間に挿入します。たとえば
List(x1, ..., xn ).reduceLeft(op) = (...(x1 op x2 ) op ... ) op xn
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}
次が 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) }
reduceLeft メソッドは、一般的で役に立つ別のメソッド foldLeft を使って定義されていることがわかります。後者は、追加のパラメータとして 積算器 z をとり、foldLeft が空リストに適用された時は、その値が返ります。つまり、
(List(x1, ..., xn ) foldLeft z)(op) = (...(z op x1 ) op ... ) op xn
メソッド 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}
右畳み込み 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)...)
それらは次のように定義されます。
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)) }
クラス 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)
このメソッド名(記号)は、順スラッシュあるいは逆スラッシュによって、畳み込み操作の木を左/右に傾いた木の絵で表しています。それぞれの : はリスト引数を指し示し、スラッシュは積算器 (あるいはゼロ) 引数 z を指し示します。つまり
(z /: List(x1, ..., xn ))(op) = (...(z op x1 ) op ... ) op xn (List(x1, ..., xn ) :\ z)(op) = x1 op ( ... (xn op acc)...)
結合則および交換則をみたす演算子(op)に対しては、/: と :\ は等価です (ただし、効率には違いがありますが)。
演習 9.4.2 リストを要素とするリストを引数とする関数 flatten を書く問題を考察しなさい。flatten の結果は、すべての要素リストを一つのリストへと連結したものです。次は :\ を用いた、このメソッドの実装です。
def flatten[A](xs: List[List[A]]): List[A] = (xs :\ (Nil: List[A])) {(x, xs) => x ::: xs}
flatten の本体を次のように置き換えた場合を考察しなさい。
((Nil: List[A]) /: xs) ((xs, x) => xs ::: x)
flatten の２つのバージョンでの漸近的計算量の違いはどうなりますか？ 実際には、flatten は他の有用な関数と共に Scala ライブラリの List オブジェクトで定義されています。ユーザープログラムからは List.flatten でアクセスできます。flatten はクラス List のメソッドでないことに注意してください --- それでは意味がありません。なぜならそれは一般のリストにではなく、リストのリストにしか適用できないからです。
リストの逆転 再考 9.2 節で、メソッド reverse の実装と、その実行時間がリストの長さの二次式になることを見ました。ここで、線形なコストをもつ reverse の新しい実装を考えましょう。アイデアは、次のようなプログラムスキームに基づく foldLeft 操作を用いることです。
class List[+A] { ... def reverse: List[A] = (z? /: this)(op?)
あとは z? と op? 部分を埋めるだけです。例から推測してみましょう。
Nil = Nil.reverse // 仕様より = (z /: Nil)(op) // reverse のテンプレートより = (Nil foldLeft z)(op) // /: の定義より = z // foldLeft の定義より
したがって z? は Nil でなくてはなりません。二つ目のオペランドを推測するために、長さが１のリストを考えます。
List(x) = List(x).reverse // 仕様より = (Nil /: List(x))(op) // reverse のテンプレートと z = Nil より = (List(x) foldLeft Nil)(op) // /: の定義より = op(Nil, x) // foldLeft の定義より
したがって op(Nil, x) は List(x) に等しく、それは x :: Nil と等しい。これから op は :: で、オペランドを交換したものだと分かります。以上から、次のような、線形な計算量をもつ reverse の実装を得ます。
def reverse: List[A] = ((Nil: List[A]) /: this) {(xs, x) => x :: xs}
(注釈 : Nil の型アノテーションは、型推論させるために必要です)
演習 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){ ?? }
ネストしたマップ 命令型言語において通常、ループのネストで書かれる多くの計算を、高階リスト操作関数を使って書くことができます。
例として次のような問題を考えましょう。与えられた正整数 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
問題を解く自然な方法は２つのステップからなります。最初のステップでは、1<=j < i < n を満たす整数の対 (i,j) の列を作ります。第二のステップでは、すべての対 (i,j) の列から、i+j が素数であるものをフィルタします。
最初のステップをより詳細に見ましょう。対の列を生成する自然な方法は３つのサブステップからなります。最初に、1 以上 n未満の整数を i のために作ります。
次に、1 以上 n 未満の各 i に対して、(i,1) から (i,i-1) までの対のリストを作ります。これは range と map の組み合わせによって可能です。
List.range(1, i) map (x => (i, x))
最後に、すべてのサブリストを 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))
マップの平坦化 マッピングと、マップで得られたサブリストの連結という組み合わせは、非常によく使うので、クラス 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) } }
flatMap を使うと「和が素数となる対」の式は、次のようにさらに簡潔に書けます。
List.range(1, n) .flatMap(i => List.range(1, i).map(x => (i, x))) .filter(pair => isPrime(pair._1 + pair._2))