Власна множина

Вказівки

Створіть власний тип множини.

Іноді виникає потреба визначити власну структуру даних певного типу, наприклад множину. У цій вправі ми визначимо власну множину. Неважливо, як вона влаштована всередині, аби лише поводилася як множина унікальних елементів.

Підказки

Щоб виконати цю вправу, потрібно створити тип даних CustomSet з екземплярами Eq та Show і реалізувати такі функції:

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

Оголошення типу-заглушки та сигнатури типів уже є, але визначити самі функції та створити змістовний тип даних, newtype або синонім типу доведеться самостійно.

Якщо є бажання написати ефективну реалізацію, але не зовсім зрозуміло, з чого почати, то найкращий відомий мені вступний посібник - це «Purely Functional Data Structures» Кріса Окасакі, одну з версій якого можна прочитати тут: https://www.cs.cmu.edu/~rwh/theses/okasaki.pdf