Представление теоретико-множественных представлений в терминах списков в Haskell

Question

Я пытаюсь определить новый тип в Haskell (т.е. наборы) и оперировать им с точки зрения функций, которые вводят и выводят неупорядоченные списки без дубликатов.

Я на правильном пути здесь?Любое предложение приветствуется, даже самый незначительный обман.Я бы хотел, чтобы мой код был максимально элегантным.

-- generalized membership

type Set a = [a]

member :: Eq a => a -> [a] -> Bool
member x []                 = False
member x (y:ys) | x == y    = True
                | otherwise = member x ys                

-- elimination of duplicates

noReps :: Set Integer -> Set Integer
noReps []                   = []
noReps (x:xs) | member x xs = noReps xs
              | otherwise   = x : noReps xs

inclusion :: Set Integer -> Set Integer -> Bool
inclusion x y = length [i | i <- x, not (member i y)] == 0

identical :: Set Integer -> Set Integer -> Bool 
identical x y = inclusion x y && inclusion y x

-- membership for sets of sets

setmember :: Set Integer -> Set (Set Integer) -> Bool
setmember [] _                      = True
setmember _ []                      = False
setmember x (y:ys)  | identical x y = True 
                    | otherwise     = setmember x ys   

addsets :: Set Integer -> Set (Set Integer) -> Set (Set Integer)
addsets x y | setmember x y = y
            | otherwise = x:y

-- adding an integer to every member of a sets of sets of integers

addelem :: Integer -> Set (Set Integer) -> Set (Set Integer) 
addelem x y = [noReps (x : i) | i <- y]

-- powerset of the set {1,...,n}

powerset :: Integer -> Set (Set Integer)
powerset 1 = [[], [1]]
powerset x = powerset (x-1) ++ addelem x (powerset (x-1))

Answer 1

выглядит хорошо для меня (для «бесполезных упражнений», как вы выразились); Одно: ни одна из ваших подписей не требует специализирования как Integer, все, что поддерживает равенство (Eq), будет работать, при этом powerset дополнительно требует числовое значение (опять же, не обязательно Integer):

noReps :: Eq a => Set a -> Set a
inclusion :: Eq a => Set a -> Set a -> Bool
identical :: Eq a => Set a -> Set a -> Bool 
setmember :: Eq a => Set a -> Set (Set a) -> Bool
addsets :: Eq a => Set a -> Set (Set a) -> Set (Set a)
addelem :: Eq a => a -> Set (Set a) -> Set (Set a) 
powerset :: (Eq a, Num a) => a -> Set (Set a)

Все эти подписи будут работать, абсолютно ничего не меняя в самих функциях.

(РЕДАКТИРОВАТЬ: обычно хорошей идеей является сделать ваши подписи как можно более универсальными и полиморфными - это не только позволит повторно использовать код, но и ограничит то, что ваши функции могут делать со своими аргументами - в данном случае, сигнатура позволяет применять ТОЛЬКО оператор == - вы снижаете риск ошибок / непреднамеренных эффектов).

Конечно, использование списков сделает код простым, но медленным - для реального кода вы бы использовали сбалансированные деревья для представления наборов - более сложным, но быстрым; фактически, именно так реализован собственный тип Set в Haskell.