Qiita Conference 2025

Qiita史上最多!豪華12名のゲストが登壇

特別講演ゲスト(敬称略)

ymrl、成瀬允宣、鹿野壮、伊藤淳一、uhyo、徳丸浩、ミノ駆動、みのるん、桜庭洋之、tenntenn、けんちょん、こにふぁー

0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

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

Last updated at Posted at 2025-03-19

記事の内容

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

0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up

Qiita Conference 2025 will be held!: 4/23(wed) - 4/25(Fri)

Qiita Conference is the largest tech conference in Qiita!

Keynote Speaker

ymrl、Masanobu Naruse, Takeshi Kano, Junichi Ito, uhyo, Hiroshi Tokumaru, MinoDriven, Minorun, Hiroyuki Sakuraba, tenntenn, drken, konifar

View event details
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?