M.Hiroi's Home Page

F# Programming

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

[ PrevPage | Ｆ＃ | NextPage ]

連想配列

一般に、キーと値を関連付けて格納するデータ構造を「連想配列」といいます。連想配列は多くのプログラミング言語でサポートされていて、プログラミング言語によっては、ハッシュ (hash), 辞書 (dictonary), マップ (map) などと呼ばれています。拙作のページ レキシカルスコープとクロージャ で簡単に説明した「連想リスト」も連想配列のひとつです。

Perl, Python, Ruby など連想配列をサポートしているスクリプト言語がありますが、その実装には「ハッシュ法」が使われています。Perl や Ruby などで連想配列をハッシュと呼ぶのは、アルゴリズムの名称からきているのです。

F# の場合、標準ライブラリに平衡二分木をベースにしたマップ Map<'a, 'b> が用意されています。'a はキーの型、'b は値の型を表します。関数型言語らしく Map は immutable なデータ構造です。また、.NET の標準ライブラリ System.Collections.Generic には辞書 Dictionary<'a, 'b> が用意されているので、それを利用することもできます。Dictionary は mutable なデータ構造です。今回は Map と Dictionary の基本的な使い方について簡単に説明します。

●マップの基本的な操作メソッド

マップはコンストラクタ Map で生成します。 

Map sequence => table

引数 sequence はシーケンスの他にリストや一次元配列でもかまいません。要素はキーと値を格納したタプルです。ようするに、連想リストからマップを生成するわけです。なお、キーとなる型には制約 comparison を満たす必要があります。

たとえば、キーが文字列で値が整数の場合、マップは次のように生成します。 

> let a = Map [("foo", 1); ("bar", 2); ("baz", 3)];;
val a: Map = map [("bar", 2); ("baz", 3); ("foo", 1)]

キーの有無はメソッド ContainsKey で調べることができます。 

this.ContainsKey(key) => bool

> a.ContainsKey("foo");;
val it: bool = true

> a.ContainsKey("Foo");;
val it: bool = false

キーに対応する値は、配列のように角カッコを使って求めることができます。ただし、キーが見つからない場合はエラーが送出されます。メソッド TryFind はキーに対応する値を option 型に包んで返します。 

this.[key] => value
this.TryFind(key) => option

> a.["bar"];;
val it: int = 2

> a.["Bar"];;
=> エラー

> a.TryFind("bar");;
val it: int option = Some 2

> a.TryFind("Bar");;
val it: int option = None

マップに新しいキーと値を追加するにはメソッド Add を使います。マップからキーと対応する値を削除するにはメソッド Remove を使います。 

this.Add (key, value) => new_table
this.Remove key => new_table

> let b = a.Add("oops", 4);;
val b: Map = map [("bar", 2); ("baz", 3); ("foo", 1); ("oops", 4)]

> a;;
val it: Map = map [("bar", 2); ("baz", 3); ("foo", 1)]

> let c = a.Remove("foo");;
val c: Map = map [("bar", 2); ("baz", 3)]

> a;;
val it: Map = map [("bar", 2); ("baz", 3); ("foo", 1)]

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

メソッド Change は指定したキーの値を更新した新しいマップを返します。 

this.Change(key, func) => new_table

値は関数 func で更新します。func の型を示します。 

'b option -> 'b option

key が見つからない場合、func には None が渡されます。このとき、Some value を返すと Add と同じ動作になります。func が None を返す場合、キーがあれば Remove と同じ動作になります。 

> a;;
val it: Map = map [("bar", 2); ("baz", 3); ("foo", 1)]

> a.Change("foo", fun _ -> Some 10);;
val it: Map = map [("bar", 2); ("baz", 3); ("foo", 10)]

> a.Change("oops", fun _ -> Some 10);;
val it: Map =
  map [("bar", 2); ("baz", 3); ("foo", 1); ("oops", 10)]

> a.Change("oops", fun _ -> None);;
val it: Map = map [("bar", 2); ("baz", 3); ("foo", 1)]

> a.Change("foo", fun _ -> None);;
val it: Map = map [("bar", 2); ("baz", 3)]

プロパティ Keys はマップのキーを格納したシーケンスを返します。Values はマップの値を格納したシーケンスを返します。 

> a.Keys;;
val it: System.Collections.Generic.ICollection =
  seq ["bar"; "baz"; "foo"]

> for x in a.Keys do printfn "%s" x;;
bar
baz
foo
val it: unit = ()

> a.Values;;
val it: System.Collections.Generic.ICollection<int> = seq [2; 3; 1]

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

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

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

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

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

この他にも、マップを操作する関数がモジュール Map に用意されています。メソッドに対応する関数を以下に示します。 

Map.empty => empty_table
Map.isEmpty table => bool
Map.count talbe => int
Map.add key value table => new_table
Map.remove key table => new_table
Map.change key func table => new_table
Map.containsKey key table => bool
Map.find key table => value
Map.tryFind key table => value option
Map.keys table => sequence
Map.values table => sequence

●高階関数

Map にはマップ用の高階関数が用意されています。 

> Map.map;;
val it: (('a -> 'b -> 'c) -> Map<'a,'b> -> Map<'a,'c>) when 'a: comparison

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

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

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

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

map, filter, fold, foldBack, iter は今までに説明した高階関数のマップバージョンです。関数にはキーと値が渡されることに注意してください。簡単な使用例を示しましょう。 

> Map.iter (fun k v -> printfn "%s, %d" k v) a;;
bar, 20
baz, 30
foo, 10
oops, 40
val it: unit = ()

> Map.map (fun _ v -> v * 10) a;;
val it: Map =
  map [("bar", 200); ("baz", 300); ("foo", 100); ("oops", 400)]

> Map.map (fun _ v -> string v) a;;
val it: Map =
  map [("bar", "20"); ("baz", "30"); ("foo", "10"); ("oops", "40")]

> Map.filter (fun _ v -> v > 20) a;;
val it: Map = map [("baz", 30); ("oops", 40)]

> Map.filter (fun (k: string) v -> k.[0] = 'b') a;;
val it: Map = map [("bar", 20); ("baz", 30)]

> Map.fold (fun a k v -> (k, v)::a) [] a;;
val it: (string * int) list =
  [("oops", 40); ("foo", 10); ("baz", 30); ("bar", 20)]

> Map.fold (fun a _ v -> a + v) 0 a;;
val it: int = 100

●検査と探索

述語 pred を満たすキーがあるか調べるには Map.exists を使います。Map.forall はすべてのキーが pred を満たせば真を返します。関数 findKey は pred を満たすキーを求めます。option 型で返す関数 tryFindKey もあります。 

Map.exists pred table => bool
Map.forall pred table => bool
Map.findKey pred table => key
Map.tryFindKey pred table => key option

pred の型は 'a -> 'b -> bool です。 

> let a = Map.empty |> Map.add 1 10 |> Map.add 3 30 |> Map.add 5 50;;
val a: Map = map [(1, 10); (3, 30); (5, 50)]

> Map.exists (fun k _ -> k % 2 <> 0) a;;
val it: bool = true

> Map.exists (fun k _ -> k % 2 = 0) a;;
val it: bool = false

> Map.forall (fun k _ -> k % 2 <> 0) a;;
val it: bool = true

> Map.forall (fun k _ -> k % 2 <> 0) (Map.add 2 20 a);;
val it: bool = false

> Map.findKey (fun k _ -> k % 2 = 0) a;;
=> エラー

> Map.tryFindKey (fun k _ -> k % 2 <> 0) a;;
val it: int option = Some 1

> Map.tryFindKey (fun k _ -> k % 2 = 0) a;;
val it: int option = None

●マップの変換

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

> Map.toList;;
val it: (Map<'a,'b> -> ('a * 'b) list) when 'a: comparison

> Map.toArray;;
val it: (Map<'a,'b> -> ('a * 'b)[]) when 'a: comparison

> Map.toSeq;;
val it: (Map<'a,'b> -> seq<'a * 'b>) when 'a: comparison

> Map.ofList;;
val it: (('a * 'b) list -> Map<'a,'b>) when 'a: comparison

> Map.ofArray;;
val it: (('a * 'b)[] -> Map<'a,'b>) when 'a: comparison

> Map.ofSeq;;
val it: (seq<'a * 'b> -> Map<'a,'b>) when 'a: comparison

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

> Map.toList a;;
val it: (string * int) list =
  [("bar", 20); ("baz", 30); ("foo", 10); ("oops", 40)]

> Map.toArray a;;
val it: (string * int)[] =
  [|("bar", 20); ("baz", 30); ("foo", 10); ("oops", 40)|]

> Map.toSeq a;;
val it: seq =
  seq [("bar", 20); ("baz", 30); ("foo", 10); ("oops", 40)]

> Map.ofList [("foo", 10); ("bar", 20); ("baz", 30); ("oops", 40)];;
val it: Map =
  map [("bar", 20); ("baz", 30); ("foo", 10); ("oops", 40)]

> Map.ofArray [|("foo", 10); ("bar", 20); ("baz", 30); ("oops", 40)|];;
val it: Map =
  map [("bar", 20); ("baz", 30); ("foo", 10); ("oops", 40)]

> seq {("foo", 10); ("bar", 20); ("baz", 30); ("oops", 40)} |> Map.ofSeq;;
val it: Map =
  map [("bar", 20); ("baz", 30); ("foo", 10); ("oops", 40)]

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

●ハッシュ法の仕組み

ここでハッシュ法について簡単に説明しておきましょう。ハッシュ法は「ハッシュ表 (hash table)」と呼ばれるデータを格納する配列と、データを数値に変換する「ハッシュ関数 (hash function)」を用意します。

たとえば、ハッシュ表の大きさを n とすると、ハッシュ関数はデータを 0 から n - 1 までの整数値に変換するように作ります。この値を「ハッシュ値 (hash value)」と呼びます。ハッシュ値はハッシュ表の添字に対応し、この位置にデータを格納します。つまり、ハッシュ関数によってデータを格納する位置を決める探索方法がハッシュ法なのです。

ハッシュ法で不特定多数のデータを取り扱う場合、異なるデータでも同じハッシュ値が生成されることがあります。これをハッシュ値の「衝突(collision)」といいます。つまり、データをハッシュ表に登録しようとしても、すでに先客が居座っているわけです。この場合、2 種類の解決方法があります。

ひとつは、ハッシュ表に複数のデータを格納することです。配列にはひとつのデータしか格納できないので、複数個のデータをまとめて格納しておく工夫が必要になります。このときによく利用されるデータ構造がリストです。ハッシュ表からデータを探索する場合、まずハッシュ値を求め、そこに格納されているリストの中からデータを探索します。これを「チェイン法 (chaining)」といいます。

この方法ではハッシュ値の衝突が頻繁に発生すると、データを格納するリストが長くなるため、探索時間が余分にかかってしまいます。効率よく探索を行うには、ハッシュ表の大きさとハッシュ関数の選択が重要になります。

第 2 の方法は空いている場所を探して、そこにデータを入れる方法です。この場合、最初とは違うハッシュ関数を用意して、新しくハッシュ値を計算させて場所を決めます。この処理を空いている場所が見つかるまで繰り返します。この方法を「オープンアドレス法 (open addressing)」といいます。

この場合、データの最大数はハッシュ表の大きさに制限されます。また、ハッシュ表の空きが少なくなると、探索効率も極端に低下してしまいます。このため、ハッシュ表の空きが少なくなったら、ハッシュ表のサイズを大きくして、ハッシュ表を作り直す作業を行うのがふつうです。これを「リハッシュ (rehash)」といいます。そのあと探索効率は良くなるので、リハッシュにかけた時間のもとは十分にとれます。

ハッシュ法を実装する場合、どちらの方法でも等値の判定処理とハッシュ関数が必要になります。.NET の場合、クラス System.Object のメソッド Equals をオーバーライドすることで、等値演算子を定義することができます。このとき、メソッド GetHashCode もオーバーライドしないとワーニングが表示されますが、この GetHashCode がハッシュ関数になります。

.NET の辞書 (Dictionary) はハッシュ法を使っています。既存のデータ型は Equals と GetHashCode をオーバーライドしているので、F# でも辞書を使うのは簡単です。ただし、参照型をキーにするときは等値判定とハッシュ値に注意してください。たとえば、クラスのインスタンスはアドレスを使って等値判定を行うので、要素が同じでも等しいと判定されないことがあります。また、配列は要素の値で等値判定を行いますが、要素が同じでもハッシュ値が異なることがあります。 

> type Foo(a: int) =
-   let x = a;;
type Foo =
  new: a: int -> Foo

> Foo(1) = Foo(1);;
val it: bool = false

> [|1;2;3|] = [|1;2;3|];;
val it: bool = true

> [|1;2;3|].GetHashCode();;
val it: int = 4825033

> [|1;2;3|].GetHashCode();;
val it: int = 55283354

> [|1;2;3|].GetHashCode();;
val it: int = 48766684

> [1;2;3] = [1;2;3];;
val it: bool = true

> [1;2;3].GetHashCode();;
val it: int = 1956583134

> [1;2;3].GetHashCode();;
val it: int = 1956583134

> (1,2,3) = (1,2,3);;
val it: bool = true

> (1,2,3).GetHashCode();;
val it: int = 1152

> (1,2,3).GetHashCode();;
val it: int = 1152

リストは要素の値で等値判定とハッシュ値の計算を行っているようです。タプルは値型なので、要素の値を使って処理されています。辞書 (ハッシュ) を使う場合、キーには値型を選ぶ、もしくは Equals と GetHashCode をオーバーライドすることをお勧めします。

●辞書

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

> type dict<'a, 'b> = System.Collections.Generic.Dictionary<'a, 'b>;;
type dict<'a,'b> = System.Collections.Generic.Dictionary<'a,'b>

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

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

Dictionary<'a, 'b>() => empty_table

型略称を使うと、次のようになります。 

> let a = dict<string,int>();;
val a: dict<string,int> = dict []

F# のタプル (連想リスト) で辞書を初期化することはできません。ご注意くださいませ。

●辞書のアクセス

要素は配列のように角カッコでアクセスすることができます。 

1. dic.[key]           // リード
2. dic.[key] <- value  // ライト

1 でキーが見つからない場合はエラーになります。2 は key の値を value に更新します。key が見つからない場合は key と value が辞書に登録されます。メソッド Add(key, value) でも辞書に登録することができます。Map とは違って辞書は mutable なデータ構造なので、キーに対応する値は破壊的に修正されることに注意してください。 

> a.["foo"] <- 10;;
val it: unit = ()

> a.["bar"] <- 20;;
val it: unit = ()

> a.Add("baz", 30);;
val it: unit = ()

> a;;
val it: dict = dict [("foo", 10); ("bar", 20); ("baz", 30)]

> a.["foo"];;
val it: int = 10

> a.["bar"];;
val it: int = 20

> a.["baz"];;
val it: int = 30

> a.["oops"];;
=> エラー

辞書からキーと値を削除するにはメソッド Remove を使います。 

dic.Remove(key) => bool

削除できた場合は true, キーが見つからない場合は false を返します。 

> a.["oops"] <- 40;;
val it: unit = ()

> a.["oops"];;
val it: int = 40

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

> a.["oops"];;
=> エラー

メソッド Clear は辞書を空にします。 

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

> a;;
val it: dict = dict []

●検査

キーの有無はメソッド ContainsKey で、値の有無はメソッド ContanisValue で調べることができます。 

dic.ContainsKey(key) => bool
dic.ContainsValue(value) => bool

> a;;
val it: dict = dict [("foo", 100); ("bar", 20); ("baz", 30)]

> a.ContainsKey("foo");;
val it: bool = true

> a.ContainsKey("oops");;
val it: bool = false

> a.ContainsValue(20);;
val it: bool = true

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

●プロパティ

辞書にはプロパティが用意されています。基本的なプロパティを以下に示します。 

> a;;
val it: dict = dict [("foo", 10); ("bar", 20); ("baz", 30)]

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

> a.Keys;;
val it: System.Collections.Generic.Dictionary`2.KeyCollection =
  seq ["foo"; "bar"; "baz"]

> a.Values;;
val it: System.Collections.Generic.Dictionary`2.ValueCollection =
  seq [10; 20; 30]

●簡単な例題

それでは簡単な例題として、3 次元空間の異なる点 (x, y, z) を n 個作る関数を作ります。要素 x, y, z は 0 から 99 までの整数値とし、乱数で生成することにします。生成する点が少なければ、マップや辞書を使わなくても線形探索で十分ですが、数が多くなると線形探索では時間がかかるようになります。

プログラムは次のようになります。 

リスト : n 個の異なる点を作る

open System

// 型略称
type dict<'a, 'b> = Collections.Generic.Dictionary<'a, 'b>

// 点 (x, y, z) を作る
let makePoint (gen: Random) = 
  (gen.Next(100), gen.Next(100), gen.Next(100))

// 異なる点を N 個作る (線形探索)
let makeData n =
  let gen = Random()
  let rec iter i xs =
    if i = n then xs
    else
      let p = makePoint gen
      if List.contains p xs then iter i xs
      else iter (i + 1) (p::xs)
  iter 0 []

// マップ
let makeData1 n =
  let gen = Random()
  let rec iter i (table: Map<(int*int*int),bool>) =
    if i = n then table
    else
      let p = makePoint gen
      if table.ContainsKey(p) then iter i table
      else table.Add(p, true) |> iter (i + 1)
  Map.empty |> iter 0

// 辞書 (ハッシュ)
let makeData2 n =
  let gen = Random()
  let table = dict<(int*int*int),bool>()
  let rec iter i =
    if i = n then table
    else
      let p = makePoint gen
      if table.ContainsKey(p) then iter i
      else (
        table.[p] <- true
        iter (i + 1)
      )
  iter 0

点はタプルで表します。関数 makeData は makePoint で点をひとつ生成し、それが今まで生成した点と異なることを関数 List.contains でチェックします。List.contains は線形探索なので、点が増えると時間がかかるようになります。

関数 makeData1 は生成したデータのチェックにマップを使います。マップは immutable なデータ構造なので、局所関数 iter の引数に渡して、iter を再帰呼び出しするときに更新します。関数 makeData2 は辞書を使ってチェックします。辞書は mutable なデータ構造なので、iter の中でデータを追加しています。

実際に 2000, 4000, 8000, 16000, 32000 個の点を作ったときの実行時間を示します。

表 : 実行時間 (単位 : 秒)
2000400080001600032000
線形探索0.2480.7442.98411.297 ----
マップ 0.0180.0230.0460.1010.228
辞書 0.0010.0020.0030.0210.024

線形探索と比べると、圧倒的にマップや辞書の方が速いですね。マップと辞書を比べると、辞書 (ハッシュ) の方が速くなりました。一般に、データの探索だけならばハッシュのほうが速くなるようです。興味のある方はいろいろ試してみてください。

集合 (Set)

「集合 (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 = 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 = set ["bar"; "baz"; "foo"; "oops"]

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

> b.Add("baz");;
val it: Set = 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 = set ["bar"; "baz"]

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

> b.Remove("Foo");;
val it: Set = 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 に用意されています。メソッドに対応する関数を以下に示します。 

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

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 を満たせば真を返します。 

Map.exists pred table => bool
Map.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> クラス をお読みくださいませ。

Copyright (C) 2022 Makoto Hiroi
All rights reserved.
[ PrevPage | Ｆ＃ | NextPage ]