Get n elements of list having the highest property

Question

I'm new to Haskell and trying to implement some genetic algorithms. Currently I fail with the selection of the n best element of a list of individuals (where each individual is a list for itself. An individual is created as follows:

ind1 :: [Int]
ind1 = [1, 1, 1, 1, 1, 1, 1]
ind2 :: [Int]
ind2 = [0, 0, 0, 0, 0, 0, 0]

The appropriate population consists of a list of those individuals:

pop :: [[Int]]
pop = [ind1, ind2]

What I want to achieve is to get the best n individuals of the population, where the "best" is determined by the sum of its elements, e.g.,

> sum ind1
7
> sum ind2
0

I started creating a function for creating tuples with individual and its quality:

f x = [(ind, sum ind) | ind <- x]

so at least I got something like this:

[([1, 1, 1, 1, 1, 1, 1], 7), ([0, 0, 0, 0, 0, 0, 0], 0)]

How do I get from here to the expected result? I do not even manage to get the "fst" of the tuple where "snd == max". I started with recursive approaches as seen in different topics, but unfortunately without reasonable result. Any suggestions, probably also where to read? Thank you!

Answer 1

The best choice here is to use sortBy from Data.List:

sortBy :: (a -> a -> Ordering) -> [a] -> [a]

The sortBy function is higher order, so it takes a function as one of its arguments. The function it needs is one that takes two elements and returns a Ordering value (LT, EQ or GT). You can write your own custom comparison function, but the Data.Ord module has comparing, which exists to help with writing these comparison functions:

comparing :: Ord b => (a -> b) -> (a -> a -> Ordering)

Hopefully you can see how comparing pairs with sortBy, you pass it a function to convert your type to a known comparable type, and then you have a function of the right type to pass to sortBy. So in practice you can do

import Data.List (sortBy)
import Data.Ord (comparing)

-- Some types to make things more readable
type Individual = [Int]
type Fitness = Int

-- Here's our fitness function (change as needed)
fitness :: Individual -> Fitness
fitness = sum

-- Redefining so it can be used with `map`
f :: Individual -> (Individual, Fitness)
f ind = (ind, fitness ind)

-- If you do want to see the fitness of the top n individuals
solution1 :: Int -> [Individual] -> [(Individual, Fitness)]
solution1 n inds = take n $ sortBy (flip $ comparing snd) $ map f inds

-- If you just want the top n individuals
solution2 :: Int -> [Individual] -> [Individual]
solution2 n inds = take n $ sortBy (flip $ comparing fitness) inds

The flip in the arguments to sortBy forces the sort to be descending instead of the default ascending, so the first n values returned from sortBy will be the n values with the highest fitness in descending order. If you wanted to try out different fitness functions then you could do something like

fittestBy :: (Individual -> Fitness) -> Int -> [Individual] -> [Individual]
fittestBy fit n = take n . sortBy (flip $ comparing fit)

Then you'd have

solution2 = fittestBy sum

But you could also have

solution3 = fittestBy product

if you wanted to change your fitness function to be the product rather than the sum.