Prefix Evaluation of a Chromosome in Haskell

My HGEP project is focusing on PGEP right now, though there is no reason not to add karva notation later on. One reason I'm doing prefix first is that there is no need to be aware of the structure of a chromosome, except a very simple validity check to ensure we never make any illegal individuals (illegal in the sense that they do not encode any expression tree). I've finished the prefix evaluation code, and I liked it enough to post about it.

The code involves evaluating a list of operations. The operations are defined like so

data OP a = OP { arity::Int, applyOp::[a]->a }

Each on is a function of some arity and takes a list of arguments- hopefully with length >= arity.One nice thing about prefix notation is that (as mentioned in the original PGEP paper) there is no need to actually create an expression tree- the operations can be evaluated as a list. The only complication is that the operations must "eat" their arguments off the list. Constants and variables are removed from the list and their values returned, but an operation like "+" must evaluate its first argument, then its second argument before returning their sum. The second evaluation must evaluate the list left over from the first evaluation. Hopefully some of that makes sense.

And without further attempts at explanation- here is some code:

prefix :: [OP a] -> a
prefix (op:ops) = evalState (prefixEval op) ops

prefixEval :: OP a -> State [OP a] a
prefixEval (OP 0 fn) = return $ fn []
prefixEval op = do
  args <- evalArgs (arity op)
  return $ applyOp op args

evalArgs :: Int -> State [OP a] [a]
evalArgs 0 = return []
evalArgs n = do
  (op:ops) <-get
  put ops
  arg <- prefixEval op
  args <- evalArgs (n-1)
  return $ arg : args

Notice that it is a mutual recursion that allows us to take the list apart and eval each argument. This reminds me of the metacircular interpreter for lisp (eval apply). Also notice that the problem of having to evaluate only the part of the list not yet inspected is done by making explicit that the list is the state of the computation. I like how we have to be so explicit about the type of computation we are performing.

In another post I hope to talk about symbolic regression and different ways to implement it is Haskell.