Well, at least this is a nice exercise! I'm assuming that all operators associate to the left, and use the usual precedence rules. My approach would consider (1+2)+3 different from 1+(2+3), and enumerate it again. Of course they are different computations, though mathematically equivalent. Jonas' approach is better here, but it seems to miss X/(X/X) — not tested, it's just not in his email. But then the equivalent X/X*X is present. So... what kind of equivalences *exactly* do you want to omit? Here's some code for my somewhat more permissive solution:
data Expr = Val Float | Op Char Expr Expr deriving (Eq)
instance Show Expr where showsPrec _ (Val v) = shows v showsPrec p (Op o e1 e2) = showParen (p>q) $ showsPrec q e1 . showString [' ',o,' '] . showsPrec (q+1) e2 where q = case o of '+' -> 1 '-' -> 1 '*' -> 3 '/' -> 3
Split a sequence in two non-empty sequences at all possible places.
allSplits :: [a] -> [([a],[a])] -- ok, this is ugly allSplits xs = [splitAt n xs | n <- [1 .. length xs - 1]]
Calculate all ASTs.
exps [x] = [Val x] exps xs = [ Op o l r | (as,bs) <- allSplits xs , l <- exps as , r <- exps bs , o <- "+-*/" ]
putStr . unlines . map show $ exps [1..3] -- Stefan Klinger o/klettern /\/ bis zum send plaintext only - max size 32kB - no spam \ Abfallen http://stefan-klinger.de