「Example9.5」の編集履歴（バックアップ）一覧に戻る
Example9.5 - (2008/08/28 (木) 23:46:40) のソース
** 9.5 Summary
This chapter has introduced lists as a fundamental data structure in programming. Since lists are immutable, they are a common data type in functional programming languages. They have a role comparable to arrays in imperative languages. However, the access patterns between arrays and lists are quite different. Where array accessing is always done by indexing, this is much less common for lists. We have seen that scala.List defines a method called apply for indexing however this operation is much more costly than in the case of arrays (linear as opposed to constant time). Instead of indexing, lists are usually traversed recursively, where recursion steps are usually based on a pattern match over the traversed list. There is also a rich set of higher-order combinators which allow one to instantiate a set of predefined patterns of computations over lists.
この章ではリストをプログラミングの基礎的なデータ構造として紹介しました。リストは不変的なので関数型プログラミング言語では一般的なデータ型です、命令型言語における配列と比較出来る役割を持っています。しかし配列とリストではアクセス方法に大きな違いがあります。配列へのアクセスが常に添字によってなされますが、リストに対してはそれは滅多に行われません。scala.List には添字アクセスの為の apply メソッドが定義されているのを見ましたが、この操作は配列の場合よりずっとコストがかかります (定数時間に対して線形)。添字の代わりに、通常リストは再帰によって横断され、再帰のステップは通常横断するリストへのパターンマッチに基づきます。また一揃えの豊富な高階コンビネータによって、予め定義されたリストに対する計算パターンを具体化出来ます。
----
#comment
