Сортировка абстрактных типов данных в Haskell - PullRequest
Новая
       14

Сортировка абстрактных типов данных в Haskell

6 голосов
/ 28 апреля 2011

Например, у меня есть следующее: 

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

Если бы я хотел найти наименьшее something в базе к их первому элементу (Float) , как я мог это сделатьтот?Я объяснил это следующим образом, но я не могу понять, как его реализовать

Поскольку у меня есть список somethings, самый простой способ - создать собственную вспомогательную функцию min, котораясравнивает 2 somethings и возвращает наименьшее из двух значений.Однако он пытается сделать это «более простым способом», который застрял у меня с type ошибками компиляции ... 

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

Я не знаком с sortBy и compare on,Я только что столкнулся с подобным вопросом здесь, в SO, но мне не удалось заставить его работать.Как новичок в Haskell, есть ли другой способ приблизиться к этому?

Ответы [ 3 ]

6 голосов
/ 28 апреля 2011

Если вы хотите сравнить на основе первого поля типа данных, вы можете позволить Haskell написать для вас код: 

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

Предложение deriving указывает, какие реализации классов типов генерируются автоматическидля типа Something.Здесь мы получаем Eq, который позволяет нам спросить, равны ли два Something (например, с ==), и Ord, что позволяет нам сравнить два Something и узнать, какой из них "more ".

Поведение по умолчанию на Haskell при получении Ord заключается в сравнении каждого поля от первого к последнему, поэтому код по умолчанию начинается с сравнения первого Float каждого Something, что и являетсявы хотите.

Как только вы работаете с типом, который реализует Ord, вы можете использовать всевозможные встроенные функции, такие как minimum :: Ord a => [a] -> a.Это берет список любого типа, который реализует Ord, и возвращает наименьший элемент.Итак, в качестве примера: 

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

smallest = minimum [st1,st2]
5 голосов
/ 28 апреля 2011

Использование пользовательского типа data обычно является лучшим вариантом, но если вы действительно хотите использовать кортежи, вы можете начать с определения вспомогательной функции comparingFst, которая сравнивается на основе первого элемента кортежа. 

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

Теперь вы можете взять меньший из двух элементов: 

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

или из списка элементов 

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

И вы также можете использовать ту же вспомогательную функцию для сортировки: 

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

Также стоит упомянуть, что по умолчанию кортежи сравниваются поэлементно, начиная с первого элемента, поэтому при условии, что ваши типы Aa и Bb могут быть получены из Ord и Eq, вы не нужно ничего лишнего, т.е. пример становится: 

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

Другими словами, вы можете просто использовать стандартные функции min и sort как есть.

5 голосов
/ 28 апреля 2011

Во-первых, у вас есть некоторые синтаксические ошибки.

Вы можете сделать две вещи.Во-первых, следуя модели использования функции доступа для доступа к нужному полю (fst), мы можем определить метки для полей вашего типа: 

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

, а затем отсортировать по field_x

import Data.List
import Data.Function

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

получение минимума равнозначно снятию головы с отсортированного списка: 

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

альтернативно, вы можете написать собственный экземпляр Ord для SomethingТип, который сравнивает значения только с использованием field_x, затем обычные sort и minimum (и другие функции Ord), будет "просто работать".

...