
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
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