haskell set type de données

Question

Salut tout le monde je suis en train de comprendre comment faire un type de données ensemble dans haskell, mais je ne peux pas comprendre cela, c'est ce que j'ai à ce jour, je suis un peu confus

data Set a = Node a | List { 
    list :: [a] 
}deriving(Eq,Show,Ord) 

insert :: Set Integer -> Set Integer -> Bool 
insert (Node itemToInsert) (List list) 
    |contains (List list) (Node itemToInsert) == False = List(list:(Node itemToInsert)) 


contains :: Set Integer -> Set Integer -> Bool 
contains (List []) (Node numberToFind) = False 
contains (List (x:xs)) (Node numberToFind) 
    |x == (Node numberToFind) = True 
    |otherwise = contains (List (xs)) (Node numberToFind) 

Merci pour votre aide!

Answer 1

De votre code, il semble que vous avez déjà compris, qu'un ensemble peut être vu comme une liste sans doublons. Alors laissez-nous exprimer cela dans une définition de type simple:

data Set a = Set [a] 

Afin d'assurer qu'il n'y ait pas de doublons, on peut introduire des « constructeurs intelligents » qui sont des fonctions qui ne sont pas techniquement un constructeur, mais qui sont utilisés En tant que tel.

empty :: Set a 
empty = Set [] 

Nous en aurons besoin d'un autre pour créer des ensembles non vides. Jetons un coup d'oeil à votre fonction insert. Pourquoi renvoie-t-il un Bool? Ne devrait-il pas retourner un ensemble? Pourquoi insert attend deux ensembles? Donc, pour insérer un entier dans un ensemble d'entiers on pourrait vous utiliser la signature de type:

insert :: Integer -> Set Integer -> Set Integer 

La mise en œuvre se compose de deux cas: 1. l'entier donné est pas dans l'ensemble donné, et 2. la donnée entier est dans l'ensemble donné.

insert x (Set xs) 
    | not (x `elem` xs) = Set (x:xs) 
    | otherwise   = Set xs 

Depuis, cette question semble faire partie d'un devoir. Je dirais que vous devriez essayer de comprendre comment mettre en œuvre elem vous-même.