Création d'une nouvelle instance Ord pour les listes

Question

Ceci est ma première tentative de création d'une instance personnalisée d'une classe telle que Ord.

J'ai défini une nouvelle structure de données pour représenter une liste:

data List a = Empty | Cons a (List a) 
    deriving (Show, Eq) 

Maintenant, je veux définir une nouvelle instance de Ord Liste telle que la liste a < = Liste b implique « la somme des les éléments de la liste a sont inférieurs ou égaux à la somme des éléments de la liste b "

tout d'abord, est-il nécessaire de définir une nouvelle fonction" somme "puisque la somme définie dans Prelude ne fonctionnera pas avec la nouvelle liste Type de données? alors, comment définir la nouvelle instance d'Ord for List?

grâce

Answer 1

Tout d'abord, cela ne fonctionnera pas exactement comme l'instance de la liste normale. L'instance normale ne dépend que des éléments de la liste pouvant être commandés eux-mêmes; votre proposition dépend de leur nombre (par exemple dans la classe Num) et est donc plus étroite.

Il est nécessaire de définir une nouvelle fonction sum. Heureusement, il est très facile d'écrire sum comme une simple fonction récursive. (Par pure coïncidence, vous pouvez appeler votre fonction sum', qui est prononcé comme « prime somme » et par convention signifie qu'il est une fonction très similaire à sum.)

En outre, l'instance devrait dépendre de la classe Num ainsi que la classe Ord.

Une fois que vous avez une nouvelle fonction sum, vous pouvez définir une chose par exemple comme ceci:

instance (Ord n, Num n) => Ord (List n) where compare = ... 
    -- The definition uses sum' 

Cette déclaration d'instance peut être lu en disant que pour tous les types n, si n est en Ord et Num, List n est dans Ord où des comparaisons fonctionnent comme suit. La syntaxe est très similaire à mathématique où => est implication. Espérons que cela facilite la mémorisation de la syntaxe.

Vous devez donner une définition raisonnable de compare. Pour référence, compare a b fonctionne comme suit: si a < b il renvoie LT, si a = b il renvoie EQ et si a > b il renvoie GT.

Ceci est une fonction facile à mettre en œuvre, donc je vais le laisser comme un exercice au lecteur. (J'ai toujours voulu dire ça: P).

Answer 2

Généralisation @ approche de Tikhon un peu, vous pouvez également utiliser Monoid au lieu de Num comme une contrainte, où vous avez déjà une « somme » prédéfinie avec mconcat (bien sûr, vous avez encore besoin Ord). Cela vous donner quelques types en considération que des chiffres (par exemple List (List a), que vous pouvez facilement définir récursive)

D'autre part, si vous faire voulez utiliser un Num comme monoid, vous devez décider chaque fois pour Sum ou Product.On pourrait soutenir que le fait d'écrire explicitement cela peut réduire la brièveté et la lisibilité, mais c'est un choix de conception qui dépend du degré de généralité que vous voulez avoir à la fin.

Answer 3

Que diriez-vous ...

newtype List a = List [a] 

Ceci est très fréquent si vous voulez introduire de nouvelles, des instances de classe de type « incompatible » pour un type donné (voir, par exemple ZipList ou plusieurs monoïdes comme Sum et Product)

Maintenant, vous pouvez facilement réutiliser les instances pour la liste, et vous pouvez également utiliser sum.

Answer 4

.. Qu'en est-

data List a = Empty | Cons a (List a) 
       deriving (Show, Eq) 


instance (Ord a, Num a, Eq a) => Ord (List a) where 

     -- 2 empty lists 

     Empty <= Empty   = True 

     -- 1 empty list and 1 non-empty list 

     Cons a b <= Empty   = False 
     Empty <= Cons a b   = True 

     -- 2 non-empty lists 

     Cons a b <= Cons c d  = sumList (Cons a b) <= sumList (Cons c d) 


-- sum all numbers in list 

sumList   ::  (Num a) => List a -> a 

sumList Empty    =  0 
sumList (Cons n rest)  =  n + sumList rest 

Est-ce que vous cherchez?

Answer 5

.. ou une autre solution avec la fonction sum dans Prelude.

data List a = Empty | Cons a (List a) 
       deriving (Show, Eq) 


instance (Ord a, Num a, Eq a) => Ord (List a) where 

     -- 2 empty lists 

     Empty <= Empty   = True 

     -- 1 empty list and 1 non-empty list 

     Cons a b <= Empty   = False 
     Empty <= Cons a b   = True 

     -- 2 non-empty lists 

     Cons a b <= Cons c d  = sum (listToList (Cons a b)) 
               <= sum (listToList (Cons c d)) 


-- convert new List to old one 

listToList  ::  (Num a) => List a -> [a] 

listToList Empty    =  [] 
listToList (Cons a rest)  =  [a] ++ listToList rest