Geek Answers Handbook

Genetic programming in Haskell

There is GenProg ( http://hackage.haskell.org/package/genprog ), but this only applies to numerical optimization, in this case finding an equation that describes the data.

But I demand for cycles, if instructions, when statements, logical checks, etc. I need to be able to generate imperative structures. Any thought on this? My best options so far seem like a husk scheme, where I can run the scheme code as DSL in Haskell. Surely there should be better ways?

+4
source share
1 answer

If you are looking for something similar to S-expressions, this is pretty easy to model in Haskell. Say, for example, we want to represent simple algebraic equations with variables, such as

x + 5 / (y * 2 - z)

This can be represented by a simple AST in Haskell, in particular we can implement it as

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)

This would allow us to express the expression above as

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

But it is rather inconvenient to write and read difficult. Start by working with magic Showto make it pretty printed:

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

If you don’t understand that everything happens here, this is normal, many complications are simplified thanks to some built-in functions for efficiently constructing strings with parentheses in them properly and all these funny things. To a large extent, it is copied from documents to Text.Show. Now, if we print our expression on top, it will look like

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 - . , Maybe undefined, , . DSL.

, , ( ) . System.Random. , . , , , . , , , . -, , , :

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

, -100 100 . .

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 a literal
            | prob < 20  = randomLit
            -- 10% chance that it 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)

- , node, . , Num, !

, - Expr , , . Haskell, , 2 4 node. , , , . IO, , . , , , , evalExpr helper, .

. , , - S- Haskell.

+8

More articles:


All Articles