共通部分が一番長い要素を取り出す
共通部分が一番長い要素を取り出す関数chooseMaxを定義しましょう。最大値を求めるには,
Haskellでは,
今,
> let compFst (n1,s1) (n2,s2) = compare n1 n2
このcompFstをmaximumByの第一引数に指定すれば,
> let chooseMax = maximumBy compFst
chooseMaxを使ってみましょう。
> chooseMax [(1,"boo"),(3,"foo"),(2,"woo")]
(3,"foo")
一番大きな整数を持つ要素が選ばれました。
共通部分のみを残す
ここまでで,
> let extract (i,xs) = take i xs
利用例を次に示します。
> extract (3,"boofoo")
"boo"
まとめる
以上をまとめて最長重複文字列を探す関数maxDupStrを定義しましょう
> let maxDupStr = extract . chooseMax . calcLen .
makePair . sort . tails
使ってみましょう。
> maxDupStr "mississippi"
"issi"
正しく動きました。これをファイルに書き出すと,
リスト1 maxDupStr.
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)
関数プログラミングに不可欠な
ただ,
この本を読んで
なお,
『プログラミングHaskell』(注c)
限定されたHaskellの構文を用いた関数プログラミングの入門書です。関数プログラミングのエッセンスが凝縮されています。章末の例題を解いたり,
大学での長年の講義資料がもとになっているため,
この本の原書は,
この本を読んでもHaskellの細かい文法は習得できません。そこでさらにHaskellを学ぶのであれば,
『プログラミングの基礎』(注f)
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年