[Haskell-cafe] List all multiply/add combinations
Stefan Klinger
all-lists at stefan-klinger.de
Mon Nov 19 00:23:31 CET 2012
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
More information about the Haskell-Cafe
mailing list