Tri des types de données abstraites en Haskell

Question

Par exemple, j'ai les éléments suivants,

type something = (Float, Float, Int, Aa, Bb, Cc, Int)

Si je devais désirer trouver le plus petit something en base à leur premier élément (Flottant) comment pourrais-je faire ça ? Le raisonnement que j'ai suivi est le suivant, mais je n'arrive pas à trouver comment le mettre en œuvre.

Parce que j'ai une liste de somethings le moyen le plus simple serait de créer mon propre min fonction d'aide qui compare 2 somethings et renvoie le plus petit des deux. Cependant, c'est en essayant de faire cette "manière plus facile" que je me suis retrouvé coincé avec type erreurs de compilation...

findMin :: something -> something -> somthing
findMin x y = sortBy (compare `on` fst) x y

Je ne suis pas familier avec sortBy y compare on Je viens de tomber sur une question similaire ici dans SO mais je n'ai pas réussi à la faire fonctionner. En tant que débutant en Haskell, y a-t-il une autre façon d'aborder cette question ?

Answer 1

Si vous souhaitez effectuer une comparaison basée sur le premier champ d'un type de données, vous pouvez laisser Haskell écrire le code pour vous :

data Something = Something Float Float Int String Bool Char Int
               deriving (Eq, Ord)

Le site deriving spécifie les implémentations des classes de type qui sont automatiquement générées pour le projet Something type. Ici, nous dérivons Eq ce qui nous permet de demander si deux Something sont égales (par exemple, avec des == ), et Ord qui nous permet de comparer deux Something et savoir lequel est "le plus grand".

Le comportement par défaut de Haskell lors de la dérivation Ord est de comparer chaque champ du premier au dernier, donc le code par défaut commencera par comparer le premier Float de chaque Something ce qui est exactement ce que vous voulez.

Une fois que vous avez affaire à un type qui implémente Ord vous pouvez utiliser toutes sortes de fonctions intégrées telles que minimum :: Ord a => [a] -> a . Ceci prend une liste de n'importe quel type qui implémente Ord et rend le plus petit élément. Donc, à titre d'exemple :

st1 = Something 3.14 2.72 7 "hello" False 'λ' 42
st2 = Something 3.15 2.72 7 "hello" False 'λ' 42

smallest = minimum [st1,st2]

Answer 2

Vous avez quelques erreurs de syntaxe, tout d'abord.

Il y a deux choses que vous pouvez faire. Premièrement, en suivant le modèle de l'utilisation d'une fonction accesseur pour obtenir le champ que vous voulez ( fst ), nous pouvons définir des étiquettes pour les champs de votre type :

data Something = Something { field_x, field_y :: Float,
                             field_z    :: Int }

et ensuite trier sur field_x

import Data.List
import Data.Function

sortSomethings :: [Something] -> [Something]
sortSomethings = sortBy (compare `on` field_x)

obtenir le mimimum revient à enlever la tête de la liste triée :

minSomethings  :: [Something] -> Something
minSomethings  = head . sortSomethings

Alternativement, vous pouvez écrire un Ord instance pour le Something qui compare les valeurs uniquement en utilisant field_x alors, régulier sort y minimum (et autres Ord -), fonctionneront "tout simplement".

Answer 3

Utilisation d'un data est généralement la meilleure option, mais si vous voulez vraiment utiliser les tuples, vous pouvez commencer par définir une fonction d'aide comparingFst qui compare sur la base du premier élément du tuple.

import Data.Ord
import Data.List

-- Dummy data types for example purposes. Derive from Show just so
-- that the example can be more easily tested interactively in ghci.
data Aa = Aa deriving Show
data Cc = Cc deriving Show

type Something = (Float, Float, Int, Aa, Cc, Int)

comparingFst :: Something -> Something -> Ordering
comparingFst = comparing fstSomething
    where fstSomething (x,_,_,_,_,_) = x

Vous pouvez maintenant prendre le plus petit de deux éléments avec :

findMin :: Something -> Something -> Something
findMin x y = case comparingFst x y of
    LT -> x
    _  -> y

ou à partir d'une liste d'éléments

findMinimum :: [Something] -> Something
findMinimum = minimumBy comparingFst

Et vous pouvez également utiliser la même fonction d'aide pour le tri :

sortSomethings :: [Something] -> [Something]
sortSomethings = sortBy comparingFst

Il convient également de mentionner que les tuples sont, par défaut, comparés par élément, en commençant par le premier élément. Aa y Bb peuvent être dérivés de Ord y Eq vous n'avez besoin de rien d'autre, c'est-à-dire que l'exemple devient :

import Data.List

data Ab = Ab deriving (Show, Ord, Eq)
data Cc = Cc deriving (Show, Ord, Eq)

type Something = (Float, Float, Int, Ab, Cc, Int)

findMin :: Something -> Something -> Something
findMin x y = min x y

findMinimum :: [Something] -> Something
findMinimum = minimum

sortSomethings :: [Something] -> [Something]
sortSomethings = sort

En d'autres termes, vous pouvez simplement utiliser l'option standard min y sort fonctionne en l'état.