「ExampleChap2」の編集履歴（バックアップ）一覧に戻る
ExampleChap2 - (2008/05/14 (水) 06:59:09) のソース
* Chapter 2 A First Example
As a first example, here is an implementation of Quicksort in Scala.
最初の例として、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)
}
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:
この実装は Java や C で書くものと大変良く似ています。同じ演算子、類似の制御構造を使用します。多少の構文的な差異があります。特に、
- 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.
- 定義は予約語で始まります。関数定義は def で始まり、変数定義は var で始まり、値 (すなわち読み出し専用の変数) の定義は val で始まる。
- シンボルの宣言型は、シンボルとコロンの後に書きます。宣言型は省略出来ます。コンパイラが文脈から推論するからです。
- 配列型は T[] ではなく Array[T] と書き、配列の選択は a[i] ではなく a(i) と書きます。
- 関数は他の関数の内側に入れ子に出来ます。入れ子になった関数は、それを包む関数の仮引数やローカル変数にアクセス出来ます。例えば配列 xs の名前は関数 swap と sort1 から見えるため、それらに仮引数として渡す必要はありません。
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.
今までのところ、Scala は構文に少し変わった点があるものの、かなり普通の言語に見えます。実際、プログラムを普通の命令型あるいはオブジェクト指向で書く事も可能です。Scala で書かれたコンポーネントを、例えば Java, C#, 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.
しかし、プログラムを全く違った様に書く事も可能です。クイックソートを再び、今度は関数型風に書いてみます。
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 <)))
}
}
> 訳注：元の英語版のソースは一番外の{}が無いためエラーになる。上記は修正してある。
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
- 上記の３つの副配列を一緒に結合する事で結果を得ます。
>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 これは命令的なアルゴリズムのしている事と同じという訳ではありません。後者 (関数型風の方を指す?) は配列をピボットに対して小さいか大きいか等しいかで２つの副配列に分割します。
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) を持っています。しかし命令型実装が引数の配列を変更する事によって同じ場所で動作するのに対して、関数型実装は新しくソートされた配列を返し引数の配列は変更しません。関数型実装はそれ故に命令型実装に比べ一時的なメモリをより多く必要とします。
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 の標準ライブラリの一部である「シーケンス」のクラス Seq[T] の単なるライブラリメソッドであり、そのライブラリ自身も Scala で実装されています。配列は Seq のインスタンスなのでシーケンスのメソッドは全て使用可能です。
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
特に「述語関数」を引数に取るメソッド filter があります。この述語関数は配列の酔う尾をブール値に写像させる必要があります。filter の結果は与えられた述語関数が真となる元の配列の全ての要素からなる配列です。Array[T] 型のオブジェクトの filter メソッドは下記のシグネチャを持ちます。
ーーーーー 修正案 by ryugate
この述語関数は配列の酔う尾をブール値に写像させる必要があります。
→（filterの引数である）この述語関数は配列の要素をブール値に写像させる必要があります。
filter の結果は与えられた述語関数が真となる元の配列の全ての要素からなる配列です
→filter の結果は元の配列の要素のなかで与えられた述語関数が真となる全ての要素からなる配列です
ーーーーー
def filter(p: T => Boolean): Array[T]
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 のように他の関数を引数として取ったり、関数を結果として返す様な関数は、「高階関数」と呼ばれます。
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 o p E ′ is always interpreted as the method call E .o p (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 >) と等価です。
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 を返す関数を表しています。これは「部分適用された関数」の例です。表れていない引数を明示的にしてこの関数を書く別の等価な方法は x => pivot > x です。この関数は無名、すなわち名前を付けて定義されていません。仮引数 x の型は省略されているのは Scala コンパイラが関数の使用される文脈から自動的に推論可能な為です。纏めると xs.filter(pivot >) はリスト xs の要素で pivot より小さいもの全てからなるリストを返します。
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) と看做されます。もちろんコンパイラは自由に整数引数に対するメソッド + の呼び出しの特例として認識し、効率の良いインラインコードを生成出来ます。（もしほどほどに賢いコンパイラならば、そうするのが期待されます）
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:
効率とより良いエラー診断の為に while ループは Scala ではプリミティブな構文です。しかし原理的には、単に予め定義された関数でもあり得ます。下記は考えうる実装です。
def While (p: => Boolean) (s: => Unit) {
if (p) { s ; While(p)(s) }
}
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 関数は最初の仮引数をテスト関数とし、それは引数を取らずブール値を返します。二番目の仮引数として同様に仮引数を取らず Unit 型の結果を返すコマンド関数を取ります。While 関数はテスト関数が真を返す限りコマンド関数を呼び出します。
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 を返す関数は「手続き」とも呼ばれます。最初のクイックソートの実装の swap 関数のより「式指向」な定式化は、これをより明示的に示します。
def swap(i: Int, j: Int) {
val t = xs(i); xs(i) = xs(j); xs(j) = t
()
}
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 は必須ではありません。注意点として、明示的に値を返す関数は常に "=" を本体あるいは定義式の前に必要とします。
----
- ご指摘どうもありがとうございます＞ryugateさん。 -- tmiya (2008-05-14 06:59:09)
#comment
