SLIB(Scheme)で集合を使ってみる

以下の環境でSLIBを使っていきます。
CPU : Intel Core i5 2.60GHz
OS : WIndows 10
言語 : Gauche 0.9.9

準備
定義
基本操作
- adjoin
- union
- intersection
- subset?
- member-if
もう少し高度な操作
- some
- every
- notany
- notevery
おわりに

準備

今回のテーマは集合です。
SLIBでは集合に対する操作をリストに対して使えるので、リストを集合とみなして使っていけるようです。
まずはモジュールのインポートから。

gosh> (use slib)
gosh> (require 'common-list-functions)
#t

定義

次に簡単な集合 $A=\{0, 2, 5\}$ と $B=\{1,2,8,9\}$ を定義します。

gosh> (define A '(0 2 5)) 
A     
gosh> (define B '(1 2 8 9)) 
B

基本操作

adjoin

adjoinは集合に要素を加える操作となります。試しに集合Aに要素1を加えてみましょう。

gosh> (adjoin 1 A)
(1 0 2 5)
gosh> A  
(0 2 5)

集合の要素が1つ増えているのがわかります。ただ、もとの集合Aは変化していないので注意が必要です。
当然ですが、以下のように、すでに集合に含まれている要素をadjoinしてもなにも変わりません。

gosh> (adjoin 0 A) 
(0 2 5)

union

unionは和集合 $A\cup B$ の操作を実行します。

gosh> (union A B)
(0 5 1 2 8 9)

intersection

intersectionは積集合 $A\cap B$ の操作を実行します。

gosh> (intersection A B)
(2)

subset?

subset?は $A\subset B$ が真か偽かを判断します。

gosh> (subset? A B) 
#f
gosh> (subset? '(0 2) A)
#t
gosh> (subset? '(0 2) B) 
#f

要素0と要素2はともに集合Aに含まれるのでは $\{0,2\}\subset A$ は真になります。

member-if

説明がまどろっこしいのでいきなり例を見てみます。

(member-if odd? '(2 4 6 9 5 8 7)) 
(9 5 8 7)

odd?というのは与えられた数字が奇数かどうでないかを判定する関数です。この場合、member-ifが行うのはリストを先頭から調べ、一番初めに奇数という条件を満たした要素と後ろに残った要素からなるリストを返すことです。
ですから、条件を満たす要素がすでにリストの先頭にある場合は、なにも変わらないように見えます。例えば先ほどと同じリストに対し、偶数か否かを判定するeven?を使えば次のようになります。

gosh> (member-if even? '(2 4 6 9 5 8 7)) 
(2 4 6 9 5 8 7)

もう少し高度な操作

ほかにもいろいろできそうなので、下準備として以下の関数を定義します。

gosh> (define (contain-char c) (lambda (pname) (number? (string-scan pname c)))) 
contain-char

contain-charはstring中に文字cが含まれているかどうかを判定する関数を返します。
使い方は以下の通りです。

gosh> ((contain-char "l") "mike")
#f
gosh> ((contain-char "m") "mike") 
#t

mikeという文字列は文字lを含みませんが文字mは含んでいる、というわけですね。

some

まずは人名のリストを作ります。

gosh> (define name-list '("haruhi" "kyon" "yuki" "mikuru" "itsuki")) 
name-list

someは与えられたリストに条件を満たす要素が1つでもあれば真となります。
アルファベットiを使う名前の人がいるか調べてみます。

gosh> (some (contain-char "i") name-list)
#t

#tなので条件を満たす人が少なくとも1人はいるようです。要素5の集合なので見れば一目瞭然ですが。
数式でイメージするとこんな感じでしょうか↓

$(some\ F\ A)\rightarrow\bigvee_{a\in A} F(a)$

ただし、Aは先ほど定義したname-listで、関数Fは要素aが条件を満たせば真、そうでなければ偽となる関数とします。

every

everyはすべての要素が条件を満たす場合に真となります。

gosh> (every (contain-char "i") name-list) 
#f

人名リストname-listのうち、人名kyonはアルファベットiを含まないので結果は偽となります。
everyは数式だとこんな感じでしょうか↓

$(every\ F\ A)\rightarrow\bigwedge_{a\in A} F(a)$

notany

notanyはいずれの要素も条件を満たさない場合に真となります。
例を以下に示します。

gosh> (notany (contain-char "i") name-list)   
#f
gosh> (notany (contain-char "p") name-list) 
#t

人名リストにはアルファベットiを含む人名がいくつかあるので偽となります。また、アルファベットpを含む人名はさすがにいないので真となります。
数式だとこんな感じでしょうか↓

$(notany\ F\ A)\rightarrow\overline{\bigvee_{a\in A} F(a)}=\bigwedge_{a\in A}\overline{F(a)}$

自明なことですが、これが意味するところはnotanyがsomeの否定だということです。こうして数式で見ると、いずれの要素も条件を満たさないときに真となる、ということがイメージしやすくなっている気がします。そう感じるのは私が理系だからでしょうか。

notevery

最後にnoteveryです。
こちらはnotanyのときよりさらにわかりやすいと思います。
名前の通りeveryの否定です。1つでも条件を満たさない要素があれば真となります。
例を見てみましょう。

gosh> (notevery (contain-char "i") name-list) 
#t

人名リストにある名前はアルファベットiを含まない名前kyonがあります。したがって真となります。
数式だとこんな感じですね↓

$(notevery\ F\ A)\rightarrow\overline{\bigwedge_{a\in A} F(a)}=\bigvee_{a\in A}\overline{F(a)}$

おわりに

SLIBで集合を使ってみようということで書いた文章ですが途中でリストの話みたいになっていました。もともと集合としてリストを使うよという話なので問題はないのですが、もう少しさらっと済ませればよかった気がします。
はてな記法 *1 *2にも少しずつ慣れてきましたが正直正解がわかりません。
それはそれとして、今後も集合やリストはばりばり使っていきたいところです。

*1:https://7shi.hateblo.jp/entry/2018/07/27/185311

*2:https://staff.hatenablog.com/entry/2015/09/09/152158

仮想計算機構

IT業界と無縁な派遣社員のブログ