前回のエントリー微妙に揺れのある２つの文字列リストに対する積集合(Intersection)と差集合(difference)の計算 の Haskell 編です。
積集合と差集合とか書いて・・・途中で気づいたのですが、２つの集合の差だけを求めれば済む話だった。 Haskell 編では差だけを求めます。
前回同様ですが、 微妙に揺れのある次のような 二つの文字列リスト（画像ファイル名）があるとする。
listA = ["grape.pdf", "apple_v1.pdf", "apple_v2.pdf", "lemon_v1.pdf", "peach_v2.pdf"]
listB = ["grape.png", "lemon.png", "strawberry.png"]
このリストの差の計算について考えます。
いきなり揺れのあるデータではなく、簡単なデータからはじめます。 つまりこのような二つのリスト:
listA = ["grape.png", "apple.png", "lemon.png", "peach.png"]
listB = ["grape.png", "lemon.png", "strawberry.png"]
この 差 listA - listB を考えます。
$ stack new diff
$ cd diff
app/Main.hs に次のコードに書き換えます。
module Main where
--import Lib
listA = ["grape.png", "apple.png", "lemon.png", "peach.png"]
listB = ["grape.png", "lemon.png", "strawberry.png"]
result :: [String]
result = listA - listB
main :: IO ()
main = print $ result
実行してみましょう。たぶんエラーだけど。
$ stack run
いろいろエラーメッセージ
やっぱり無理か。
Groovy ならこれで差が計算できるのに。
def listA = ["grape.png", "apple.png", "lemon.png", "peach.png"]
def listB = ["grape.png", "lemon.png", "strawberry.png"]
println (listA - listB)
実行。
$ groovy diff.groovy
[apple.png, peach.png]
ほらね。
Haskell に戻りましょう。 もしかして、文字列リストの差をとる関数があるかもしれないのですが、 ここでは difference 関数を定義して filter を使って差を計算します。
difference :: [String] -> [String] -> [String]
difference list0 list1 = filter (\item -> not $ elem item list1) list0
result :: [String]
result = difference listA listB
これで実行してみる。
$ stack run
["apple.png","peach.png"]
バッククォートを使うと中置演算子になるので、このように書くことができる。
--result = difference listA listB
result = listA `difference` listB
listA - listB 的な表現に近づいたものの、たいしてうれしくもない。
それでは本題の２つのリストの差に挑戦します。
listA = ["grape.pdf", "apple_v1.pdf", "apple_v2.pdf", "lemon_v1.pdf", "peach_v2.pdf"]
listB = ["grape.png", "lemon.png", "strawberry.png"]
_v1 や _v2 があったりなかったり、そして拡張子が pdf から png に変化するのは無視してリストの差を求めたいので、 この文字列の等価性の評価を独自ルールにすればよい。 独自ルールにするには、String の型のままでは不都合なので(Eq 型クラスの実装が既存の型に対しては上書き実装できないから)、次のように Item という型を作成して、Show と Eq を独自に定義します。
src/Lib.hs
module Lib
( Item(Item)
) where
import Text.Regex.Posix
data Item = Item String
itemName :: Item -> String
itemName (Item v) = v
instance Show Item where
show it = itemName it
roundItemName :: Item -> String
roundItemName item = round (itemName item)
where
round :: String -> String
round itemName = head $ tail $ head $ itemName =~ "([a-z]+)(_v[0-9])?\\.(pdf|png)"
instance Eq Item where
(==) itemA itemB = (roundItemName itemA)==(roundItemName itemB)
ポイントは Item に対して Eq を定義しているところ:
instance Eq Item where
(==) itemA itemB = (roundItemName itemA)==(roundItemName itemB)
アイテム名そのものではなく、丸めた名前を使って等価性の評価を行うように変更。 この丸めた名前を作り出す roundItemName 関数で、_v1, _v2 や拡張子を除去している。
この部分で正規表現を使って文字列の丸め処理をしているがその話は別のエントリーを書く予定。
正規表現を使うために Text.Regex.Posix を使うので package.yml の dependencies に regex-posix を追記。
dependencies:
- base >= 4.7 && < 5
- regex-posix
もしかすると 事前に stack install regex-posix しておく必要があったかも。
この Item 型を使うように app/Main.hs も書き換えます。
import Lib
listA = ["grape.pdf", "apple_v1.pdf", "apple_v2.pdf", "lemon_v1.pdf", "peach_v2.pdf"]
listB = ["grape.png", "lemon.png", "strawberry.png"]
itemListA :: [Item]
itemListA = toItems listA
itemListB :: [Item]
itemListB = toItems listB
toItems :: [String] -> [Item]
toItems xs = map (\s -> Item s) xs
Lib をインポートして、 listA, listB の各要素を文字列から Item に変えて itemListA, itemListB をつくります。
今度は、この itemListA と itemListB の差を計算します。 そのために、 difference, result 関数を Item に対応させます。
difference :: [Item] -> [Item] -> [Item]
difference list0 list1 = filter (\item -> not $ elem item list1) list0
result :: [Item]
result = itemListA `difference` itemListB
実行します。
$ stack run
[apple_v1.pdf,apple_v2.pdf,peach_v2.pdf]
できました。
前回 JavaScript で実装したのと同じ発想で実装できました。 Haskell は等価性の評価ルールを Eq 型クラスを使って定義できるしくみがあるので、そこは JavaScript 実装よりコードの意図が明確になり、わかりやすい。
最後に app/Main.hs 全体を載せます。
module Main where
import Lib
listA = ["grape.pdf", "apple_v1.pdf", "apple_v2.pdf", "lemon_v1.pdf", "peach_v2.pdf"]
listB = ["grape.png", "lemon.png", "strawberry.png"]
itemListA :: [Item]
itemListA = toItems listA
itemListB :: [Item]
itemListB = toItems listB
toItems :: [String] -> [Item]
toItems xs = map (\s -> Item s) xs
difference :: [Item] -> [Item] -> [Item]
difference list0 list1 = filter (\item -> not $ elem item list1) list0
result :: [Item]
result = itemListA `difference` itemListB
main :: IO ()
main = print $ result