在相同数据结构上运行的相似函数

Question

我有以下形式的数据类型：

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)

我的 'main' 数据类型是解决方案。现在我想实现一些 genetic/evolutionary 算法。

这意味着我必须变异 Solution。我的大部分突变都需要对个体 trip 进行操作。

例如将a的元素取反trip。或者将周一的行程换成周二。或者甚至将解决方案 1 的周一行程与解决方案 2 的周一行程交换。

对于大多数突变，我需要执行以下步骤：

1. 我需要随机性来确定 Trip(s) 变异。
2. 改变 Trips
3. Return 更新后的解决方案

显然 (2.) 对于每个变异函数都是唯一的。但是 (1.) 和 (3.) 很相似。

在不必为每个变异函数重复步骤 1（和 3）的情况下实现它的好方法是什么？

Answer 1

概念：高阶函数

高阶函数是将另一个函数作为输入的函数。在没有意识到的情况下，您可能已经使用了几个高阶函数（例如 map 和 foldl）。

简单地使用一个高阶函数，带有签名的东西：

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

所以这里的第一个参数是一个变异旅行的函数，你的mutateGeneric函数本身生成随机数，根据函数进行修改，然后return求解。如果你不执行 IO （例如因为随机数是另外生成的），你可以简单地使用：

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

例子

假设你首先在 0 和 4（含）之间生成一个 int 来确定那一天，接下来你对那天的两次旅行进行变异，最后你 return变异的解决方案。

首先我们要定义一些实用方法：

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 }

然后突变看起来像：

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

现在修饰符可以例如将第一个与第二个 Trips 项交换：

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

最后你可以说你的修改启发式是：

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

关键是你可以简单地构造另一个修饰符，如swapModifier，并将其与mutateGeneric结合起来。当然上面的例子比较简单。此外，您可能需要更新分数和处罚。您可以在 mutateGeneric 函数中执行此操作。