* 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 で書くものと大変良く似ています。Scalaでは同じ演算子、類似の制御構造を使用します。ただし、多少の構文的な差異があります。具体的には、 - 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. - 配列が空あるいは要素が１つならば、既にソートされている為、直ちにリターンします。 - 配列が空で無ければ、配列の真ん中の要素をピボットとして選択します。 - 配列を２つの副配列に分割し、片方にはピボットより小さな要素を含む様に、もう片方にはピボットより大きな要素を含む様にします。そして３つ目の配列にはピボットと等しい要素を含む様にします。 > 訳注：副配列は3つでは? - 初めの２つの副配列を 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 これは手続き型のアルゴリズムのしている事と同じという訳ではありません。後者 (関数型風の方を指す?) の場合、元の配列の要素をピボットに対して小さいか大きいか等しいかで２つ(3つ?)に分けてそれぞれの副配列へ代入します。 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 >) 」と等価です。 ーーーーー HELP 上の「文字で始まる文字と数字からなる列」の修正を求めます。 ーーーーー 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) - おぉ。コメント欄があったのですね。直接書いちゃってスミマセン。気づいたら、またコメントさせていただきます。 -- ryugate (2008-05-19 21:53:05) - いえ、直接本文に追記して頂いてOKです。wikiに慣れてない人の為のコメント欄です。 -- tmiya (2008-05-25 23:26:44) #comment
下から選んでください:
