haskell - Haskell 中的遗传编程

Question

例如，有 GenProg (http://hackage.haskell.org/package/genprog)，但它只处理数值优化，在这种情况下找到一个描述数据的方程。

但我需要 for 循环、if 语句、when 语句、 bool 检查等。我需要能够生成命令式结构。对此有什么想法吗？到目前为止，我最好的选择似乎是 husk-scheme，我可以在 Haskell 中将 Scheme 代码作为 DSL 运行。肯定有更好的方法吗？

Answer 1

如果您正在寻找类似于 S 表达式的东西，这很容易在 Haskell 中建模。比如说，我们想用变量来表示简单的代数方程，比如

x + 5 / (y * 2 - z)

这可以用 Haskell 中的简单 AST 来表示，特别是我们可以将其实现为

data Expr
    = Lit Double        -- Literal numbers
    | Var Char          -- Variables have single letter names
    | Add Expr Expr     -- We can add things together
    | Sub Expr Expr     -- And subtract them
    | Mul Expr Expr     -- Why not multiply, too?
    | Div Expr Expr     -- And divide
    deriving (Eq)

这将使我们将上面的等式表示为

Add (Var 'x') (Div (Lit 5) (Sub (Mul (Var 'y') (Lit 2)) (Var 'z')))

但这写起来相当笨重，而且难以阅读。让我们从工作开始 Show魔术使它打印得很漂亮:

instance Show Expr where
    showsPrec n (Lit x)   = showParen (n > 10) $ showsPrec 11 x
    showsPrec n (Var x)   = showParen (n > 10) $ showChar x
    showsPrec n (Add x y) = showParen (n >  6) $ showsPrec 7 x . showString " + " . showsPrec 7 y
    showsPrec n (Sub x y) = showParen (n >  6) $ showsPrec 7 x . showString " - " . showsPrec 7 y
    showsPrec n (Mul x y) = showParen (n >  7) $ showsPrec 8 x . showString " * " . showsPrec 8 y
    showsPrec n (Div x y) = showParen (n >  7) $ showsPrec 8 x . showString " / " . showsPrec 8 y

如果您不了解这里发生的所有事情，那没关系，一些内置函数可以很容易地使很多复杂化变得容易，这些函数可以有效地正确构建带有括号的字符串以及所有有趣的东西。它几乎是从 Text.Show 中的文档中复制出来的。 .现在如果我们从上面打印出我们的表达式，它看起来像

x + 5.0 / (y * 2.0 - z)

现在简化构建这些表达式。由于它们几乎是数字，我们可以实现 Num ( abs 和 signum 除外)和 Fractional :

instance Num Expr where
    fromInteger = Lit . fromInteger
    (+) = Add
    (-) = Sub
    (*) = Mul
    abs = undefined
    signum = undefined

instance Fractional Expr where
    (/) = Div
    fromRational = Lit . fromRational

现在我们可以从上面输入表达式为

Var 'x' + 5 / (Var 'y' * 2 - Var 'z')

即使我们必须手动指定变量，这至少更容易在视觉上解析。

现在我们已经有了漂亮的输入和输出，让我们专注于评估这些表达式。由于我们在这里有变量，我们需要某种将变量与值相关联的环境

import Data.Map (Map)
import qualified Data.Map as M

type Env = Map Char Double

现在它只是基本的模式匹配(以及辅助函数)

import Control.Applicative

binOp :: (Double -> Double -> Double) -> Expr -> Expr -> Env -> Maybe Double
binOp op x y vars = op <$> evalExpr x vars <*> evalExpr y vars

evalExpr :: Expr -> Env -> Maybe Double
evalExpr (Lit x)   = const $ Just x
evalExpr (Var x)   = M.lookup x
evalExpr (Add x y) = binOp (+) x y
evalExpr (Sub x y) = binOp (-) x y
evalExpr (Mul x y) = binOp (*) x y
evalExpr (Div x y) = binOp (/) x y

现在我们可以使用 evalExpr用变量替换来评估我们的迷你语言中的表达式。如果有一个 undefined variable ，所有的错误处理都是由 Maybe 完成的。 monad，我们甚至可以通过隐含环境参数来减少重复。这对于简单的表达式 DSL 来说都是非常标准的。

因此，为了有趣，生成随机表达式和(最终)突变。为此，我们需要 System.Random .我们希望能够生成不同复杂度的表达式，因此我们将粗略地表达它。由于它是随机的，我们有可能得到比指定的更短或更深的树。这可能是您想要调整和调整以获得所需结果的东西。首先，因为我已经有先见之明已经编写了这段代码，所以让我们定义两个帮助器来生成随机文字和随机变量:

randomLit, randomVar :: IO Expr
randomLit = Lit <$> randomRIO (-100, 100)
randomVar = Var <$> randomRIO ('x',  'z')

这里没有什么令人兴奋的，我们得到-100 到 100 之间的 double 数，以及最多 3 个变量。现在我们可以生成大型表达式树。

generateExpr :: Int -> IO Expr
-- When the depth is 1, return a literal or a variable randomly
generateExpr 1 = do
    isLit <- randomIO
    if isLit
        then randomLit
        else randomVar
-- Otherwise, generate a tree using helper
generateExpr n = randomRIO (0, 100) >>= helper
    where
        helper :: Int -> IO Expr
        helper prob
            -- 20% chance that it's a literal
            | prob < 20  = randomLit
            -- 10% chance that it's a variable
            | prob < 30  = randomVar
            -- 15% chance of Add
            | prob < 45  = (+) <$> generateExpr (n - 1) <*> generateExpr (n - 1)
            -- 15% chance of Sub
            | prob < 60  = (-) <$> generateExpr (n - 1) <*> generateExpr (n - 1)
            -- 15% chance of Mul
            | prob < 75  = (*) <$> generateExpr (n - 1) <*> generateExpr (n - 1)
            -- 15% chance of Div
            | prob < 90  = (/) <$> generateExpr (n - 1) <*> generateExpr (n - 1)
            -- 10% chance that we generate a possibly taller tree
            | otherwise = generateExpr (n + 1)

该函数的大部分内容只是指定生成给定节点的概率，然后为每个算子生成左右节点。由于我们重载了 Num，我们甚至不得不使用普通的算术运算符。 ，多么得心应手!

现在，请记住，我们仍然可以对 Expr 的构造函数进行模式匹配。 type 用于其他操作，例如替换节点、交换节点或测量深度。为此，您只需将其视为 Haskell 中的任何其他二叉树类型，除了它有 2 个叶构造函数和 4 个节点构造函数。至于突变，您必须编写遍历此结构并选择何时换出节点以及用什么换出它们的代码。它将住在 IO monad，因为您将生成随机值，但这应该不会太难。这个结构应该很容易根据需要进行扩展，比如如果你想添加三角函数和求幂，你只需要更多的构造函数， evalExpr 中的更多表达式，以及 helper 中的相应子句，以及一些概率调整。

您可以获取此示例的完整代码 here .希望这可以帮助您了解如何在 Haskell 中制定类似 S 表达式的内容。