Sorting abstract datatypes in Haskell

Question

For example I have the following,

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

If I were to desire to find the smallest something in base to their first element (Float) how could I do that? The way I have reasoned it is the following, yet I cant manage to figureout how to implement it

Because I have a list of somethings the easiest way should be to create my own min helper function that compares 2 somethings and returns the smallest of the two. However it is trying to do that "easier way" that got me stuck with type compile errors...

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

I am not familiar with sortBy and compare on, I just came across a similar question here in SO but I couldnt manage to make it work. As a beginner in Haskell, is there another way to approaching this?.

Answer 1

If you want to compare based on the first field of a data type, you can let Haskell write the code for you:

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

The deriving clause specifies which type classes implementations are automatically generated for the Something type. Here, we derive Eq which allows us to ask whether two Somethings are equal (e.g., with ==), and Ord, which allows us to compare two Somethings and know which one is "greater".

Haskell's default behavior when deriving Ord is to compare each field from first to last, so the default code will start by comparing the first Float of each Something, which is exactly what you want.

Once you're dealing with a type that implements Ord, you can use all sorts of built-in functions like minimum :: Ord a => [a] -> a. This takes a list of any type that implements Ord, and gives back the smallest element. So, as an example:

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

Using a custom data type is usually the better option, but if you really want to use tuples, you can start by defining a helper function comparingFst that compares based on the first element of the 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

Now you can take the smaller of two elements with:

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

or from a list of elements

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

And you can also use the same helper function for sorting:

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

Also, it's worth mentioning that tuples are, by default, compared element-wise, starting from the first element, so assuming your Aa and Bb types can be derived from Ord and Eq, you don't need anything extra, i.e. the example becomes:

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

In other words, you can just use the standard min and sort functions as-is.

Answer 3

You have some syntax errors, firstly.

There are two things you can do. Firstly, following the model of using an accessor function to get at the field you want (fst), we can define labels for the fields of your type:

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

and then sort on field_x

import Data.List
import Data.Function

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

getting at the mimimum is the same as taking the head off the sorted list:

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

alternatively, you can write a custom Ord instance for the Something type that compares values only using field_x, then regular sort and minimum (and other Ord-based functions), will "just work".