ReScriptでListの積集合と差集合を求める

リストは再帰的に定義されるデータ構造なので、再帰関数で処理するときれいです。

# ReScript実行環境の準備
https://rescript-lang.org/docs/manual/latest/installation にしたがって ReScript をインストールします。
[《プログラミングの基礎》をReScriptで読む 第1章](https://qiita.com/sgigagaeru/items/df793d98cb411d2b2d2a)に、少しだけ詳しい記載があります。

# リストにアイテムが含まれるか判定する関数
積集合、差集合を求める際に、リストにアイテムが含まれるか判定する必要が出てくるので、まずその関数を作ります。[^has]
[^has]: 標準ライブラリにある`List.has`を使うことにしても良いです。

src ディレクトリに SetUtility.res というファイル名で ReScript ファイルを作成しました。

```ReScript:src/SetUtility.res
let rec has = (lst, item) => switch lst {
| list{} => false // 空リストの場合は false
| list{first, ...rest} => // 先頭の要素(first)とそれ以外のリスト(rest)の場合は
    if first == item {
      true  // 先頭の要素が item なら true
    } else {
      has(rest, item)  // 残りのリストの中に item があるか調べる
    }
}
```
ReScriptでは、リストに対してパターンマッチングが使えるので、きれいに書くことができます。
パターンマッチングについては https://rescript-lang.org/docs/manual/latest/pattern-matching-destructuring を参照してください。

テストも書いておきます。
テストにパスした場合はコンソールに`true`が、そうでない場合は`false`が表示されます。

```ReScript:src/SetUtility.res
// hasのテスト
let list1 = list{1, 2, 3, 4, 5}
Console.log(has(list1, 1) == true)
Console.log(has(list1, 6) == false)

let list2 = list{"One", "Two", "Three"}
Console.log(has(list2, "Two") == true)
Console.log(has(list2, "Four") == false)

type user = {id: int, name: string}
let list3 = list{
  {id: 01, name: "Ultraman"},
  {id: 02, name: "Ultraseven"},
  {id: 03, name: "Newman"}
}
Console.log(has(list3, {id: 01, name: "Ultraman"}) == true)
Console.log(has(list3, {id: 04, name: "Godzilla"}) == false)
```

ReScriptファイルをJavaScriptファイルに変換します。

```SH:SH
npm run res:build
```

srcディレクトリの SetUtility.res が JavaScript に変換され、SetUtility.bs.js に出力されます。
変換された JavaScript を実行します。

```SH:SH
node src/SetUtility.res.js
true
true
true
true
true
true
```
true が六つ表示され、テストもパスしていることが分かります。[^record_test]
[^record_test]: `list<int>`に対する関数を書いたつもりでしたが、`list<string>`でも動作する関数になっていました(`list2`に対するテスト結果)。レコードに対しては動作しないだろうと思っていたら動きました(`list3`に対するテスト結果)。ReScriptの`==`はけっこうすごいようです。

# 積集合を求める
```ReScript:src/SetUtility.res
// 目的 : lst1 と lst2 の積集合を求める
// intersection : (list<'a>, list<'a>) => list<'a>
let rec intersection = (lst1, lst2) => switch lst1 {
| list{} => list{}
| list{first, ...rest} => 
    if has(lst2, first) {
      // first が lst2 にあるなら結果のリストに含める
      list{first, ...intersection(rest, lst2)}
    } else {
      // first が lst2 にないなら結果のリストに含めない
      intersection(rest, lst2)
    }
}

// intersection のテスト
let list01 = list{1, 2, 3, 4, 5}
let list02 = list{3, 4, 5, 6, 7}
Console.log(intersection(list01, list02) == list{3, 4, 5})

let list03 = list{
  {id: 01, name: "1gou"},
  {id: 02, name: "2gou"},
  {id: 03, name: "V3"}
}
let list04 = list{
  {id: 03, name: "V3"},
  {id: 05, name: "X"},
  {id: 07, name: "Stronger"}
}
Console.log(intersection(list03, list04) == list{{id: 03, name: "V3"}})
```
hasのときと同じように JavaScript に変換して実行すると動作していることが確認できます。

# 差集合を求める
```ReScript:src/SetUtility.res
// 目的 : lst1 と lst2 の差集合 (lst1 - lst2) を求める
// difference : (list<'a>, list<'a>) => list<'a>
let rec difference = (lst1, lst2) => switch lst1 {
| list{} => list{}
| list{ first, ...rest } =>
    if has(lst2, first) {
      // first が lst2 にあるなら結果のリストに含めない
      difference(rest, lst2)
    } else {
      // first が lst2 にないなら結果のリストに含める
      list{first, ...difference(rest, lst2)}
    }
}

// difference のテスト
Console.log(difference(list03, list04) == list{
  {id: 01, name: "1gou"},
  {id: 02, name: "2gou"}
})
Console.log(difference(list04, list03) == list{
  {id: 05, name: "X"},
  {id: 07, name: "Stronger"}
})
```
JavaScriptに変換して実行して、動作を確認できます。

# `Js.List.foldRight`を使う
パターンマッチの部分が
```ReScript:ReScript
| list{} => // 初期値
| list{first, ...rest} => // firstと、restに対する再帰の結果とを処理
```
の形の場合は、`Js.List.foldRight`が使える気がします。
書き直してみたら使えました。
```ReScript:src/SetUtility.res
// 目的 : lstの中にitemが含まれるか調べる
// has : (list<'a>, 'a) => bool
let has = (lst, item) => Js.List.foldRight(
  (first, rest_result) => if first == item {true} else {rest_result},
  lst,
  false
)

// 目的 : lst1 と lst2 の積集合を求める
// intersection : (list<'a>, list<'a>) => list<'a>
let intersection = (lst1, lst2) => Js.List.foldRight(
  (first, rest_result) => if has(lst2, first) {list{first, ...rest_result}} else {rest_result},
  lst1,
  list{}
)

// 目的 : lst1 と lst2 の差集合 (lst1 - lst2) を求める
// difference : (list<'a>, list<'a>) => list<'a>
let difference = (lst1, lst2) => Js.List.foldRight(
  (first, rest_result) => if has(lst2, first) {rest_result} else {list{first, ...rest_result}},
  lst1,
  list{}
)
```