Generating arbitrary functions with QuickCheck?
Hi, I'v been reading a small paper/lesson on writing parser combinators in Haskell, and it seems more or less straightforward. In this case a parser is defined thusly:
type Parser a = String -> Maybe (a, String) And then it goes on to list some simple parsers, and then starts going on about combinators. I was wondering how one would write quickcheck properties for the items presented in the paper, and the answer seemed fairly straightforward for the actual parsers. But how on earth would you write a test for a combinator? Presumable one would need to make the type an instance of Arbitrary. I see two problems: Firstly, as far as i can tell, one cannot declare a type synonym to be an instance of a type class, thus how would you make it an instance of Arbitrary? Secondly, (and more importantly, or at least more interesting) I can see how one would make a generator for simple compound data types, but how on earth do you make a generator produce functions?
On 15 Sep 2010, at 16:29, Matias Eyzaguirre wrote:
Hi, I'v been reading a small paper/lesson on writing parser combinators in Haskell, and it seems more or less straightforward. In this case a parser is defined thusly:
type Parser a = String -> Maybe (a, String) And then it goes on to list some simple parsers, and then starts going on about combinators. I was wondering how one would write quickcheck properties for the items presented in the paper, and the answer seemed fairly straightforward for the actual parsers. But how on earth would you write a test for a combinator? Presumable one would need to make the type an instance of Arbitrary. I see two problems: Firstly, as far as i can tell, one cannot declare a type synonym to be an instance of a type class, thus how would you make it an instance of Arbitrary?
The standard solution here is to create a newtype, and generate them instead.
Secondly, (and more importantly, or at least more interesting) I can see how one would make a generator for simple compound data types, but how on earth do you make a generator produce functions?
With some difficulty, but it can be done. You could for example, select at random, a combinator or axiomatic parser, on selecting a combinator, generate a pair of parsers to hand to it with a slightly lower chance of generating a combinator and stick them together. Bob
On 16 September 2010 01:58, Thomas Davie
Firstly, as far as i can tell, one cannot declare a type synonym to be an instance of a type class, thus how would you make it an instance of Arbitrary?
The standard solution here is to create a newtype, and generate them instead.
I've also written and used dedicated generation functions (especially for Strings, since I don't want _really_ arbitrary strings since some of them might accidentally bring up formatting that my parser can't cope with (or will parse as something else). Note that this is more for generating sub-parts of other data types, rather than for types I want to be able to run QC tests on. -- Ivan Lazar Miljenovic Ivan.Miljenovic@gmail.com IvanMiljenovic.wordpress.com
The type (String -> Maybe (a, String)) should already be an instance of
arbitrary if a is.
One way of generating functions is to have some sort of hashing function (a
-> Int). Functions from a to b can be generating by using the hash value to
transform the random seed before the b is generated. Here is a rough outline
for such a system:
genB :: StdGen -> B
hashA :: A -> Int
transformGen :: Int -> StdGen -> StdGen
genFun :: StdGen -> (A -> B)
genFun g a = genB $ transformGen (hashA a) g
In QC you have this instance:
(CoArbitraryhttp://hackage.haskell.org/packages/archive/QuickCheck/2.1.0.1/doc/html/Test...
a, Arbitraryhttp://hackage.haskell.org/packages/archive/QuickCheck/2.1.0.1/doc/html/Test...
b)
=> Arbitraryhttp://hackage.haskell.org/packages/archive/QuickCheck/2.1.0.1/doc/html/Test...
(a
-> b)
And CoArbitrary is the class where you implement the trick described above.
Look at the function called variant as well.
/J
On 16 September 2010 02:59, Ivan Lazar Miljenovic wrote: On 16 September 2010 01:58, Thomas Davie Firstly, as far as i can tell, one cannot declare a type synonym to be
an instance of a type class, thus how would you make it an instance of
Arbitrary? The standard solution here is to create a newtype, and generate them
instead. I've also written and used dedicated generation functions (especially
for Strings, since I don't want _really_ arbitrary strings since some
of them might accidentally bring up formatting that my parser can't
cope with (or will parse as something else). Note that this is more
for generating sub-parts of other data types, rather than for types I
want to be able to run QC tests on. --
Ivan Lazar Miljenovic
Ivan.Miljenovic@gmail.com
IvanMiljenovic.wordpress.com
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
On 15 September 2010 16:29, Matias Eyzaguirre
Secondly, (and more importantly, or at least more interesting) I can see how one would make a generator for simple compound data types, but how on earth do you make a generator produce functions?_______________________________________________
There are papers by Pieter Koopman and colleagues describing function generation for GAst - the Clean equivalent to QuickCheck: http://www.st.cs.ru.nl/Onderzoek/Publicaties/publicaties.html
participants (5)
-
Ivan Lazar Miljenovic -
Jonas Almström Duregård -
Matias Eyzaguirre -
Stephen Tetley -
Thomas Davie