As part of me learning about quickCheck I want to build a test generator for a levenshtein edit distance implementation. The obvious approach I think is to start with two equal strings and a random non-reducable series of insert/delete/traspose actions, apply that to one of the strings and assert that the levenshtein distance is the length of the random series.
I am quite stuck with this can someone help?
Getting "non-reducible" right sounds pretty hard. I would try to find a larger number of less complicated invariants. Here are some ideas:
x, if you apply exactly one change to it, producing y, the edit distance between x and y should be 1.x and y, compute the distance d between them. Then, change y, yielding y', and compute its distance from x: it should differ from d by at most 1.n edits to a string x, the distance between the edited string and x should be at most n. Note that case (1) is a special case of this, where n=0, so you could omit that one for concision if you like. Or, keep it around, since case (1) may generate simpler counterexamples.x to y should be the same as from y to x.If you have another, known-good implementation of the algorithm to test against, you could compare to that, and assert that you always get the same answer as it does.
The above were all just things that appealed to me without any research. You could do more: for example, encode the lower and upper bounds as defined by wikipedia.
