M.Hiroi's Home Page

F# Programming

F# Junk Scripts

[ Home | Ｃ＃ | Ｆ＃ ]

多倍長整数

> 2I;;
val it: System.Numerics.BigInteger = 2 {IsEven = true;
                                        IsOne = false;
                                        IsPowerOfTwo = true;
                                        IsZero = false;
                                        Sign = 1;}

> printfn "%A" 2I;;
2
val it: unit = ()

> printfn "%A" (2I ** 64);;
18446744073709551616
val it: unit = ()

> printfn "%A" (2I ** 128);;
340282366920938463463374607431768211456
val it: unit = ()

●階乗

リスト : 階乗

let rec fact n =
  if n = 0 then 1I
  else (bigint n) * fact(n - 1)

> for i = 0 to 20 do printfn "%A" (fact i) done;;
1
1
2
6
24
120
720
5040
40320
362880
3628800
39916800
479001600
6227020800
87178291200
1307674368000
20922789888000
355687428096000
6402373705728000
121645100408832000
2432902008176640000
val it: unit = ()

> printfn "%A" (fact 50);;
30414093201713378043612608166064768844377641568960512000000000000
val it: unit = ()

●フィボナッチ数

リスト : フィボナッチ数

let fibo n =
  let rec fiboi n a b =
    if n = 0 then a
    else fiboi (n - 1) b (a + b)
  fiboi n 0I 1I

> for i = 50 to 60 do printfn "%A" (fibo i) done;;
12586269025
20365011074
32951280099
53316291173
86267571272
139583862445
225851433717
365435296162
591286729879
956722026041
1548008755920
val it: unit = ()

> printfn "%A" (fibo 100);;
354224848179261915075
val it: unit = ()

> printfn "%A" (fibo 200);;
280571172992510140037611932413038677189525
val it: unit = ()

●トリボナッチ数

次の漸化式で生成される数列をトリボナッチ数といいます。

\(\begin{array}{l} T_0 = T_1 = 0 \\ T_2 = 1 \\ T_{n+3} = T_{n+2} + T_{n+1} + T_n \end{array}\) 
リスト : トリボナッチ数

let tribo n =
  let rec triboi n a b c =
    if n = 0 then a
    else triboi (n - 1) b c (a + b + c)
  triboi n 0I 0I 1I

> for i = 0 to 40 do printf "%A " (tribo i) done;;
0 0 1 1 2 4 7 13 24 44 81 149 274 504 927 1705 3136 5768 10609 19513 35890 66012 121415 223317 
410744 755476 1389537 2555757 4700770 8646064 15902591 29249425 53798080 98950096 181997601 
334745777 615693474 1132436852 2082876103 3831006429 7046319384 
val it: unit = ()

> printfn "%A" (tribo 100);;
53324762928098149064722658
val it: unit = ()

●テトラナッチ数

次の漸化式で生成される数列をテトラナッチ数列といいます。

\(\begin{array}{ll} T_0 = T_1 = T_2 = 0 \\ T_3 = 1 \\ T_{n+4} = T_{n+3} + T_{n+2} + T_{n+1} + T_n \end{array}\) 
リスト : テトラナッチ数

let tetra n =
  let rec tetrai n a b c d =
    if n = 0 then a
    else tetrai (n - 1) b c d (a + b + c + d)
  tetrai n 0I 0I 0I 1I

> for i = 0 to 40 do printf "%A " (tetra i) done;;
0 0 0 1 1 2 4 8 15 29 56 108 208 401 773 1490 2872 5536 10671 20569 39648 76424 147312 
283953 547337 1055026 2033628 3919944 7555935 14564533 28074040 54114452 104308960 
201061985 387559437 747044834 1439975216 2775641472 5350220959 10312882481 19878720128 
val it: unit = ()

> printfn "%A" (tetra 100);;
2505471397838180985096739296
val it: unit = ()

●組み合わせの数

リスト : 組み合わせの数

let combination (n: int) (r: int) =
  let rec comb n r =
    if n = 0I || r = 0I then 1I
    else ((n - r + 1I) * comb n (r - 1I)) / r
  comb (bigint n) (bigint r)

> for i = 30 to 50 do printfn "(%d, %d) = %A" (2 * i) i (combination (2 * i) i) done;;
(60, 30) = 118264581564861424
(62, 31) = 465428353255261088
(64, 32) = 1832624140942590534
(66, 33) = 7219428434016265740
(68, 34) = 28453041475240576740
(70, 35) = 112186277816662845432
(72, 36) = 442512540276836779204
(74, 37) = 1746130564335626209832
(76, 38) = 6892620648693261354600
(78, 39) = 27217014869199032015600
(80, 40) = 107507208733336176461620
(82, 41) = 424784580848791721628840
(84, 42) = 1678910486211891090247320
(86, 43) = 6637553085023755473070800
(88, 44) = 26248505381684851188961800
(90, 45) = 103827421287553411369671120
(92, 46) = 410795449442059149332177040
(94, 47) = 1625701140345170250548615520
(96, 48) = 6435067013866298908421603100
(98, 49) = 25477612258980856902730428600
(100, 50) = 100891344545564193334812497256
val it: unit = ()

●多角数

点を多角形の形に並べたとき、その総数を多角数 (polygonal number) といいます。三角形に配置したものを三角数 (triangular number)、四角形に配置したものを四角数 (square number)、五角形に配置したものを五角数 (pentagonal number) といいます。三角数、四角数、五角数を下図に示します。

多角数の点の増分を表に示すと、次のようになります。 

 n   三角数            四角数             五角数
---+-----------------------------------------------------------
 1 |  1                 1                  1
 2 |  3 = 1+2           4 = 1+3            5 = 1+4
 3 |  6 = 1+2+3         9 = 1+3+5         12 = 1+4+7
 4 | 10 = 1+2+3+4      16 = 1+3+5+7       22 = 1+4+7+10
 5 | 15 = 1+2+3+4+5    25 = 1+3+5+7+9     35 = 1+4+7+10+13
 6 | 21 = 1+2+3+4+5+6  36 = 1+3+5+7+9+11  51 = 1+4+7+10+13+16

      ・・・・・・      ・・・・・・・     ・・・・・

 n | n(n + 1) / 2      n^2                n(3n - 1) / 2

表を見ればお分かりのように、三角数は公差 1、四角数は公差 2、五角数は公差 3、p 角数は公差 p - 2 の等差数列の和になります。初項を a, 公差を d とすると、等差数列の和 \(S_n\) は次式で求めることができます。

\( S_n = \dfrac{n(2a + (n - 1)d}{2} \)

a = 1, d = p - 2 を代入して計算すると、多角数 \(P_{p,n}\) は次式で求めることができます。

\( P_{p,n} = \dfrac{(p - 2)n^2 - (p - 4)n}{2} \)

この式を F# でプログラムすると、次のようになります。 

リスト : 多角数

let polygonalNumber (p: int) (n: int) =
  let polynum p n = ((p - 2I) * n * n - (p - 4I) * n) / 2I
  polynum (bigint p) (bigint n)

それでは実行してみましょう。 

> for p = 3 to 8 do
-   for n = 1 to 16 do
-     printf "%A " (polygonalNumber p n)
-   printfn "";;
1 3 6 10 15 21 28 36 45 55 66 78 91 105 120 136
1 4 9 16 25 36 49 64 81 100 121 144 169 196 225 256
1 5 12 22 35 51 70 92 117 145 176 210 247 287 330 376
1 6 15 28 45 66 91 120 153 190 231 276 325 378 435 496
1 7 18 34 55 81 112 148 189 235 286 342 403 469 540 616
1 8 21 40 65 96 133 176 225 280 341 408 481 560 645 736
val it: unit = ()

三角数かつ四角数である数を平方三角数 (square triangular number) といいます。F# でナイーブにプログラムすると次のようになります。 

リスト : 平方三角数

// 多角数の数列
let makePolyNumSeq (p: int) =
  let mutable i = 1
  fun () ->
    let item = polygonalNumber p i
    i <- i + 1
    item

// n 以下の平方三角数
let squareTriangular (n: bigint) =
  let p3 = makePolyNumSeq 3
  let p4 = makePolyNumSeq 4
  let rec iter (b, c, a) =
    if c > n then List.rev a
    else if b = c then iter (p3(), p4(), b::a)
    else if b < c then iter (p3(), c, a)
    else iter (b, p4(), a)
  iter (p3(), p4(), [])

実行結果は次のようになります。 

> printfn "%A" (squareTriangular 100000000000I);;
[1; 36; 1225; 41616; 1413721; 48024900; 1631432881; 55420693056]
val it: unit = ()

ところで、平方三角数 - Wikipedia に掲載されている平方三角数の公式 (一般項と漸化式) を使うと、もっと簡単にプログラムすることができます。

\( f(n) = \begin{cases} 0 & if \ n = 0 \\ 1 & if \ n = 1 \\ 34 \times f(n - 1) - f(n - 2) + 2 \quad & if \ n \geq 2 \end{cases} \)

図 : 平方三角数の漸化式

漸化式を末尾再帰でプログラムすると次のようになります。 

リスト : 平方三角数 (2)

let squareTriangularNum n =
  let rec iter n a b =
    if n = 0 then a
    else iter (n - 1) b (34I * b - a + 2I)
  iter n 0I 1I

実行結果は次のようになります。 

> for i = 1 to 10 do printfn "%A" (squareTriangularNum i) done;;
1
36
1225
41616
1413721
48024900
1631432881
55420693056
1882672131025
63955431761796
val it: unit = ()

●カタラン数

カタラン数 - Wikipedia によると、バランスの取れたカッコ列の総数や多角形を三角形分割したときの総数がカタラン数になるそうです。カタラン数は次に示す公式で求めることができます。

\( \mathrm{C}_n = \dfrac{{}_{2n} \mathrm{C}_n}{n + 1} = \dfrac{(2n)!}{(n+1)!n!} \)

カタラン数は組み合わせの数を求める関数 combination を使うと簡単に求めることができます。 

リスト : カタラン数

let catalan n = (combination (2 * n) n) / bigint(n + 1)

> for i = 0 to 20 do printfn "%A" (catalan i) done;;
1
1
2
5
14
42
132
429
1430
4862
16796
58786
208012
742900
2674440
9694845
35357670
129644790
477638700
1767263190
6564120420
val it: unit = ()

> printfn "%A" (catalan 50);;
1978261657756160653623774456
val it: unit = ()

> printfn "%A" (catalan 100);;
896519947090131496687170070074100632420837521538745909320
val it: unit = ()

●モンモール数

「完全順列 (derangement)」の総数を「モンモール数 (Montmort number)」といいます。モンモール数は次の漸化式で求めることができます。

\( A_n = \begin{cases} 0 & if \ n = 1 \\ 1 & if \ n = 2 \\ (n - 1) \times (A_{n-1} + A_{n-2}) \quad & if \ n \geq 3 \end{cases} \) 
リスト : モンモール数

let montmort n =
  let rec montsub i a b =
    if i = n then a
    else montsub (i + 1) b ((a + b) * bigint(i + 1))
  montsub 1 0I 1I

> for i = 1 to 20 do printfn "%A" (montmort i) done;;
0
1
2
9
44
265
1854
14833
133496
1334961
14684570
176214841
2290792932
32071101049
481066515734
7697064251745
130850092279664
2355301661033953
44750731559645106
895014631192902121
val it: unit = ()

> printfn "%A" (montmort 50);;
11188719610782480504630258070757734324011354208865721592720336801
val it: unit = ()

●ベル数

集合を分割する方法 の総数を「ベル数 (Bell Number)」といい、次の漸化式で求めることができます。

\(\begin{array}{ll} B(0) = 1 & \\ B(1) = 1 & \\ B(n+1) = \displaystyle \sum_{k=0}^n {}_n \mathrm{C}_k \times B(k) \quad & if \ n \geq 1 \end{array}\) 
リスト : ベル数

// 添字付き畳み込み
let foldWithIndex f a xs =
  let rec foldSub i a = function
    [] -> a
  | x::xs -> foldSub (i + 1) (f i x a) xs
  foldSub 0 a xs

// ベル数
let bellNumber n =
  let rec bellSub i bs =
    if i = n then List.head bs
    else bellSub (i + 1)
                 ((foldWithIndex (fun k x a -> (combination i k) * x + a) 0I bs) :: bs)
  bellSub 0 [1I]

bellNumber は公式をそのままプログラムするだけです。累積変数 bs にベル数を逆順で格納します。\({}_n \mathrm{C}_k\) は関数 combination で求めます。\({}_n \mathrm{C}_k \times B(k)\) の総和は関数 foldWithIndex で計算します。

foldWithIndex は添字を関数に渡して畳み込みを行います。ラムダ式の引数 k が添字、x がリストの要素、a が累積変数です。bs は逆順になっていますが、二項係数は \({}_n \mathrm{C}_i\) と \({}_n \mathrm{C}_{n-i}\) の値が同じになるので、そのまま計算しても大丈夫です。 

> for i = 0 to 20 do printfn "%A" (bellNumber i) done;;
1
1
2
5
15
52
203
877
4140
21147
115975
678570
4213597
27644437
190899322
1382958545
10480142147
82864869804
682076806159
5832742205057
51724158235372
val it: unit = ()

> printfn "%A" (bellNumber 50);;
185724268771078270438257767181908917499221852770
val it: unit = ()

●分割数

整数 n を 1 以上の自然数の和で表すことを考えます。これを「整数の分割」といいます。整数を分割するとき、同じ自然数を何回使ってもかまいませんが、並べる順序が違うだけのものは同じ分割とします。簡単な例を示しましょう。次の図を見てください。

6 の場合、分割の仕方は上図のように 11 通りあります。この数を「分割数」といいます。分割の仕方を列挙する場合、整数 n から k 以下の整数を選んでいくと考えてください。まず、6 から 6 を選びます。すると、残りは 0 になるので、これ以上整数を分割することはできません。次に、6 から 5 を選びます。残りは 1 になるので、1 を選ぶしか方法はありません。

次に、4 を選びます。残りは 2 になるので、2 から 2 以下の整数を分割する方法になります。2 から 2 を選ぶと残りは 0 になるので 2 が得られます。1 を選ぶと残りは 1 になるので、1 + 1 が得られます。したがって、4 + 2, 4 + 1 + 1 となります。同様に、6 から 3 を選ぶと、残りは 3 から 3 以下の整数を選ぶ方法になります。

6 から 2 以下の整数を選ぶ方法は、残り 4 から 2 以下の整数を選ぶ方法になり、そこで 2 を選ぶと 2 から 2 以下の整数を選ぶ方法になります。1 を選ぶと 4 から 1 以下の整数を選ぶ方法になりますが、これは 1 通りしかありません。最後に 6 から 1 を選びますが、これも 1 通りしかありません。これらをすべて足し合わせると 11 通りになります。

整数 n を k 以下の整数で分割する総数を求める関数を p(n, k) とすると、p(n, k) は次のように定義することができます。

\( p(n, k) = \begin{cases} 1 & if \ n = 0 \ or \ k = 1 \\ 0 & if \ n \lt 0 \ or \ k \lt 1 \\ p(n - k, k) + p(n, k - 1) \quad & others \end{cases} \)

たとえば、p(6, 6) は次のように計算することができます。 

p(6, 6) => p(0, 6) + p(6, 5)
        => 1 + p(1, 5) + p(6, 4)
        => 1 +    1    + p(2, 4) + p(6, 3)
        => 1 + 1 + 2 + 7
        => 11

p(2, 4) => p(-2, 4) + p(2, 3)
        =>    0     + p(-1, 3) + p(2, 2)
        =>    0     +    0     + p(0, 2) + p(2, 1)
        => 0 + 0 + 1 + 1
        => 2

p(6, 3) => p(3, 3) + p(6, 2)
        => p(0, 3) + p(3, 2) + p(4, 2) + p(6, 1)
        =>    1    + p(1, 2) + p(3, 1) + p(2, 2) + p(4, 1) + 1
        =>    1    +    1    +    1    + p(0, 2) + p(2, 1) + 1 + 1
        => 1 + 1 + 1 + 1 + 1 + 1 + 1
        => 7

これをそのままプログラムすると実行時間は遅くなるのですが、動的計画法を使うと、大きな値でも高速に計算することができます。次の図を見てください。 

k 
1 : [1,  1,  1,  1,  1,  1,  1] 

2 : [1,  1,  1+1=2, 1+1=2, 2+1=3, 2+1=3, 3+1=4]
 => [1,  1,  2,  2,  3,  3,  4]

3:  [1,  1,  2,  1+2=3, 1+3=4, 2+3=5, 3+4=7]
 => [1,  1,  2,  3,  4,  5,  7]

4:  [1,  1,  2,  3,  1+4=4, 1+5=6, 2+7=9]
 => [1,  1,  2,  3,  5,  6,  9

5:  [1,  1,  2,  3,  5,  1+6=7, 1+9=10]
 => [1,  1,  2,  3,  5,  7,  10]

6:  [1,  1,  2,  3,  5,  7,  10+1=11]
 => [1,  1,  2,  3,  5,  7,  11]

大きさ n + 1 の配列を用意します。配列の添字が n を表していて、p(n, 1) から順番に値を求めていきます。p(n, 1) の値は 1 ですから、配列の要素は 1 に初期化します。次に、p(n, 2) の値を求めます。定義により p(n, 2) = p(n - 2, 2) + p(n, 1) なので、2 番目以降の要素に n - 2 番目の要素を加算すれば求めることができます。あとは、k の値をひとつずつ増やして同様の計算を行えば p(n, n) の値を求めることができます。 

リスト : 分割数 (動的計画法)

let partitionNumber n =
  let table = Array.create (n + 1) 1I
  for k = 2 to n do
    for m = k to n do
      table.[m] <- table.[m] + table.[m - k]
  table.[n]

> for i = 1 to 20 do printfn "%A" (partitionNumber i) done;;
1
2
3
5
7
11
15
22
30
42
56
77
101
135
176
231
297
385
490
627
val it: unit = ()

> printfn "%A" (partitionNumber 100);;
190569292
val it: unit = ()

> printfn "%A" (partitionNumber 200);;
3972999029388
val it: unit = ()

> printfn "%A" (partitionNumber 1000);;
24061467864032622473692149727991
val it: unit = ()

ところで、数がもっと大きくなると動的計画法を使ったプログラムでも遅くなります。もっと高速に求める方法があるので、興味のある方は拙作のページ Puzzle DE Programming 分割数 をお読みくださいませ。

集合

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

F# の場合、標準ライブラリに集合を扱うモジュール Set が用意されていますが、今回は F# の勉強ということで、モジュールを使う方法とオブジェクト指向を使う方法の二通りで set を作ることにします。標準モジュール Set は二分木 (平衡木) を使っていますが、今回は簡単な例題ということでリストを使うことにします。

●モジュールによる実装

モジュールで定義する関数を表に示します。

表 : 集合の基本操作
名前機能
empty空の集合
add x s 集合 s に要素 x を追加する
remove x s 集合 s から要素 x を削除する
contains x s 要素 x は集合 s に含まれているか
count s集合 s の要素数を返す
isEmpty s集合 s が空集合ならば真を返す
isSubset s1 s2 s1 は s2 の部分集合か
isEqual s1 s2 s1 と s2 は等しいか
union s1 s2 s1 と s2 の和集合を求める
intersection s1 s2 s1 と s2 の積集合を求める
difference s1 s2 s1 と s2 の差集合を求める
iter func s 集合の各要素に関数 func を適用する
ofList ls リストを集合に変換する
toList s 集合をリストに変換する

●プログラムリスト１

//
// set.fsx : モジュールによる集合
//
//           Copyright 2022 Makoto Hiroi
//
namespace Mylib

module Set =
  type 'a set = S of 'a list

  let empty = S []

  let add x (S xs) =
    if List.contains x xs then S xs
    else S (x::xs)

  let remove x (S xs) =
    let rec removeList = function
      [] -> []
    | y::ys when y = x -> removeList ys
    | y::ys -> y :: removeList ys
    removeList xs

  let contains x (S xs) = List.contains x xs

  let count (S xs) = List.length xs

  let isEmpty (S xs) = List.isEmpty xs

  let isSubset (S xs) (S ys) =
    let rec isSubsetList xs ys =
      match xs with
        [] -> true
      | z::zs when List.contains z ys -> isSubsetList zs ys
      | _ -> false
    isSubsetList xs ys

  let isEqual s1 s2 = (isSubset s1 s2) && (isSubset s2 s1)

  let union (S xs) (S ys) =
    let rec unionList xs ys =
      match xs with
        [] -> ys
      | z::zs when List.contains z ys -> unionList zs ys
      | z::zs -> z :: unionList zs ys
    unionList xs ys

  let intersect (S xs) (S ys) =
    let rec interList xs ys =
      match xs with
        [] -> []
      | z::zs when List.contains z ys -> z :: interList zs ys
      | _::zs -> interList zs ys
    interList xs ys

  let difference (S xs) (S ys) =
    let rec diffList xs ys =
      match xs with
        [] -> []
      | z::zs when List.contains z ys -> diffList zs ys
      | z::zs -> z :: diffList zs ys
    diffList xs ys

  let iter func (S xs) = List.iter func xs

  let ofList xs = S (List.distinct xs)

  let toList (S xs) = xs

namespace FSI_0002.Mylib
  type 'a set = | S of 'a list
  val empty: 'a set
  val add: x: 'a -> 'a set -> 'a set when 'a: equality
  val remove: x: 'a -> 'a set -> 'a list when 'a: equality
  val contains: x: 'a -> 'a set -> bool when 'a: equality
  val count: 'a set -> int
  val isEmpty: 'a set -> bool
  val isSubset: 'a set -> 'a set -> bool when 'a: equality
  val isEqual: s1: 'a set -> s2: 'a set -> bool when 'a: equality
  val union: 'a set -> 'a set -> 'a list when 'a: equality
  val intersect: 'a set -> 'a set -> 'a list when 'a: equality
  val difference: 'a set -> 'a set -> 'a list when 'a: equality
  val iter: func: ('a -> unit) -> 'a set -> unit
  val ofList: xs: 'a list -> 'a set when 'a: equality
  val toList: 'a set -> 'a list

●実行例１

> open Mylib.Set;;
> let a = add 1 empty;;
val a: int set = S [1]

> let b = add 2 a;;
val b: int set = S [2; 1]

> let c = add 3 b;;
val c: int set = S [3; 2; 1]

> remove 3 c;;
val it: int list = [2; 1]

> remove 4 c;;
val it: int list = [3; 2; 1]

> isEmpty c;;
val it: bool = false

> isEmpty empty;;
val it: bool = true

> count a;;
val it: int = 1

> count b;;
val it: int = 2

> count c;;
val it: int = 3

> contains 1 c;;
val it: bool = true

> contains 4 c;;
val it: bool = false

> isSubset b c;;
val it: bool = true

> isSubset c b;;
val it: bool = false

> isEqual c c;;
val it: bool = true

> isEqual b c;;
val it: bool = false

> toList c;;
val it: int list = [3; 2; 1]

> let x = ofList [1;2;3;4];;
val x: int set = S [1; 2; 3; 4]

> let y = ofList [3;4;5;6];;
val y: int set = S [3; 4; 5; 6]

> union x y;;
val it: int list = [1; 2; 3; 4; 5; 6]

> intersect x y;;
val it: int list = [3; 4]

> difference x y;;
val it: int list = [1; 2]

> difference y x;;
val it: int list = [5; 6]

●クラスによる実装

クラスで定義するメソッドを表に示します。

表 : 集合 Set<'a> の基本メソッド
名前機能
new()空の集合を生成する
new(xs: 'a list)リスト xs から集合を生成する
s.add x 集合 s に要素 x を追加する
s.remove x 集合 s から要素 x を削除する
s.contains x 要素 x は集合 s に含まれているか
s.count ()集合 s の要素数を返す
s.isEmpty ()集合 s が空集合ならば真を返す
s1.isSubset s2 s1 は s2 の部分集合か
s1.isEqual s2 s1 と s2 は等しいか
s1.union s2 s1 と s2 の和集合を求める (結果は s1 にセット)
s1.intersection s2 s1 と s2 の積集合を求める (結果は s1 にセット)
s1.difference s2 s1 と s2 の差集合を求める (結果は s1 にセット)
s.iter func 集合 s の各要素に関数 func を適用する
s.toList () 集合 s をリストに変換する

●プログラムリスト２

//
// set1.fsx : クラスによる集合の実装
//
//            Copyright (C) 2022 Makoto Hiroi
//
module Mylib

type Set<'a when 'a: equality> = class
  val mutable private content : 'a list
  val mutable private size : int

  // コンストラクタ
  new () = {content = []; size = 0}
  new (xs: 'a list) =
    let ys = List.distinct xs
    {content = ys; size = List.length ys}

  // プロパティ
  member this.Content with get() = this.content

  // メソッド
  member this.add x =
    if not (List.contains x this.content) then (
      this.size <- this.size + 1
      this.content <- x::this.content
    ) else ()

  member this.remove x =
    if List.contains x this.content then (
      this.content <- List.filter (fun y -> x <> y) this.content
      this.size <- this.size - 1
    ) else ()

  member this.contains x = List.contains x this.content

  member this.count () = this.size

  member this.isEmpty = this.size = 0

  member this.isSubset (s: Set<'a>) =
    let rec isSubsetList xs ys =
      match xs with
        [] -> true
      | z::zs when List.contains z ys -> isSubsetList zs ys
      | _ -> false
    isSubsetList this.content s.content

  member this.isEqual (s: Set<'a>) =
    this.isSubset(s) && s.isSubset(this)

  member this.union (s: Set<'a>) =
    let rec unionList xs ys =
      match xs with
        [] -> ys
      | z::zs when List.contains z ys -> unionList zs ys
      | z::zs -> z :: unionList zs ys
    this.content <- unionList this.content s.content
    this.size <- List.length this.content

  member this.intersect (s: Set<'a>) =
    let rec interList xs ys =
      match xs with
        [] -> []
      | z::zs when List.contains z ys -> z :: interList zs ys
      | _::zs -> interList zs ys
    this.content <- interList this.content s.Content
    this.size <- List.length this.content

  member this.difference (s: Set<'a>) =
    let rec diffList xs ys =
      match xs with
        [] -> []
      | z::zs when List.contains z ys -> diffList zs ys
      | z::zs -> z :: diffList zs ys
    this.content <- diffList this.content s.content
    this.size <- List.length this.content

  member this.iter func = List.iter func this.content

  member this.toList () = this.content
end

namespace FSI_0002
  type Set<'a when 'a: equality> =
    new: xs: 'a list -> Set<'a> + 1 オーバーロード
    val mutable private content: 'a list
    val mutable private size: int
    member add: x: 'a -> unit
    member contains: x: 'a -> bool
    member count: unit -> int
    member difference: s: Set<'a> -> unit
    member intersect: s: Set<'a> -> unit
    member isEqual: s: Set<'a> -> bool
    member isSubset: s: Set<'a> -> bool
    member iter: func: ('a -> unit) -> unit
    member remove: x: 'a -> unit
    member toList: unit -> 'a list
    member union: s: Set<'a> -> unit
    member Content: 'a list
    member isEmpty: bool

●実行例２

> open Mylib;;
> let a = new Set<int>();;
val a: Set<int>

> a.add 1;;
val it: unit = ()

> a.add 2;;
val it: unit = ()

> a.add 3;;
val it: unit = ()

> a;;
val it: Set<int> = FSI_0002.Mylib+Set`1[System.Int32] {Content = [3; 2; 1];
                                                       isEmpty = false;}
> a.count();;
val it: int = 3

> a.contains 1;;
val it: bool = true

> a.remove 1;;
val it: unit = ()

> a.count();;
val it: int = 2

> a.contains 1;;
val it: bool = false

> let b = new Set<int>([1;2;3]);;
val b: Set<int>

> a.isSubset b;;
val it: bool = true

> b.isSubset a;;
val it: bool = false

> a.isEqual b;;
val it: bool = false

> a.isEqual a;;
val it: bool = true

> a.toList();;
val it: int list = [3; 2]

> b.toList();;
val it: int list = [1; 2; 3]

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

> x.union (new Set<int>([3;4;5;6]));;
val it: unit = ()

> x.toList();;
val it: int list = [1; 2; 3; 4; 5; 6]

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

> x.intersect (new Set<int>([3;4;5;6]));;
val it: unit = ()

> x.toList();;
val it: int list = [3; 4]

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

> x.difference (new Set<int>([3;4;5;6]));;
val it: unit = ()

> x.toList();;
val it: int list = [1; 2]
Copyright (C) 2022 Makoto Hiroi
All rights reserved.
[ Home | Ｃ＃ | Ｆ＃ ]