On Wed, Sep 3, 2008 at 11:34 AM, Andrew Coppin
<[EMAIL PROTECTED]> wrote:
> data Expression = Var String | Apply Expression Expression | Lambda String
> Expression
>
> How would you go about building random expression trees?
It's pretty simple, I think. Keep an environment of variable names
that are in enclosing lambdas, then randomly choose Apply/Lambda/Var,
ignoring Var if the environment is empty, and with Lambda adding to
the environment of its subexpression.
I suggest
type ExpGen = ReaderT [String] Gen
arbExp :: ExpGen Expression
-- exercise for the reader
instance Arbitrary Expression where
arbitrary = runReaderT arbExp []
coarbitrary = coarbExp
coarbExp (Var s) = variant 0 . coarbitrary s
coarbExp (Apply a b) = variant 1 . coarbitrary a . coarbitrary b
coarbExp (Lambda s e) = variant 2 . coarbitrary s . coarbitrary e
-- Also, apparently there is no default Arbitrary instance for strings, so...
instance Arbitrary Char where
arbitrary = elements "abcdefghijklmnopqrstuvwxyz_"
coarbitrary = coarbitrary . fromEnum
Here's some examples I got with a quick and dirty implementation for arbExp:
Lambda "" (Lambda "" (Var ""))
Lambda "jae" (Lambda "iq" (Var "jae"))
Lambda "sj" (Lambda "" (Var ""))
Lambda "n" (Var "n")
Lambda "lxy" (Lambda "md_fy" (Lambda "b" (Var "b")))
Lambda "" (Apply (Lambda "" (Var "")) (Lambda "" (Lambda "" (Var ""))))
Lambda "vve" (Lambda "mvy" (Var "vve"))
Lambda "" (Apply (Apply (Var "") (Lambda "km" (Var "km"))) (Var ""))
Lambda "" (Lambda "_" (Var ""))
Lambda "aeq" (Var "aeq")
Lambda "l_" (Apply (Var "l_") (Lambda "" (Var "l_")))
My implementation doesn't choose Apply nearly enough, but I was
worried about exponential blowup; the solution is to use the "sized"
combinator from QuickCheck and have the size determine the number of
Apply you are allowed to have.
It's also probably a good idea to not allow empty strings for variable names :)
-- ryan
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
