[Haskell-cafe] Abstracting a Genetic Algorithm

Alex Good alexjsgood at gmail.com
Wed Feb 16 00:35:39 CET 2011

I've copied this from
as someone suggested that it might spark an interesting discussion

I'm new to the world of Haskell programming and I'm cutting my teeth
on a simple genetic algorithm for finding good solutions to the
Travelling Salesman problem. I am representing the solutions as
permutations on Integers and so I have this type synonym

type Genome = [Int]

The algorithm itself is a set of functions which operate on the solutions:

mutation :: Genome -> Genome
selectParents :: [Genome] -> [Genome] -> [Genome]
crossover :: Genome -> Genome -> (Genome, Genome)
selectSurvivors :: [Genome] -> [Genome] -> [Genome]

I'm not sure how much of my code is relevant to my question so please
ask if more details are needed. One thing that might be worth
mentioning is that the type signatures above are actually simplified,
I am in fact using the State monad to carry around an StdGen so all of
these functions actually return stateful computations.

There are several things which I would like to do with this but can't
quite get my head around. I want to make it possible to choose
different representations for the solutions, it seems to me that this
would be a natural place to use a type class, so that Genome would be
the type class and [Int] a specific instance of this Genome.

Now, I want to be able to experiment with the implementations, and I
want to be able to use the code in other projects. Using a type class
like this would require that every new algorithm I create would
require me to create another instance of Genome, is this a good way to
go about creating a library?

One bonus question, just a thing that's been bothering me, is there
any way to create something like a type synonym for a function so that
if I'm writing a function which takes functions as arguments I can
write the synonym rather than the whole type signature of the function
i.e so that something like the following would work.

type someFunc = [Int] -> [Int] -> Int
someOtherFunc :: someFunc -> [Int] -> Int

Right, hopefully that's a lucid enough explanation of the problem,
feel like I've missed the really obvious answer but it hasn't jumped
out at me. Cheers

More information about the Haskell-Cafe mailing list