前章に引き続き，この章でも永続データの代表選手であるリストについて説明します。そして，実践的な文字列プログラミングの例として，最長重複文字列問題を解きます。

永続データとしてのリスト

関数プログラミングの入門書では，説明をリストから始めることが多いようです。その理由は，リストが最も簡単な永続データだからです。ここでいうリストとは，図1に示すような一方向リストのことです。ここに示されているのは文字のリストであり，[]はHaskellでの空リストです。

関数プログラミングの説明をリストから始めるのはよくないと主張する人もいます。なぜなら，リストの処理は遅いため，実践的にはほかのデータ構造（注1）を用いることが多いからです。しかし筆者としては，リストがわからない人がほかの永続データを理解できるとは思えないので，慣習通りリストから始めます。

リストには3つの基本的な操作があります。

• リストの先頭に要素を加える
• リストの先頭要素を取り出す
• リストの先頭要素を取り除いた残りのリストを取り出す

驚くべきことに，リストを取り扱う関数は，この三種の神器と再帰のみですべて実装できます。これらの操作を実際に試してみましょう。

注1）

Haskellの場合，文字列であればByteStringやTextなどです。

リストの先頭に要素を加える

Haskellでリストの先頭に要素を加えるには，二項演算子:（コンス）を使います。

> let xs = ['b','o','a','r','d']
> let ys = 'a' : xs
> ys
"aboard"

文字列「aboard」は，['a','b','o','a','r','d']の別表現だったことを思い出せば，ちゃんとリストxsの先頭に文字aが追加されているとわかります。

では，どうしてリストが永続データなのでしょうか？ 図2を見てください。xsとysで['b','o','a','r','d']が共有されていることがわかります。

関数プログラミングでは再代入はできませんから，演算子:を使ったあとも，xsの値が変化してはいけません。上記の対話環境の続きで，xsの値を調べてみると，実際に元のままであるとわかります。

> xs
"board"

このように，不変でしかも共有効率が高いのが永続データの特徴です。

リストから先頭要素を取り出す

Haskellで，リストの先頭要素を取り出すには関数headを使います。

> head ys
'a'

先頭要素を取り除いた残りのリストを取り出す

また，リストの先頭要素を取り除いた残りを取り出すには関数tailを使用します。

> tail ys
"board"

ただし，関数型言語では後述するパターンマッチが使えるので，この種の関数を使う頻度はあまり多くありません。

パターンマッチでリストの一部を取り出す

パターンマッチの例として，高階関数mapの実装を再び眺めてみましょう。

map :: (a -> b) -> [a] -> [b]
map f [] = []
map f (x:xs) = f x : map f xs

関数の引数に現れるf，[]，および(x:xs)がパターンになります。fのような変数の場合は，必ずマッチします。[]は空リストにマッチします。(x:xs)は，空でないリストにマッチし，先頭の要素にx，残りのリストにxsという名前が付きます。

この関数の意味するところは次の通りです。

• 第二引数が空リストにマッチしたら空リストを返す
• 第二引数が空でないリストにマッチしたら，「⁠fをリストの先頭に適用した結果」を「残りのリストを自分自身で処理した結果のリスト」の先頭に加える

このようにHaskellでは，関数のトップレベルで分岐が記述できます。

実際の動作例を図3に示します。

map isDigit ['1','a']

isDigit '1' : map ['a']

True : map ['a']

True : isDigit 'a' : map isDigit []

True : False : map isDigit []

True : False : []