Hi, You can make a datatype that captures exactly the expressions you want (see code below). Essentially you want to make sure that a subtraction or addition never has another subtraction or addition as its left operand. I would also like to advertise a bit and show how this type can be enumerated automatically by Feat ( http://hackage.haskell.org/package/testing-feat). Main> nvars 3 (24,[X/X-X,X*X-X,X/X+X,X*X+X,X-X-X,X-X+X,X-X/X,X-X*X,X+X-X,X+X+X,X+X/X,X+X*X,(X-X)/X,(X+X)/X,(X-X)*X,(X+X)*X,X/(X-X),X/(X+X),X/X/X,X/X*X,X*(X-X),X*(X+X),X*X/X,X*X*X]) (Obviously the Xs need to be replaced by proper variables, I can explain how that's done if anyone wants to know) 24 is the number of values in the list, you can do fst $ nvars 100 to find out that there are 317334467851069836531554283592442220021116 711774843850938552230690568780568787114173 2912210230558851072 values with 100 variables. You can even select any one of those values by index or randomly select values with uniform distribution and use it with QuickCheck (for instance to test that my experiments with showsPrec hasn't messed everything up). Pasted code: http://hpaste.org/77898 {-# LANGUAGE TemplateHaskell, DeriveDataTypeable #-} import Test.Feat import Data.Typeable -- | Any expression data AnyExpr = AnyAddSub AddSub | AnyMulDiv MulDiv | AnyVar deriving Typeable -- | Expressions with a top level addition or subtraction data MulDiv = MDOp Bool AddSub AnyExpr -- Left operand is add. or sub. | MDOpVar Bool AnyExpr -- Left operand is a variable deriving Typeable -- | Expressions with a top level multiplication or division data AddSub = ASOp Bool MulDiv AnyExpr -- Left operand is mult. or div. | ASOpVar Bool AnyExpr -- Left operand is a variable deriving Typeable deriveEnumerable ''AnyExpr deriveEnumerable ''AddSub deriveEnumerable ''MulDiv allExpressions = values :: [(Integer,[AnyExpr])] nvars n = allExpressions !! ((n-1)*3+1) instance Show AnyExpr where showsPrec d (AnyAddSub e) = showsPrec d e showsPrec d (AnyMulDiv e) = showsPrec d e showsPrec _ (AnyVar) = ("X"++) instance Show AddSub where showsPrec d (ASOpVar b e) = showParen (d > 6) $ ("X"++) . ((if b then "+" else "-")++) . showsPrec 6 e showsPrec d (ASOp b e1 e2) = showParen (d > 6) $ showsPrec 6 e1 . ((if b then "+" else "-")++) . showsPrec 6 e2 instance Show MulDiv where showsPrec d (MDOpVar b e) = showParen (d > 7) $ ("X"++) . ((if b then "*" else "/")++) . showsPrec 7 e showsPrec d (MDOp b e1 e2) = showParen (d > 7) $ showsPrec 7 e1 . ((if b then "*" else "/")++) . showsPrec 7 e2 On 18 November 2012 20:31, Rune Harder Bak wrote:

On Sun, Nov 18, 2012 at 2:04 PM, Stefan Klinger wrote:

...

Sounds like you would want to enumerate all possible *abstract* syntax trees, these implicitly have exactly the necessary parentheses. I'd do this recursively, splitting the sequence of numbers in two at all possible places, and then combine the corresponding results with all possible operators.

That was my second idea, but just doing it naively resulted in many equivalent calculations, so I thought there might be a better way to view the problem. But as Artyom showed

On Sat, Nov 17, 2012 at 11:37 PM, Artyom Kazak

wrote:

...

Indentation messed up… I have pasted the code here: http://hpaste.org/77864

enumerating the abstract syntax tree is actually (or at least could be) the way to go! Thanks a lot! What I need is a little bit different, but now I feel I'm on the right track!

This is my first question to the café and it makes me a lot more certain using Haskell for production, when you can get this kind of quick and thorough help when in doubt.

Great community!

-Rune

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe