haskell - Clean way to do rewrite rules -

i have following toy language:

module lang  data op = move int -- move pointer n steps         | add  int -- add n value under pointer         | skip     -- skip next op if value under pointer 0         | halt     -- end execution         deriving (show, eq)  type program = [op] 

the language has finite tape of memory cells wraps around, , pointer points @ cell. cells zero. program executed repeatedly until halt instruction read.

now write function optimizes given program. here optimizations perform:

| original code       | optimization   | |---------------------|----------------| | move : move b : x | move (a+b) : x | | add  : add  b : x | add  (a+b) : x | | move 0 : x          | x              | | add  0 : x          | x              | | skip : skip : x : y | x : y          | | halt : _            | halt           | 

additionally, can optimization on code not directly after skip, because doing change meaning of program.

is repeatedly pattern matching on list until no more optimizations can performed best/cleanest way this?

what if decide want perform more advanced rewrites these:

| original code                                          | optimization                                   | |--------------------------------------------------------|------------------------------------------------| | if program begins (skip : a)                  | move end of program              | | move x ++ no_skips : move -x ++ no_skips' : move w : q | move x ++ no_skips ++ no_skips' : move w-x : q | 

use maybe's!

@user2407038 told me use maybe in comment

module maybeprog  import lang import control.monad  type opt = program -> maybe program  optimize = untilfail step   step p | p' <- ateverybutskipnextwhen (==skip) rewrite                      . atevery   delnopskip                      $ untilfail moveskips p                , p /= p' = p'                | otherwise = nothing         rewrite = tryall [joinmoves, joinadds, delnopmov, delnopadd, termhalt, reorder]  joinmoves  p = (move : move b : x) <- pure p; $ move (a+b) : x joinadds   p = (add  : add  b : x) <- pure p; $ add  (a+b) : x delnopmov  p = (move 0          : x) <- pure p; x delnopadd  p = (add  0          : x) <- pure p; x delnopskip p = (skip   : skip   : x) <- pure p; x termhalt   p = (halt            : _) <- pure p; [halt] moveskips  p = (skip   : x : y  : z) <- pure p; $ y : z ++ [skip, x]  reorder p =   (move x : rst)      <- pure p   (as, move y : rst') <- break' ismove rst   guard $ x == -y && (/=skip)   (bs, move w :   q ) <- break' ismove rst'   guard $ (/=skip) bs   return $ move x : ++ bs ++ move (w-x) : q  ismove (move _) = true        ismove _        = false  --------  untilfail :: opt -> program -> program untilfail o p | p' <- o p = untilfail o p'               | otherwise   = p  atevery :: opt -> program -> program atevery o p | (x:xs) <- untilfail o p = x : atevery o xs             | otherwise               = []  ateverybutskipnextwhen c o p@(h:_)   | not $ c h   , (x:xs) <- untilfail o p = x : ateverybutskipnextwhen c o xs   | (p1:p2:ps) <- p = p1:p2:ateverybutskipnextwhen c o ps   | otherwise = p ateverybutskipnextwhen _ _ [] = []  tryall :: [opt] -> opt tryall os p =   x : _ <- pure . dropwhile (==nothing) $ ($p) <$> os   return x  break' f p | (x, y) <- break f p            , not $ null y = (x, y)            | otherwise = nothing