That's a good point. I remember having exactly that problem when writing tests for my toy language's parser. Generating random valid programs was actually tricky for several different reasons. In fact, I ultimately gave up on QuickCheck completely for that project, but mostly out of laziness.

Amusingly, I also wrote some tree diff code in Haskell recently. However, I did it rather poorly so I'm going to have to rewrite it soon (probably some time during winter break). I definitely agree that algorithms like this are particularly well-suited for QuickCheck.