「ExampleChap2」の編集履歴（バックアップ）一覧に戻る
ExampleChap2 - (2010/10/22 (金) 10:07:44) のソース
#co(){
Chapter 2 A First Example
As a first example, here is an implementation of Quicksort in Scala.
}
* 第 2 章 最初の例
最初の例として、Scala でのクイックソートの実装を示します。
def sort(xs: Array[Int]) {
def swap(i: Int, j: Int) {
val t = xs(i); xs(i) = xs(j); xs(j) = t
}
def sort1(l: Int, r: Int) {
val pivot = xs((l + r) / 2)
var i = l; var j = r
while (i <= j) {
while (xs(i) < pivot) i += 1
while (xs(j) > pivot) j -= 1
if (i <= j) {
swap(i, j)
i += 1
j -= 1
}
}
if (l < j) sort1(l, j)
if (j < r) sort1(i, r)
}
sort1(0, xs.length - 1)
}
#co(){
The implementation looks quite similar to what one would write in Java or C. We use the same operators and similar control structures. There are also some minor syntactical differences. In particular:
- Definitions start with a reserved word. Function definitions start with def, variable definitions start with var and definitions of values (i.e. read only variables) start with val.
- The declared type of a symbol is given after the symbol and a colon. The declared type can often be omitted, because the compiler can infer it from the context.
- Array types are written Array[T] rather than T[], and array selections are written a(i) rather than a[i].
- Functions can be nested inside other functions. Nested functions can access parameters and local variables of enclosing functions. For instance, the name of the array xs is visible in functions swap and sort1, and therefore need not be passed as a parameter to them.
}
この実装は Java や C で書くものと大変よく似ています。Scala では同じ演算子、似た制御構造を使います。ただし、少しばかり構文的な違いがあります。具体的には、
- 定義は予約語で始まります。関数定義は def で始まり、変数定義は var で始まり、値 (すなわち読み出し専用の変数) の定義は val で始まります。
- シンボルの型宣言は、シンボルとコロンの後に書きます。型宣言は省略できることもあります。コンパイラが文脈から推論するからです。
- 配列の型は T[] ではなく Array[T] と書き、配列の指定は a[i] ではなく a(i) と書きます。
- 関数は他の関数の内側に入れ子にできます。入れ子になった関数は、それを包む関数の引数やローカル変数にアクセスできます。次の例では、配列 xs は関数 swap と sort1 から見えるため、それらに引数として渡す必要はありません。
#co(){
So far, Scala looks like a fairly conventional language with some syntactic peculiarities. In fact it is possible to write programs in a conventional imperative or object-oriented style. This is important because it is one of the things that makes it easy to combine Scala components with components written in mainstream languages such as Java, C# or Visual Basic.
However, it is also possible to write programs in a style which looks completely different. Here is Quicksort again, this time written in functional style.
}
今までのところ、Scala は構文に少し変わった点があるものの、かなり普通の言語のように見えます。実際、プログラムを書くのは、普通の命令型(手続き型)でもオブジェクト指向でも可能です。これは重要なことです。なぜならこれは、Scala のコンポーネント(部品)を、Java、C#、Visual Basic などの主流言語で書かれたコンポーネントと組み合わせることを容易にする仕掛けの一つだからです。
しかし、プログラムをまったく違うスタイルでも書けます。クイックソートを再び、今度は関数型プログラミング風に書いてみます。
def sort(xs: Array[Int]): Array[Int] = {
if (xs.length <= 1) xs
else {
val pivot = xs(xs.length / 2)
Array.concat(
sort(xs filter (pivot >)),
xs filter (pivot ==),
sort(xs filter (pivot <)))
}
}
#co(){
The functional program captures the essence of the quicksort algorithm in a concise way:
- If the array is empty or consists of a single element, it is already sorted, so
return it immediately.
- If the array is not empty, pick an an element in the middle of it as a pivot.
- Partition the array into two sub-arrays containing elements that are less than, respectively greater than the pivot element, and a third array which contains elements equal to pivot.
- Sort the first two sub-arrays by a recursive invocation of the sort function.1
- The result is obtained by appending the three sub-arrays together.
}
関数型プログラミングはクイックソート・アルゴリズムの本質を簡潔にとらえています。
- 配列が空あるいは要素が１つなら、すでにソートされているので、直ちにそれを返します。
- 配列が空でなければ、配列の真ん中の要素をピボットとして選びます。
- 配列を副配列に分割し、一つにはピボットより小さな要素を、もう一つにはピボットより大きな要素を、そして三つ目の副配列にはピボットと等しい要素を入れます。
- 初めの２つの副配列を sort 関数の再帰呼び出しでソートします(*1)。
- これら３つの副配列をひとつに結合して、結果を得ます。
#co(){
(*1) This is not quite what the imperative algorithm does; the latter partitions the array into two sub-arrays containing elements less than or greater or equal to pivot.
}
(*1) これは命令型アルゴリズムのすることと全く同じという訳ではありません。後者では元の配列を、要素がピボットに対して小さい、あるいは、大きいか等しい、に分けて２つの副配列へ分割します。
#co(){
Both the imperative and the functional implementation have the same asymptotic complexity - O(N log(N)) in the average case and O(N2) in the worst case. But where the imperative implementation operates in place by modifying the argument array, the functional implementation returns a new sorted array and leaves the argument array unchanged. The functional implementation thus requires more transient memory than the imperative one.
}
命令型と関数型の実装のどちらも同じ漸近的計算量 --- 平均的な場合は O(N log(N))、最悪の場合は O(N2) になります。しかし命令型実装が引数の配列自体を変更するのに対して、関数型実装はソートされた新しい配列を返し、引数の配列を変更しません。ですから、関数型実装は命令型実装よりも一時的なメモリを多く必要とします。
#co(){
The functional implementation makes it look like Scala is a language that's specialized for functional operations on arrays. In fact, it is not; all of the operations used in the example are simple library methods of a sequence class Seq[T] which is part of the standard Scala library, and which itself is implemented in Scala. Because arrays are instances of Seq all sequence methods are available for them.
}
この関数型実装によって Scala が配列への関数的操作に特化した言語の様に見えます。実際は違います。この例で用いた操作は、Scala の標準ライブラリの一部である&bold(){シーケンス}クラス Seq[T] のたんなるライブラリメソッドであり、そのライブラリ自身も Scala で実装されています。そして、配列は Seq のインスタンスなのでシーケンスクラスのメソッドはすべて使用できるのです。
#co(){
In particular, there is the method filter which takes as argument a predicate function. This predicate function must map array elements to boolean values. The result of filter is an array consisting of all the elements of the original array for which the given predicate function is true. The filter method of an object of type Array[T] thus has the signature
}
とりわけ、&bold(){述語関数}(predicate function)を引数にとるメソッド filter があります。この述語関数は、配列の各要素に対して真偽値を返す必要があります。filter の結果は配列であり、元の配列の要素で述語関数が真を返すもの全てからなります。Array[T] 型オブジェクトの filter メソッドは、次のような書き方をします。
def filter(p: T => Boolean): Array[T]
#co(){
Here, T => Boolean is the type of functions that take an element of type t and return a Boolean. Functions like filter that take another function as argument or return one as result are called higher-order functions.
}
ここで T => Boolean は関数の型を表わし、その関数は型 T の引数をとり Boolean 値を返します。filter のように、他の関数を引数としたり結果として返す関数は、&bold(){高階関数}と呼ばれます。
#co(){
Scala does not distinguish between identifiers and operator names. An identifier can be either a sequence of letters and digits which begins with a letter, or it can be a sequence of special characters, such as "+", "*", or ":". Any identifier can be used as an infix operator in Scala. The binary operation E op E' is always interpreted as the method call E.op(E'). This holds also for binary infix operators which start with a letter. Hence, the expression xs filter (pivot >) is equivalent to the method call xs.filter(pivot >). }
Scala は識別子と演算子の名前を区別しません。識別子は「文字で始まる、文字と数字からなる列」でも、「 '+'、'*'、':' のような特殊文字からなる列」でも構いません。Scala ではすべての識別子は中置演算子として使えます。二項演算 E op E' は常に、メソッド呼び出し E.op(E') として解釈されます。これは文字で始まる中置二項演算子にもあてはまります。したがって、式 xs filter (pivot >) は、メソッド呼び出し xs.filter(pivot >) と等価です。
#co(){
In the quicksort program, filter is applied three times to an anonymous function argument. The first argument, pivot >, represents a function that takes an argument x and returns the value pivot > x . This is an example of a partially applied function. Another, equivalent way to write this function which makes the missing argument explicit is x => pivot > x. The function is anonymous, i.e. it is not defined with a name. The type of the x parameter is omitted because a Scala compiler can infer it automatically from the context where the function is used. To summarize, xs.filter(pivot >) returns a list consisting of all elements of the list xs that are smaller than pivot.
}
先のクイックソートプログラムで、filter は無名関数の引数に３回適用されています。最初の引数 pivot > は、引数 x をとり、値 pivot > x を返す関数を表しています。これは&bold(){部分適用された関数}の例です。この関数を、見えていない引数を明示して x => pivot > x と書いても同じです。この関数は無名、つまり名前を付けて定義されていません。引数 x の型が省略されているのは、Scala コンパイラが、関数の使用されている文脈から自動的に推論できるからです。まとめると xs.filter(pivot >) は、リスト xs の要素で pivot より小さいもの全てからなるリストを返します。
#co(){
Looking again in detail at the first, imperative implementation of Quicksort, we find that many of the language constructs used in the second solution are also present, albeit in a disguised form.
For instance, "standard" binary operators such as +, -, or < are not treated in any special way. Like append, they are methods of their left operand. Consequently, the expression i + 1 is regarded as the invocation i.+(1) of the + method of the integer value x. Of course, a compiler is free (if it is moderately smart, even expected) to recognize the special case of calling the + method over integer arguments and to generate efficient inline code for it.
}
最初のクイックソートの命令型実装をよく見ると、二つ目の例で使われている多くの構文が、隠された形ではあるものの、出てきていることが分かります。
たとえば、+、-、< のような「普通の」二項演算子が特別扱かいされていないことが分かります。append などと同じく、その左側にあるオペランドのメソッドです。したがって、式 i + 1 は整数値 i のメソッド + の呼び出し i.+(i) とみなされます。もちろんコンパイラは、整数引数に対するメソッド + の呼び出しを特例とみなし、効率のよいインラインコードを生成できます (もし、ほどほどに賢いコンパイラなら、そうすることが期待されます)。
#co(){
For efficiency and better error diagnostics the while loop is a primitive construct in Scala. But in principle, it could have just as well been a predefined function. Here is a possible implementation of it:
The While function takes as first parameter a test function, which takes no parameters and yields a boolean value. As second parameter it takes a command function which also takes no parameters and yields a result of type Unit. While invokes the command function as long as the test function yields true.}
効率と、より良いエラー診断ができるように、while ループは Scala の組み込み構文となっています。しかし原理的には、たんなる事前定義された関数であってもよいのです。次は考えうる実装です。
def While (p: => Boolean) (s: => Unit) {
if (p) { s ; While(p)(s) }
}
この While 関数は最初の引数としてテスト関数をとり、そのテスト関数は引数をとらずブール値を返します。二番目の引数としてコマンド関数をとり、そのコマンド関数も引数をとらず、Unit 型の結果値を返します。While 関数はテスト関数が真を返す限り、コマンド関数を呼び出します。
#co(){
Scala's Unit type roughly corresponds to void in Java; it is used whenever a function does not return an interesting result. In fact, because Scala is an expression-oriented language, every function returns some result. If no explicit return expression is given, the value (), which is pronounced "unit", is assumed. This value is of type Unit. Unit-returning functions are also called procedures. Here's a more "expression-oriented" formulation of the swap function in the first implementation of quicksort, which makes this explicit:
}
Scala の Unit 型は概ね Java の void に相当し、関数が特定の結果(戻り値)を返さない場合に使います。実際のところ、Scala は式指向の言語なので、すべての関数は何かしら結果を返します。もし明示的な戻り値が与えられなければ、値 () --- "unit" と発音します --- が肩代わりします。この値は Unit 型です。Unit を返す関数もまた、手続き(procedure)と呼ばれます。クイックソートの最初の実装中の swap 関数をさらに「式指向」な形にして、これを明示します。
def swap(i: Int, j: Int) {
val t = xs(i); xs(i) = xs(j); xs(j) = t
()
}
#co(){
The result value of this function is simply its last expression - a return keyword is not necessary. Note that functions returning an explicit value always need an "=" before their body or defining expression.
}
この関数の結果(戻り値)は単に最後の式です。キーワード return は必要ありません。注意点として、明示的に値を返す関数は常に、「=」を本体あるいは定義式の前に必要とします。
#center(){[[前ページ>ExampleChap1]] [[ 2 章>ExampleChap2]] [[目次>ScalaByExample和訳]] [[次ページ>ExampleChap3]]}
----
ーーーーー 修正案 by ryugate
この述語関数は配列の要素をブール値に写像させる必要があります。
→ (filterの引数である) この述語関数は配列の要素をブール値に写像させる必要があります。
filter の結果は与えられた述語関数が真となる元の配列のすべての要素からなる配列です
→filter の結果は元の配列の要素のなかで与えられた述語関数が真となるすべての要素からなる配列です
- ご指摘どうもありがとうございます＞ryugateさん。 -- tmiya (2008-05-14 06:59:09)
- おぉ。コメント欄があったのですね。直接書いちゃってスミマセン。気づいたら、またコメントさせていただきます。 -- ryugate (2008-05-19 21:53:05)
- いえ、直接本文に追記して頂いてOKです。wikiに慣れてない人の為のコメント欄です。 -- tmiya (2008-05-25 23:26:44)
- sort関数の一番外の{}は無くてOKでは？ ifの単文なので。 -- Lyc (2010-01-10 06:43:43)
- repl環境だとエラーになりますね -- tksk (2010-07-25 02:20:32)
ーーーーー HELP
上の「文字で始まる文字と数字からなる列」の修正を求めます。
#comment
