M.Hiroi's Home Page

お気楽 F# プログラミング超入門

集合 (Set)


Copyright (C) 2022 Makoto Hiroi
All rights reserved.

はじめに

「集合 (Set)」はいくつかの要素を集めたものです。一般に、集合は重複した要素を含まず、要素の順番に意味はありません。なお、要素の重複を許す集合は「多重集合 (multi set)」と呼ばれます。たとえば、集合 {1, 3, 5, 7} は {7, 5, 3, 1} や {5, 3, 1, 7} と表すこともできます。このように、要素は適当に並べてもかまわないのですが、ある規則で要素を整列させておく場合もあります。

F# の場合、標準ライブラリに平衡二分木をベースにした集合 Set<'a> が用意されています。関数型言語らしく Set は immutable なデータ構造です。また、.NET の標準ライブラリ System.Collections.Generic にも集合を表すクラス HashSet<'a> があるので、それを利用することもできます。HashSet はハッシュ法を使った高速で mutable なデータ構造です。今回は Set と HashSet の基本的な使い方について簡単に説明します。

●集合の基本的な操作メソッド

集合はコンストラクタ Set で生成します。 

Set(sequence) => set

引数 sequence は集合の要素を格納したシーケンスです。リストや一次元配列でもかまいません。集合を生成するとき、重複要素は削除されます。なお、要素となる型は制約 comparison を満たす必要があります。

簡単な例を示しましょう。 

> let a = Set(seq {1..8});;
val a: Set<int> = set [1; 2; 3; 4; 5; 6; 7; 8]

> let b = Set(seq {"foo"; "bar"; "baz"});;
val b: Set<string> = set ["bar"; "baz"; "foo"]

要素の有無はメソッド Contains で調べることができます。 

set.Contains(item) => bool

> a.Contains(5);;
val it: bool = true

> a.Contains(50);;
val it: bool = false

> b.Contains("foo");;
val it: bool = true

> b.Contains("Foo");;
val it: bool = false

集合に新しい要素 item を追加するにはメソッド Add を使います。集合に item と同じ要素がある場合、item は追加されません。集合から要素 item を削除するにはメソッド Remove を使います。item が見つからない場合、何もしないで集合を返します。 

set.Add(item) => new_set
set.Remove(item) => new_set

> a.Add(9);;
val it: Set<int> = set [1; 2; 3; 4; 5; 6; 7; 8; 9]

> a;;
val it: Set<int> = set [1; 2; 3; 4; 5; 6; 7; 8]

> a.Add(5);;
val it: Set<int> = set [1; 2; 3; 4; 5; 6; 7; 8]

> b.Add("oops");;
val it: Set<string> = set ["bar"; "baz"; "foo"; "oops"]

> b;;
val it: Set<string> = set ["bar"; "baz"; "foo"]

> b.Add("baz");;
val it: Set<string> = set ["bar"; "baz"; "foo"]

> a.Remove(5);;
val it: Set<int> = set [1; 2; 3; 4; 6; 7; 8]

> a;;
val it: Set<int> = set [1; 2; 3; 4; 5; 6; 7; 8]

> a.Remove(50);;
val it: Set<int> = set [1; 2; 3; 4; 5; 6; 7; 8]

> b.Remove("foo");;
val it: Set<string> = set ["bar"; "baz"]

> b;;
val it: Set<string> = set ["bar"; "baz"; "foo"]

> b.Remove("Foo");;
val it: Set<string> = set ["bar"; "baz"; "foo"]

Add と Remove は新しいマップを返すことに注意してください。

●プロパティ

プロパティ IsEmpty は集合が空であれば真となります。Count は集合に格納されたデータ数を表します。 

> a.Count;;
val it: int = 8

> a.IsEmpty;;
val it: bool = false

> b.Count;;
val it: int = 3

> b.IsEmpty;;
val it: bool = false

Set は二分木をベースにしているので、最小値と最大値を簡単に求めることができます。 

set.MaximumElement => max_item
set.MinimumElement => min_item

> a.MaximumElement;;
val it: int = 8

> a.MinimumElement;;
val it: int = 1

> b.MaximumElement;;
val it: string = "foo"

> b.MinimumElement;;
val it: string = "bar"

●集合演算

和集合は演算子 + で、差集合は演算子 - で求めることができます。 

> let x = Set([1;2;3;4]);;
val x: Set<int> = set [1; 2; 3; 4]

> let y = Set([3;4;5;6]);;
val y: Set<int> = set [3; 4; 5; 6]

> x + y;;
val it: Set<int> = set [1; 2; 3; 4; 5; 6]

> x - y;;
val it: Set<int> = set [1; 2]

> y - x;;
val it: Set<int> = set [5; 6]

部分集合の判定は以下のメソッドを使います。 

set.IsSubsetOf(that) => bool
set.IsSupersetOf(that) => bool

IsSubsetof は this が that の部分集合であれば真を返します。逆に IsSupersetof は that が this の部分集合であれば真を返します。 

> a;;
val it: Set<int> = set [1; 2; 3; 4]

> Set([1;2;3;4;5]) |> a.IsSubsetOf;;
val it: bool = true

> Set([1;2;3;4]) |> a.IsSubsetOf;;
val it: bool = true

> Set([1;2;3]) |> a.IsSubsetOf;;
val it: bool = false

> Set([1;2;3]) |> a.IsSupersetOf;;
val it: bool = true

> Set([1;2;3;4]) |> a.IsSupersetOf;;
val it: bool = true

> Set([1;2;3;4;5]) |> a.IsSupersetOf;;
val it: bool = false

●モジュール Set の操作関数

Set.empty => empty_set
Set.isEmpty set => bool
Set.count set => int
Set.add item set => new_set
Set.remove item set => new_set
Set.contains item set => bool
Set.maxElement set => max_item
Set.minElement set => min_item
Set.difference set1 set2 => new_set
Set.union set1 set2 => new_set
Set.intersect set1 set2 => new_set
Set.isSubset set1 set2 => bool
Set.isSuperset Set1 set2 => bool

この他にも、集合を操作する関数がモジュール Set に用意されています。メソッドに対応する関数を示します。intersect はメソッドにはありませんが積集合を求める関数です。

●高階関数

Set には集合用の高階関数が用意されています。 

> Set.map;;
val it:
  (('a -> 'b) -> Set<'a> -> Set<'b>) when 'a: comparison and 'b: comparison

> Set.filter;;
val it: (('a -> bool) -> Set<'a> -> Set<'a>) when 'a: comparison

> Set.fold;;
val it: (('a -> 'b -> 'a) -> 'a -> Set<'b> -> 'a) when 'b: comparison

> Set.foldBack;;
val it: (('a -> 'b -> 'b) -> Set<'a> -> 'b -> 'b) when 'a: comparison

> Set.iter;;
val it: (('a -> unit) -> Set<'a> -> unit) when 'a: comparison

map, filter, fold, foldBack, iter は今までに説明した高階関数の集合バージョンです。簡単な使用例を示しましょう。 

> let a = Set([1..8]);;
val a: Set<int> = set [1; 2; 3; 4; 5; 6; 7; 8]

> Set.iter (fun x -> printf "%d " x) a;;
1 2 3 4 5 6 7 8 val it: unit = ()

> Set.map (fun x -> x * x) a;;
val it: Set<int> = set [1; 4; 9; 16; 25; 36; 49; 64]

> Set.filter (fun x -> x % 2 = 0) a;;
val it: Set<int> = set [2; 4; 6; 8]

> Set.fold (+) 0 a;;
val it: int = 36

> Set.foldBack (fun x a -> x :: a) a [];;
val it: int list = [1; 2; 3; 4; 5; 6; 7; 8]

●検査

述語 pred を満たす要素があるか調べるには Set.exists を使います。Set.forall はすべての要素が pred を満たせば真を返します。 

Set.exists pred table => bool
Set.forall pred table => bool

> Set.exists (fun x -> x = 5) a;;
val it: bool = true

> Set.exists (fun x -> x > 9) a;;
val it: bool = false

> Set.forall (fun x -> x % 2 <> 0) a;;
val it: bool = false

> Set.forall (fun x -> x > 0) a;;
val it: bool = true

●集合の変換

Set には集合をリスト、配列、シーケンスに変換する関数や、その逆関数が用意されています。 

> Set.toList;;
val it: (Set<'a> -> 'a list) when 'a: comparison

> Set.toArray;;
val it: (Set<'a> -> 'a[]) when 'a: comparison

> Set.toSeq;;
val it: (Set<'a> -> seq<'a>) when 'a: comparison

> Set.ofList;;
val it: ('a list -> Set<'a>) when 'a: comparison

> Set.ofArray;;
val it: ('a[] -> Set<'a>) when 'a: comparison

> Set.ofSeq;;
val it: (seq<'a> -> Set<'a>) when 'a: comparison

簡単な使用例を示しましょう。 

> a;;
val it: Set<int> = set [1; 2; 3; 4; 5; 6; 7; 8]

> Set.toList a;;
val it: int list = [1; 2; 3; 4; 5; 6; 7; 8]

> Set.toArray a;;
val it: int[] = [|1; 2; 3; 4; 5; 6; 7; 8|]

> Set.toSeq a;;
val it: seq<int> = set [1; 2; 3; 4; 5; 6; 7; 8]

> Set.ofList [5;4;3;2;1];;
val it: Set<int> = set [1; 2; 3; 4; 5]

> Set.ofArray [|5;4;3;2;1|];;
val it: Set<int> = set [1; 2; 3; 4; 5]

> Set.ofSeq (seq {5;4;3;2;1});;
val it: Set<int> = set [1; 2; 3; 4; 5]

このほかにも Set には便利な関数が用意されています。詳細は F# のリファレンス Set Module をお読みください。

●HashSet

次は HashSet について説明します。クラス HashSet<'a> は .NET のライブラリ System.Collections.Generic にあります。F# から利用する場合は型略称を使うとよいでしょう。 

> type hset<'a> = System.Collections.Generic.HashSet<'a>;;
type hset<'a> = System.Collections.Generic.HashSet<'a>

本ページでは HashSet の別名として hset を使うことにします。

辞書はコンストラクタ HashSet で生成します。 

HashSet<'a>() => empty_set
HashSet(sequene) => set

sequence はリストや一次元配列でもかまいません。型略称を使うと、次のようになります。 

> let a = hset<int>();;
val a: hset<int>

> a;;
val it: hset<int> = seq []

> a.Count;;
val it: int = 0

> let b = hset<int>(seq {1..10});;
val b: hset<int>

> b;;
val it: hset<int> = seq [1; 2; 3; 4; ...]

> b.Count;;
val it: int = 10

集合の要素数はプロパティ Count で求めることができます。

●要素の追加と削除

要素はメソッド Add で追加し、メソッド Remove で削除することができます。 

set.Add(item) => bool
set.Remove(item) => bool

成功した場合は true を失敗した場合は false を返します。HashSet は mutable なデータ構造なので、集合の内容が破壊的に修正されることに注意してください。 

> let a = hset<int>();;
val a: hset<int>

> a;;
val it: hset<int> = seq []

> a.Add(5);;
val it: bool = true

> a;;
val it: hset<int> = seq [5]

> a.Add(5);;
val it: bool = false

> a.Add(1);;
val it: bool = true

> a;;
val it: hset<int> = seq [5; 1]

> a.Remove(1);;
val it: bool = true

> a;;
val it: hset<int> = seq [5]

> a.Remove(1);;
val it: bool = false

> a;;
val it: hset<int> = seq [5]

RemoveWhere は述語 pred を満たす要素を削除します。返り値は削除した要素数です。 

set.RemoveWhere(pred) => int

> b;;
val it: hset<int> = seq [1; 2; 3; 4; ...]

> b.RemoveWhere(fun x -> x % 2 = 0);;
val it: int = 5

> b;;
val it: hset<int> = seq [1; 3; 5; 7; ...]

メソッド Clear は集合を空にします。 

> a;;
val it: hset<int> = seq [5]

> a.Clear();;
val it: unit = ()

> a;;
val it: hset<int> = seq []

●検査

要素の有無はメソッド Contains で調べることができます。 

set.Contains(item) => bool

> let b = hset<int>(seq {1..10});;
val b: hset<int>

> b;;
val it: hset<int> = seq [1; 2; 3; 4; ...]

> b.Contains(1);;
val it: bool = true

> b.Contains(5);;
val it: bool = true

> b.Contains(10);;
val it: bool = true

> b.Contains(15);;
val it: bool = false

●集合演算

HashSet は sequence と集合演算を行うことができます。 

set.ExceptWith(sequence) => unit
set.IntersectWith(sequence) => unit
set.UnionWith(sequence) => unit
set.IsSubsetOf(sequence) => bool
set.IsSupersetOf(sequence) => bool

メソッド ExceptWith は set と sequence の差集合を求めます。メソッド IntersectWith は set と sequence の積集合を求めます。メソッド UnionWtih は set と sequence の和集合を求めます。メソッドIsSubsetOf は set が sequence の部分集合であれば真を返します。逆に、メソッド IsSupersetOf は sequence が set の部分集合であれば真を返します。 

> let a = hset([1;2;3;4]);;
val a: hset<int>

> a;;
val it: hset<int> = seq [1; 2; 3; 4]

> a.UnionWith([3;4;5;6]);;
val it: unit = ()

> a;;
val it: hset<int> = seq [1; 2; 3; 4; ...]

> for x in a do printfn "%d " x;;
1
2
3
4
5
6
val it: unit = ()

> let a = hset([1;2;3;4]);;
val a: hset<int>

> a.IntersectWith([3;4;5;6]);;
val it: unit = ()

> a;;
val it: hset<int> = seq [3; 4]

> let a = hset([1;2;3;4]);;
val a: hset<int>

> a.ExceptWith([3;4;5;6]);;
val it: unit = ()

> a;;
val it: hset<int> = seq [1; 2]

> hset([1..4]).IsSubsetOf([1..5]);;
val it: bool = true

> hset([1..4]).IsSubsetOf([1..3]);;
val it: bool = false

> hset([1..4]).IsSupersetOf([1..5]);;
val it: bool = false

> hset([1..4]).IsSupersetOf([1..3]);;
val it: bool = true

このほかにもクラス HashSet<'a> には便利なメソッドが用意されています。詳細は .NET のリファレンス HashSet<T> クラス をお読みくださいませ。

初版 2022 年 5 月 21 日