CODEWITHSUNDEEP
haskellcode-duplication
Richard Deurwaarder
Richard Deurwaarder

Reputation: 2040

Similar functions operating on the same datastructure

I've got a data type of the following form:

type Orders                 = [Int]
data Score                  = Score Cost Penalty Penalty
type Trip                   = (Int, Cost, Orders)
type Trips                  = [Trip]
type DaySolution            = (Trips, Trips)
data Solution               = Solution { score         :: Score,
                                         skippedOrders :: Orders,
                                         monday        :: DaySolution,
                                         tuesday       :: DaySolution,
                                         wednesday     :: DaySolution,
                                         thursday      :: DaySolution,
                                         friday        :: DaySolution
                              } deriving(Show)

My 'main' datatype is solution. Now I want to implement some genetic/evolutionary algorithm.

This means I have to mutate Solution. Most of my mutations will need to operate on individual trip's.

For example, reverse the elements of a trip. Or Swap the trips of monday with tuesday. Or even swap the monday trips of solution 1 with the monday trips of solution 2.

For most mutations I need the following steps:

  1. I need randomness to determine what Trip(s) to mutate.
  2. Mutate the Trips
  3. Return the updated solution

Obviously (2.) would be unique for each mutation function. But (1.) and (3.) are quite similar.

What is a good way of implementing this without having to duplicate steps 1 (and 3) for each mutation function?

Upvotes: 0

Views: 55

Answers (1)

willeM_ Van Onsem
willeM_ Van Onsem

Reputation: 477200

Concept: higher order functions

A higher order function is a function that takes as input another function. Without realizing, you have probably used several higher order functions already (like map and foldl).

Simply use a higher order function, something with signature:

mutateGeneric :: (Trip -> IO Trip) -> Solution -> IO Solution

so here the first argument is a function to mutate a trip, and your mutateGeneric function itself generates random numbers, performs a modification based on the function, and then returns the solution. If you do not perform IO (for instance because random numbers are generate otherwise), you can simply use:

mutateGeneric :: (Trip -> Trip) -> Solution -> Solution

Example

Say you first generate an int between 0 and 4 (inclusive) to determine the day, next you mutate both trips of that day, and finally you return the mutated solution.

First we are going to define some utility methods:

getDay :: Int -> Solution -> DaySolution
getDay 0 = monday
getDay 1 = tuesday
getDay 2 = wednesday
getDay 3 = thursday
getDay 4 = friday

setDay :: Int -> Solution -> DaySolution -> Solution
setDay 0 s d = s { monday = d }
setDay 1 s d = s { tuesday = d }
setDay 2 s d = s { wednesday = d }
setDay 3 s d = s { thursday = d }
setDay 4 s d = s { friday = d }

Then mutation looks like:

mutateGeneric modifier solution = do
    di <- randomIO :: IO Int
    tam <- modifier ta
    tbm <- modifier tb
    return $ setDay day solution (tam,tbm)
        where day = mod day 5
              (ta,tb) = getDay day solution

and now a modifier could for instance swap the first with the second Trips item:

swapModifier :: Trips -> IO Trips
swapModifier (a:b:s) = return (b:a:s)
swapModifier x = return x

Then finally you can say that your modification heurstic is:

heuristic1 :: Solution -> IO Solution
heuristic1 = mutateGeneric swapModifier

The point is that you can simply construct another modifier like swapModifier and combine it with mutateGeneric. Of course the example above is rather simple. Furthermore perhaps you need to update scores and penalties. This you can do in the mutateGeneric function.

Upvotes: 3

Related Questions