Haskell でリストから特定の要素を抽出する - 再帰的な定義、末尾再帰、filter, elem, partition, intersect

1. リストから特定の要素を抽出したい

例えば、ある村に、村人が 5 人住んでいたとする。

太郎、花子、次郎、三郎、明美

この村には、指名手配されている犯人がいる。指名手配されている犯人のリストは、以下の通り。

花子、三郎、四郎

これより、村にいる犯人を見つけたい。

2. 型の定義と、関数の型

最初に、「人」を表す Person 型を定義する。ここでは名前が一致することで、同じ人であるとする。

data Person = P { name :: String } deriving (Show, Eq)

村人のリストを定義。

ps = [P "Tarou", P "Hanako", P "Jiro", P "Saburou", P "Akemi"]

「指名手配されている犯人のリスト」と、「村人のリスト」が与えられたら、一致した人を、リストで返す関数を extract とする。関数の型は次の通り。

extract :: [Person] -> [Person] -> [Person]

3. filter 関数を使い、再帰的に定義

Haskell でリストから抽出するには、filter 関数を利用する。

具体的な処理のイメージは、

「指名手配されている犯人のリスト」から、一人ずつ取り出して、
「村人のリスト」と照合し、
一致するものがあれば返す。

リストの要素を順に見ていく処理は、再帰的な定義をする。

最初にパターンマッチにより、指名手配されている犯人のリストを、「先頭の要素」と「それよりも後ろの要素」に分解。
犯人リストの「先頭の要素」と、村人の「先頭の要素」が一致するか調べる。

extract (x:xs) ps = filter (== x) ps …

「先頭よりも後ろの要素」に対して、同じように一致しているか調べる。その結果を、上記の結果と結合して返す。

extract (x:xs) ps = filter (== x) ps ++ extract xs ps

ところで、指名手配されている犯人のリストを、パターンマッチで分解している。そのため、リストを分解しつくし、空リストになった場合を考える必要がある。よって、「指名手配のリストが空なら、一致する人はいない」という定義を加える。

extract []     _  = []

全体を示すと、

extract []     _  = []
extract (x:xs) ps = filter (== x) ps ++ extract xs ps

このような再帰的な定義の仕方を考えると、頭が混乱する。最近、少し慣れてきたかも。

4. 末尾再帰呼出しで定義

再帰的に定義できたので、「末尾再帰呼出し」の形に定義を変えてみる。

末尾再帰呼出しの形にするには、次の二つのことが必要。

結果を累積的に保持する役割を持つ引数を追加。
処理の最後で自分自身を呼出す。

最初に、結果を累積的に保持するための引数を、第 2 引数に置く。

extract' (x:xs) acc ps =

次に、いきなり自分自身を呼出す。

extract' (x:xs) acc ps = extract' …

最初は acc が空だとして、「指名手配されている犯人のリストの先頭要素で、抽出できるか」試す。

extract' (x:xs) acc ps = extract' … (filter (== x) ps) …

filter 関数で抽出した結果を acc に加える。

extract' (x:xs) acc ps = extract' … (acc ++ (filter (== x) ps)) …

指名手配されている犯人のリストの残りも、同じように処理すればいいので、引数 acc に追加した結果を、引数に与えて再帰的な呼出しをする。

extract' (x:xs) acc ps = extract' xs (acc ++ (filter (== x) ps)) ps

ただし、先ほどと同じく、パターンマッチで指名手配されている犯人のリストを分解している。そのため、これが空になった場合についても考えなければいけない。

引数 acc に結果が詰め込まれるはずなので、それをそのまま返す。

extract' []     acc _  = acc

全体を示す。

extract' []     acc _  = acc
extract' (x:xs) acc ps = extract' xs (acc ++ (filter (== x) ps)) ps

関数をラップ

上記で定義した関数を使うには、引数 acc に空リストを与える。

extract' [P "Hanako", P "Saburou", P "Sirou"] [] ps

しかし、毎回、空リストを渡すのは面倒なので、extract’ 関数をラップする関数を定義する。

extract xs ps = extract' xs [] ps
    where
      extract' []     acc _  = acc
      extract' (x:xs) acc ps = extract' xs (acc ++ (filter (== x) ps)) ps

これで関数のインターフェイスが、最初に定義した関数と同じになった。

末尾再帰呼出すメリットを簡単に言えば、再帰的な関数の呼出しが深くなり過ぎ、スタックオーバーフローしてしまったら、末尾再帰呼出しの形にして正格評価で対処できること。

5. 各々の要素が「特定のリストに含まれるか？」検査する方法

「リストの中にある要素が存在するかどうか？」というと、Python のシーケンス型における `in’ を連想する。

print "Hanako" in ["Tarou", "Hanako", "Jiro"]      #=> True
print "Hanako" not in ["Tarou", "Hanako", "Jiro"]  #=> False

Haskell では elem, notElem 関数に相当する。

*Main> "Hanako" `elem` ["Tarou", "Hanako", "Jiro"]
True
*Main> "Hanako" `notElem` ["Tarou", "Hanako", "Jiro"]
False

問題に戻り、先ほどまでの定義を、

各々の村人を「指名手配されている犯人のリスト」から抽出できるか？

に変更。

extract xs ps = filter (\x -> x `elem` xs) ps

部分適用、セクションを利用すると、

extract xs = filter (`elem` xs)

抽出ではなく、リストを分割したい場合

抽出ではなく、村人を指名手配されている犯人と、そうでない人に分割したい場合は、Data.List の partition を使う。

import Data.List

extract xs = partition (`elem` xs)

6. 共通部分を抽出する方法

村人の集合と指名手配されている人の集合を図に描くと、求めたいのは二つの集合の共通部分ということになる。

Data.List には集合的な操作として intersect が定義されている。

import Data.List

extract = intersect

つまり、わざわざ自分で関数を定義する必要はなかった。

なぜこれをすぐに連想しなかったのだろう … パタッ(o_ _)ｏ~†

7. Data.Set を利用する

集合の操作をしたいなら、Data.Set モジュールを利用する。

リストと集合の変換は、

fromList <=> toList

共通部分と差は、

それぞれ型を見ると、集合の要素が Ord のインスタンスできないといけない。そのため、Person 型に Ord を追加。

import Data.Set

data Person = P { name :: String } deriving (Show, Eq, Ord)

extract xs ps = toList $ xs' `intersection` ps'
    where
      xs' = fromList xs
      ps' = fromList ps

先ほどと同じように、リストを分割したいなら、

extract xs ps = ( toList $ xs' `intersection` ps', 
                  toList $ ps' `difference`   xs' )
    where
      xs' = fromList xs
      ps' = fromList ps

「要素に重複があってはならない」という制約がない限り、partition 使った方が楽かな。

すぐに忘れる脳みそのためのメモ

2010年2月2日火曜日