[Haskell-cafe] Compiler's bane

[Ryan Ingram]

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