【Haskellで遊びたい初心者へ】数学の「集合」概念を実装してみた

## 記事の内容
この記事では、Haskellを使って数学の集合概念を実装します。
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
```

### 実行例
```Haskell
-- メイン関数
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)
```

https://github.com/meta77/Haskell-Set.git

## 再帰の練習をしましょう
Haskellの初心者ならば、再帰という考え方に慣れる必要があります。
今回のコードにも再帰が含まれます。
ちょうどいい練習になると思うので、コードに含まれるある関数の定義を詳しく分析してみましょう。

要素を削除する関数`removeElement`の定義を丁寧に解説します。

```Haskell
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と再帰関数】](https://qiita.com/kyogoku_meta/items/6d6bbbc3abc4b7bd8338)
[Haskell入門　典型的な再帰関数の練習](https://qiita.com/kyogoku_meta/items/ca77a4ae782875d5be91)
[Haskell初心者は絶対に意識したい【文字列とリスト】 ( ' ) と ( " ) の違い](https://qiita.com/kyogoku_meta/items/55d14f38fab99da20d25)