カスタムセット

説明

独自の集合型を作成しましょう。

集合のように、何らかの型の独自のデータ構造を定義する必要があることもあります。 この演習では、自分だけの集合を定義します。 内部でどのように動作するかは重要ではありません。一意な要素の集合のように振る舞えばよいのです。

ヒント

この演習を完了するには、データ型CustomSetを作成し、EqとShowのインスタンスを定義したうえで、次の関数を実装する必要があります。

• delete
• difference
• empty
• fromList
• insert
• intersection
• isDisjointFrom
• isSubsetOf
• member
• null
• size
• toList
• union

ダミーのデータ宣言と型シグネチャはすでに用意されていますが、関数を定義し、意味のあるデータ型、newtype、型シノニムを作るのは自分で行う必要があります。

効率的な実装を書くことに興味はあるけれど、どこから手を付ければよいかわからないという場合は、私が知るかぎり最良の入門書はChris Okasakiの『Purely Functional Data Structures』です。そのバージョンはこちらで読めます。 https://www.cs.cmu.edu/~rwh/theses/okasaki.pdf