定理証明手習い (72) subset?, list-extend, list-union
普通に集合を扱う関数
list-extend
はどこぞでちょっと使いました
(subset? xs ys)
xs
がys
の部分集合かどうか
(list-extend xs x)
xs
の末尾にx
を追加する 重複はしない
リストを先頭から眺めて、重複があれば終わり
末尾まで届いたら要素を追加
(list-union xs ys)
xs
の末尾にys
を結合する 重複はしない 順序を保存
xs
にys
の先頭の要素を追加したものと、ys
の残りを結合する
O(n2)だけどソートとかしてないしそんなもんかな
list-union
では、全域性の主張や帰納的な主張を構成するのに都合がいいように、左から右の順番で要素の順番が保持されます。
ソートはしないよ宣言
どうでもいいですが「左から右の」順番ってなんでしょう
「右から左の」順番だったら何かちがうのかな
「上から下の」じゃないよって言いたいわけではないだろうし