F#で集合を扱う その1

F#で数学における「集合」を扱うために、名前空間：Microsoft.FSharp.Collections には Set というモジュールが用意されています。

整数0から5までの集合を作るには、

let is = Set.ofList [0..5]

このコードは、整数0から5のリスト [0; 1; 2; 3; 4; 5] に Set.ofList という関数を適用して集合 is を生成しています。

F# Interactiveで実行してみると

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

Set.ofList は set で代用できるので以下のコードも同じ意味。

let is = set [0..5]

> let is = set [0..5];;
val is : Set<int> = set [0; 1; 2; 3; 4; 5]

コンソール出力ではリストとの区別は分かりにくいのですが 、F#の集合（Set）は内部的に平衡二分木によって要素を保持しています。要素の重複は許可されません。順序付けのために各要素を比較する必要があるため、この集合における要素は前提条件として、型制約があり IComparable インターフェイスを実装している必要があります。普通のプリミティブ型などは特に問題なく要素として使えます。

例えば、順序を無視して要素を与えても同じ集合を生成できます。

> let is = set [1; 0; 2; 4; 3; 5];;
val is : Set<int> = set [0; 1; 2; 3; 4; 5]

リストどうしでは要素の並び順が違えば同値とはみなしませんが、

> [0; 1; 2; 3; 4; 5] = [1; 0; 2; 4; 3; 5];;
val it : bool = false

集合どうしでは要素の与え方に関わらず同値とみなします。

> set [0; 1; 2; 3; 4; 5] = set [1; 0; 2; 4; 3; 5];;
val it : bool = true

注意：上の例では、単純にイコール記号（=）を使ってリストどうしや集合どうしの同値判定をしていますが、この場合は内部的に System.Object クラスの Equals メソッドのオーバーライドが行われていて、データ構造に配慮した適切な同値判定が行われています。

集合を定義する方法は複数あり、パイプライン演算子 |> を用いて要素を1つずつ集合に追加していくこともできます。

> let s2 = 
    set []
    |> Set.add 1
    |> Set.add 0
    |> Set.add 2
    |> Set.add 4
    |> Set.add 3
    |> Set.add 5 ;;

val s2 : Set<int> = set [0; 1; 2; 3; 4; 5]

 集合において要素の重複は許可されないので、下記コードのように同じ値を何度追加しても2回目以降は要素を追加することはできません。

> let s3 =
    set []
    |> Set.add 1    
    |> Set.add 1    
    |> Set.add 1 ;;  
 
val s3 : Set<int> = set [1]