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

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

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

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

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

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

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

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

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 : []

最長重複文字列問題

Haskellでは、文字のリストが文字列でした。整数のリストよりも文字列のほうが親しみが湧きやすいと思いますので、リストプログラミングの例として文字列プログラミングを取り上げます。文字列が文字のリストではない言語もありますが、ここで学ぶ考え方はそのまま通用すると思います。

文字列プログラミングの課題として、『⁠珠玉のプログラミング』（⁠注2）の15章2節に載っている「最長重複文字列」問題を取り上げましょう。これは、読んで字のごとく、最も長く重複している部分文字列を探す問題です。

たとえば、ケネディ大統領の就任演説の中で有名なフレーズで考えてみましょう。

Ask not what your country can do for you,
but what you can do for your country.

このフレーズの最長重複文字列は「can do for you」です。

この問題を取り上げる理由は、問題自体が実践的で興味深く、また問題に適したデータ構造を使うと問題解決が簡単になる例として秀逸だからです。今回、関数プログラミングで解いていきますが、前記の本には命令プログラミングの解法が載っていますから、必要であれば見比べることもできます。

接尾辞リストが問題を解く鍵

みなさんは、この問題をどうやって解くでしょうか？ この問題に初めて出会ったのなら、かなり難しいと思います。

問題を解く鍵となるのは、接尾辞リスト（あるいは接尾辞配列）というデータ構造です。あるリストに対する接尾辞リストとは、そのリストの先頭を順に削っていったリストを要素として持つリストのことです。言葉で説明してもわかりにくいと思いますので、Haskellに接尾辞リストを作らせてみましょう。

Haskellでは、Data.Listモジュールのtailsが接尾辞リストを作る関数です[3]⁠。対話環境でモジュールを読み込むには、:moduleコマンドのあとにモジュール名を入力します。技術的な理由は省きますが、この章のこれ以降、GHCiを起動する際に-XNoMonomorphismRestrictionというオプションを指定してください。

% ghci -XNoMonomorphismRestriction
> :module Data.List

これで、tails関数が使えるようになりました[4]⁠。文字列bananaの接尾辞リストを作ってみましょう。

> tails "banana"
["banana","anana","nana","ana","na","a",""]

先頭が順に削られていった文字列のリストとは何かよくわかると思います。実は、接尾辞リストは永続データであるリストととても相性が良いのです。図4を見てください。文字列bananaのどこもコピーしていないことがわかります。

tails "banana"で作成されたリストにおいて、たとえば"nana"は3番目に現れています。図4で"nana"に対応するのは、上段の左から3番目の四角です。この四角の下向きの矢印は、"nana"というリストを指していますね。

解き方の指針

接尾辞リストが手に入れば、この最長重複文字列問題を解くのはそれほど難しくはありません。解き方の指針を示します。

• 接尾辞リストを作る
• ソートする
• 隣り合う要素を組にする
• 組となっている2つの文字列の共通部分の長さを求める
• 共通部分が一番長い要素を取り出す
• 共通部分のみを残す

この設計を入力の例とともに図示したのが図5です。入力例は"mississippi"であり、答えである出力は"issi"となっています。

また、図5には各部品に対し、これから作る関数の名前と型を書き込んであります。ある部品の出力の型が、次の部品の入力の型と一致していることを確かめておいてください。

接尾辞リストを作る／ソートする

一番目の部品tailsや二番目の部品sortは、Data.Listライブラリで提供されています。sortに文字列のリストが渡された場合は、辞書順に整列します。

隣り合う要素を組にする

次に隣り合う要素を組にする関数makePairを作りましょう。この実装には、常套手段があります。xsが与えられた場合、tail xsとzipを取ればよいのです。

> let makePair xs = zip xs (tail xs)

使ってみましょう。

> makePair ["boo","foo","woo"]
[("boo","foo"),("foo","woo")]

文字列の共通している部分の長さを求める

文字列の共通している部分の長さを求める関数calcLenを作ります。calcLenは、大まかにいうとリストを取ってリストを返すので、要素を変換することになります。

入力のリストが持つ要素は「文字列」と「文字列」の組でした。重複文字列を求めるのですから、この共通部分が欲しいのですが、あとで最も長いものを選び出せるように、共通部分の長さを計算しましょう。また、どちらかの文字列を残しておきましょう。どちらにも同じ共通部分があるので、どちらを残してもかまいませんが、ここでは前者を残すことにします。つまり出力のリストの要素は、「⁠共通部の長さ」と「前者の文字列」の組になります。

共通部分の長さを測る

2つの文字列に対して共通部分の長さを求めるにはどうすればよいでしょうか？ 例として、wordとworldを考えます。リストが2つあるので、常套手段としてzipを取ってみましょう。

> zip "word" "world"
[('w','w'),('o','o'),('r','r'),('d','l')]

この結果を見ると、第一要素と第二要素が等しい組だけ取り出したリストを新たに作り、その長さを測ればよいとわかります。リストの先頭から、ある条件に合致する間、要素を取り出して新たにリストを作るには高階関数takeWhileが使えます。

補助関数として第一要素と第二要素が等しいか調べる関数pairEqを定義します。

> let pairEq (x,y) = x == y

このように、組もパターンとして使えます。pairEqとtakeWhileを使ってみましょう。

> let ret1 = zip "word" "world"
> takeWhile pairEq ret1
[('w','w'),('o','o'),('r','r')]

あとは、このリストの長さを測るだけですから、共通の長さを測る関数comlenは次のように定義できます。リストの長さを測るには前出のlengthが使えます。

> let comlen xs ys = length (takeWhile pairEq
(zip xs ys))

利用例を次に示します。

> comlen "word" "world"
3

関数calcLenを定義する

次に、「⁠文字列」と「文字列」の組を取り、「⁠共通部分の長さ」と「第一要素の文字列」の組を返す関数lenstrを定義します。

> let lenstr (xs,ys) = (comlen xs ys, xs)

使ってみましょう。

> lenstr ("word","world")
(3,"word")

lenstrができてしまえば、あとはこの関数を入力リストにmapするだけです。そこで、calcLenは次のように定義できます。

> let calcLen = map lenstr

共通部分が一番長い要素を取り出す

共通部分が一番長い要素を取り出す関数chooseMaxを定義しましょう。最大値を求めるには、ソートする必要はありません。リストを1回走査すれば、最大値が見つかるはずです。

Haskellでは、リストから最大値を見つける関数maximumByが用意されています。最大値が複数あった場合は、最後の最大値が返ります。maximumByは、第一引数に標準の比較関数compareを使って実装した関数を取ることが想定されています。

今、比較したいのは共通部分の長さ、つまり組の第一要素です。組の第一要素をcompareで比較する関数compFstを次のように定義します。

> let compFst (n1,s1) (n2,s2) = compare n1 n2

このcompFstをmaximumByの第一引数に指定すれば、chooseMaxが完成します。

> let chooseMax = maximumBy compFst

chooseMaxを使ってみましょう。

> chooseMax [(1,"boo"),(3,"foo"),(2,"woo")]
(3,"foo")

一番大きな整数を持つ要素が選ばれました。

共通部分のみを残す

ここまでで、「⁠共通部分の長さ」と「文字列」の組が得られました。最後にすべきことは、文字列から共通部分を切り出すことです。共通部分は、文字列の前方側にあります。リストの先頭にあるN個の要素をリストとして取り出すには、基本関数takeが利用できます。takeを使って、extractを実装してみましょう。

> let extract (i,xs) = take i xs

利用例を次に示します。

> extract (3,"boofoo")
"boo"

まとめる

以上をまとめて最長重複文字列を探す関数maxDupStrを定義しましょう（例外処理は省略しています⁠）⁠。

> let maxDupStr = extract . chooseMax . calcLen .
makePair . sort . tails

使ってみましょう。

> maxDupStr "mississippi"
"issi"

正しく動きました。これをファイルに書き出すと、リスト1のようになります。関数の定義に加えて、関数の型も記述しています。なお、モジュールを読み込むには、importを使います。

import Data.List

--最長重複文字列を計算する
maxDupStr :: [Char] -> [Char]
maxDupStr = extract . chooseMax . calcLen . makePair . sort . tails

--隣り合う要素を組にする
makePair :: [[Char]] -> [([Char], [Char])]
makePair xs = zip xs (tail xs)

--文字列の共通部分の長さを求める
calcLen :: [([Char], [Char])] -> [(Int, [Char])]
calcLen = map lenstr

lenstr :: ([Char],[Char]) -> (Int,[Char])
lenstr (xs,ys) = (comlen xs ys, xs)

comlen :: [Char] -> [Char] -> Int
comlen xs ys = length (takeWhile pairEq (zip xs ys))

pairEq :: (Char,Char) -> Bool
pairEq (x,y) = x == y

--共通部分が一番長い要素を取り出す
chooseMax :: [(Int,[Char])] -> (Int,[Char])
chooseMax = maximumBy compFst

compFst :: (Int,[Char]) -> (Int,[Char]) -> Ordering
compFst (n1,s1) (n2,s2) = compare n1 n2

--共通部分のみを残す
extract :: (Int, [Char]) -> [Char]
extract (i,xs) = take i xs