Home About
Haskell , set-theory

微妙に揺れのある2つの文字列リストの差(difference)の計算 Haskell 編

前回のエントリー微妙に揺れのある2つの文字列リストに対する積集合(Intersection)と差集合(difference)の計算 の Haskell 編です。

積集合と差集合とか書いて・・・途中で気づいたのですが、2つの集合の差だけを求めれば済む話だった。 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 的な表現に近づいたものの、たいしてうれしくもない。

揺れのある表記を含んだ文字列に挑戦

それでは本題の2つのリストの差に挑戦します。

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