[入門]関数プログラミング―質の高いコードをすばやく直感的に書ける!

第3章 リストと文字列―最長重複文字列問題で知るリストプログラミング

この記事を読むのに必要な時間:およそ 5.5 分

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

共通部分が一番長い要素を取り出す関数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を使います。

リスト1 maxDupStr.hs

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

COLUMN お勧め入門書紹介

『Scheme手習い』注a

関数プログラミングに不可欠な「再帰」を学ぶための本です。質問と答えが対話的に列挙された形式になっており,どんどん読み進めていけます。

ただ,技術的な背景の解説はないので,それぞれの章の目的がわからないまま読み進めてしまう恐れがあります。ぜひ何回も読み返して,自分で目的を考えてみてください。

この本を読んで「人生が変わった」という人を何人か知っています。それは,問題を再帰的に考えられるようになるからです。

なお,続編の『Scheme修行』注bでは,関数型風にも命令型風にも書けるSchemeの命令プログラミングとしての側面が解説されています。

『プログラミングHaskell』注c

限定されたHaskellの構文を用いた関数プログラミングの入門書です。関数プログラミングのエッセンスが凝縮されています。章末の例題を解いたり,付録の基本関数を眺めれば,関数プログラミングの考え方が身につくでしょう。

大学での長年の講義資料がもとになっているため,扱われている例題がクールです。たとえば,短いコードで暗号を解読したり,4つの数から10を作る切符番号問題を最適化したりします。

この本の原書は,筆者のプログラミング人生を根底から変えました。翻訳する機会を得られたことに感謝しています。

この本を読んでもHaskellの細かい文法は習得できません。そこでさらにHaskellを学ぶのであれば,"Learn You a Haskell for Great Good!"注dの訳である『すごいHaskellたのしく学ぼう!』注eもお勧めします。2012年5月ごろに発売される予定です。

『プログラミングの基礎』注f

OCamlを用いたプログラミングの入門書です。もちろん関数プログラミングに重点が置かれていますが,破壊的な代入のあるOCamlの特徴を活かして,副作用を持つ関数を適切に実装する方法も解説されています。

この本も大学での講義資料がもとになっており,例題が洗練されています。この本は,全体を通じて「メトロネットワークの最短路問題」を解いていきます。本の前半で問題が解け,後半では最適化していきます。

たとえばCしか使わないプログラマにも,ぜひ読んでいただきたい本です。

『Scalaスケーラブルプログラミング第2版』注g

Scalaの開発者が書いたScalaの入門です。Scalaは仕様が大きいので本も分厚いですが,各章は短いので案外スラスラ読めます。

Scalaでは,プログラムを命令的にも関数的にも記述できます。両方の選択肢がある場合,この本では関数的な記述を勧めています。そうすれば,コンパイル時にエラーをたくさん発見できますし,マルチコアと相性が良くなるからです。

関数プログラミングに興味のあるJavaプログラマに,この本をお勧めします。ただ,関数プログラミングの知識を深めるには,ほかの本と併読すべきです。

注a)
Daniel P. Friedman and Matthias Felleisen著,元吉文男/横山晶一訳,オーム社,2010年
注b)
Daniel P. Friedman and Matthias Felleisen著,元吉文男/横山晶一訳,オーム社,2011年
注c)
Graham Hutton著,山本和彦訳,オーム社,2009年
注d)
Miran Lipovača著,2011年
注e)
田中英行,村主崇行訳,オーム社。書名や発売日などは現時点のもので,変更になる可能性があります。
注f)
浅井健一著,サイエンス社,2007年
注g)
Martin Odersky,Lex Spoon,Bill Venners著,長尾高弘訳,羽生田栄一監修,水島宏太特別寄稿,インプレスジャパン,2011年

著者プロフィール

山本和彦(やまもとかずひこ)

株式会社IIJイノベーションインスティテュート(IIJ-II)技術研究所 主幹研究員。

開発した代表的なオープンソフトにMew,Firemacs,Mightyがある。『プログラミングHaskell』や『Haskellによる並列・並行プログラミング』の翻訳者。職場ではHaskell,家庭では3人の子供と格闘する日々を送っている。

web:http://www.mew.org/~kazu/

twitter:@kazu_yamamoto