前章に引き続き、この章でも永続データの代表選手であるリストについて説明します。そして、実践的な文字列プログラミングの例として、最長重複文字列問題を解きます。 永続データとしてのリスト 関数プログラミングの入門書では、説明をリストから始めることが多いようです。その理由は、リストが最も簡単な永続データだからです。ここでいうリストとは、図1に示すような一方向リストのことです。ここに示されているのは文字のリストであり、[]はHaskellでの空リストです。 図1 リストの構造 関数プログラミングの説明をリストから始めるのはよくないと主張する人もいます。なぜなら、リストの処理は遅いため、実践的にはほかのデータ構造[1]を用いることが多いからです。しかし筆者としては、リストがわからない人がほかの永続データを理解できるとは思えないので、慣習通りリストから始めます。 リストには3つの基本的な操作があります