記事の内容

この記事では、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初心者は絶対に意識したい【文字列とリスト】 ( ' ) と ( " ) の違い