On Wed, Sep 3, 2008 at 11:34 AM, Andrew Coppin
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