Instead of attacking the problem textually, try to create a datatype which would describe your expressions, then generate all values of this datatype, filter those you don’t need, and convert the rest into Strings. Currently your expressions are represented by “String” — conversion is very cheap, but filtering is “hard” (since it boils down to parsing). Binary trees would suit you better.

The following algorithm generates all possible expressions and throws away most of unnecessary duplicates.

import qualified Data.Map as M

data Expr = Num Int | Add Expr Expr | Sub Expr Expr | Mul Expr Expr | Div Expr Expr

Rendering function is highly imperfect. Either write one yourself, or change the definition of Expr to something like “Num Int | App Op [Expr]” — this way rendering would become much easier.

render :: Expr -> String render (Num n) = show n render (Add a b) = "(" ++ render a ++ "+" ++ render b ++ ")" render (Sub a b) = "(" ++ render a ++ "-" ++ render b ++ ")" render (Mul a b) = "(" ++ render a ++ "*" ++ render b ++ ")" render (Div a b) = "(" ++ render a ++ "/" ++ render b ++ ")"

Let’s assume that we have lN numbers.

nums = [1, 2, 3] lN = length nums

Our goal is to build table of all possible expressions, which can be build using numbers from i-th to j-th, where i, j are in range from 0 to lN-1. We have to fill the table in the following order: numbers themselves, expressions consisting of two numbers, three, four, … N.

table :: M.Map (Int, Int) [Expr] table = M.fromList $ [((i, i), [Num n] ) | (i, n) <- zip [0..lN-1] nums] ++ [((i, j), calc i j) | i <- [0..lN-1], j <- [i+1,i+2..lN-1]]

answer = table M.! (0, lN-1)

Our next goal is a function which fills this table:

calc :: Int -> Int -> [Expr] calc i j = do --elements from i to k will form one branch, k+1 to j — another k <- [i,i+1..j-1] le <- table M.! (i, k) re <- table M.! (k+1, j)

We don’t want to generate both (a+b)+c and a+(b+c), or (a+b)-c and a+(b-c), or (a-b)-c and a-(b+c), or (a-b)+c and a-(b-c), so we’re eliminating the second variant in each pair. Multiplication and division follow the same pattern.

case re of Add _ _ -> [Mul le re, Div le re] Sub _ _ -> [Mul le re, Div le re] Mul _ _ -> [Add le re, Sub le re] Div _ _ -> [Add le re, Sub le re] otherwise -> [Add le re, Sub le re, Mul le re, Div le re]

Here are generated expressions: 1*(2+3) 1/(2+3) 1*(2-3) 1/(2-3) 1+(2*3) 1-(2*3) 1+(2/3) 1-(2/3) (1+2)+3 (1+2)-3 (1+2)*3 (1+2)/3 (1-2)+3 (1-2)-3 (1-2)*3 (1-2)/3 (1*2)+3 (1*2)-3 (1*2)*3 (1*2)/3 (1/2)+3 (1/2)-3 (1/2)*3 (1/2)/3