[Haskell-cafe] List all multiply/add combinations

[Stefan Klinger]

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