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_ _)o~†
7. Data.Set を利用する
集合の操作をしたいなら、Data.Set モジュールを利用する。
リストと集合の変換は、
共通部分 と 差 は、
それぞれ型を見ると、集合の要素が 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 使った方が楽かな。
0コメント:
コメントを投稿