Get the n elements of the list with the highest property
I am new to Haskell and am trying to implement some genetic algorithms. I am currently failing to select the best n items of a list of persons (where each individual is a list for himself. A person is created like this:
ind1 :: [Int]
ind1 = [1, 1, 1, 1, 1, 1, 1]
ind2 :: [Int]
ind2 = [0, 0, 0, 0, 0, 0, 0]
The corresponding population consists of a list of these 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, for example
> sum ind1
7
> sum ind2
0
I started building a function to create tuples with personality and quality:
f x = [(ind, sum ind) | ind <- x]
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 the expected output from here? I can't even get the "fst" of the tuple where "snd == max" is. I started with recursive approaches as seen from different topics, but unfortunately without a reasonable result. Any suggestions maybe also where to read? Thank!
source to share
The best choice here is to use sortBy
from Data.List
:
sortBy :: (a -> a -> Ordering) -> [a] -> [a]
The function sortBy
is of a higher order, so it takes a function as one of its arguments. He needs a function that takes two elements and returns a value Ordering
( LT
, EQ
or GT
). You can write your own comparison function, but a module Data.Ord
has comparing
one that exists to help with writing these comparison functions:
comparing :: Ord b => (a -> b) -> (a -> a -> Ordering)
Hopefully, you see the comparing
pairs with sortBy
pass it a function to convert your type to a known comparable type, and then you have a function of the correct type to transition 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 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
flip
in arguments sortBy
causes the sort to descend instead of the default, so the first n
values returned from sortBy
will have the values n
with the highest match in descending order. If you want to try different fitness features, you can do something like
fittestBy :: (Individual -> Fitness) -> Int -> [Individual] -> [Individual]
fittestBy fit n = take n . sortBy (flip $ comparing fit)
Then you will have
solution2 = fittestBy sum
But you can also have
solution3 = fittestBy product
if you want to change your fitness function as a product and not an amount.
source to share