記事の内容
この記事では、Haskellを使って数学の集合概念を実装します。
Haskell初心者向けの練習として、ちょうどいい題材となることが狙いです。
もしHaskell初心者ならば、プログラムの具体例がたくさん欲しいと思います。
ぜひ、この記事を練習にお役立てください。
集合概念を作るために
集合の厳密な数学的定義は無視します、すみません（笑）
集合概念を表現するために、今回は次のような機能を実装します。
- 集合は重複のないリストとして扱う
- 集合を作る関数
- 重複を取り除くヘルパー関数
- 要素を追加する関数
- 要素を削除する関数
- 和集合
- 共通部分
- 集合の要素数を返す
集合概念を表すために、上記性質の実装で必要十分かどうかは考慮しません。
あくまでも、Haskellの練習の題材としてお使いください。
Haskellのコード
準備
-- 集合を定義するデータ型
-- 集合は重複のないリストとして扱う
module Main where
-- 集合型の定義
newtype Set a = Set [a] deriving (Show)
-- 集合を作る関数（重複を削除）
makeSet :: (Eq a) => [a] -> Set a
makeSet xs = Set (removeDuplicates xs)
-- 重複を取り除くヘルパー関数
removeDuplicates :: (Eq a) => [a] -> [a]
removeDuplicates [] = []
removeDuplicates (x:xs) -- 再帰 により、空リスト [] に到達するまで処理が続く。空リスト [] に到達すると、逆順に結果を構築しながら戻っていく。
| x `elem` xs = removeDuplicates xs
| otherwise = x : removeDuplicates xs
-- 要素を追加する関数
addElement :: (Eq a) => a -> Set a -> Set a
addElement x (Set xs)
| x `elem` xs = Set xs -- すでに存在するならそのまま。
| otherwise = Set (x:xs)
-- 要素を削除する関数
removeElement :: (Eq a) => a -> Set a -> Set a
removeElement _ (Set []) = Set []
removeElement x (Set (y:ys))
| x == y = Set ys
| otherwise = addElement y (removeElement x (Set ys)) -- 先頭の要素 y はそのままにして、再帰結果に再び追加します。削除対象でない要素は順に戻す。
-- 和集合 (Union)
union :: (Eq a) => Set a -> Set a -> Set a
union (Set xs) (Set ys) = makeSet (xs ++ ys)
-- 共通部分 (Intersection)
intersection :: (Eq a) => Set a -> Set a -> Set a
intersection (Set xs) (Set ys) = makeSet [x | x <- xs, x `elem` ys] -- x が ys に含まれているならリストに残す。
-- 集合の要素数を返す
setSize :: Set a -> Int
setSize (Set xs) = length xs
実行例
-- メイン関数
main :: IO ()
main = do
let set1 = makeSet [1, 2, 3, 4]
let set2 = makeSet [3, 4, 5, 6]
putStrLn "Set 1:"
print set1
putStrLn "Set 2:"
print set2
-- 和集合
let setUnion = union set1 set2
putStrLn "\nUnion of Set 1 and Set 2:"
print setUnion
-- 共通部分
let setIntersection = intersection set1 set2
putStrLn "\nIntersection of Set 1 and Set 2:"
print setIntersection
-- 要素の追加
let set3 = addElement 7 set1
putStrLn "\nSet 1 after adding element 7:"
print set3
-- 要素の削除
let set4 = removeElement 2 set1
putStrLn "\nSet 1 after removing element 2:"
print set4
-- 集合のサイズ
putStrLn "\nSize of Set 1:"
print (setSize set1)
再帰の練習をしましょう
Haskellの初心者ならば、再帰という考え方に慣れる必要があります。
今回のコードにも再帰が含まれます。
ちょうどいい練習になると思うので、コードに含まれるある関数の定義を詳しく分析してみましょう。
要素を削除する関数removeElementの定義を丁寧に解説します。
removeElement x (Set (y:ys))
| x == y = Set ys
| otherwise = addElement y (removeElement x (Set ys))
x と y が違うなら、y を保持しつつ、残りの ys を再帰的に処理します。
removeElement x (Set ys)を計算し、その結果に y を追加するという流れになります。
具体的な計算手順を一歩ずつ追ってみましょう。
例
removeElement 3 (Set [1,2,3,4])
処理の流れを追いましょう。
removeElement 3 (Set [1,2,3,4])
1 ≠ 3 → 再帰呼び出し
removeElement 3 (Set [2,3,4])
2 ≠ 3 → 再帰呼び出し
removeElement 3 (Set [3,4])
3 == 3 (一致！)
Set [4] を返す
addElement 2 (Set [4])
→ Set [2,4]
addElement 1 (Set [2,4])
→ Set [1,2,4]
最終結果 Set [1,2,4]
丁寧に処理の流れを追ってみてください！
再帰の流れが実感できるはずです。
関連記事
「状態の変化」が禁止されている言語でどうやって繰り返し処理するの？【Haskellと再帰関数】
Haskell入門 典型的な再帰関数の練習
Haskell初心者は絶対に意識したい【文字列とリスト】 ( ' ) と ( " ) の違い