This post is part of a series of posts on implementing a minimal version of QuickCheck from scratch. The source code is available on GitHub .
In this post I’ll be porting the function from QuickCheck that shrinks numbers.
Prelude
When reporting back the actual input that caused a function to fail, QuickCheck first cleans the noise by reporting back the counterexample. — This is called shrinking . See how it works here .
All the shrinking functions have the same signature:
shrink :: a -> [ a ]
So in F# it can look like this:
' a -> ' a seq
Shrinking numbers
QuickCheck shrinks towards smaller numeric values with the following generic function:
-- | Shrink an integral number.
shrinkIntegral :: Integral a => a -> [ a ]
shrinkIntegral x =
nub
$
[ - x | x < 0 , - x > x ]
++
[ x' | x' <- takeWhile ( << x ) ( 0 : [ x - i | i <- tail ( iterate (` quot ` 2 ) x ) ]) ]
where
-- a << b is "morally" abs a < abs b, but taking care of overflow.
a << b = case ( a >= 0 , b >= 0 ) of
( True , True ) -> a < b
( False , False ) -> a > b
( True , False ) -> a + b < 0
( False , True ) -> a + b > 0
(View on Hackage )
Let’s try this one out first:
λ> :t shrinkIntegral
shrinkIntegral :: Integral a => a -> [a]
λ> shrinkIntegral 1
[0]
λ> shrinkIntegral (-1)
[1,0]
λ> shrinkIntegral (-2)
[2,0,-1]
λ> shrinkIntegral (-3)
[3,0,-2]
λ> shrinkIntegral (-4)
[4,0,-2,-3]
λ> shrinkIntegral (-2)
[2,0,-1]
λ> shrinkIntegral 2
[0,1]
λ> shrinkIntegral 3
[0,2]
λ> shrinkIntegral 4
[0,2,3]
λ> shrinkIntegral (-700)
[700,0,-350,-525,-613,-657,-679,-690,-695,-698,-699]
λ> shrinkIntegral 700
[0,350,525,613,657,679,690,695,698,699]
λ> shrinkIntegral 7
[0,4,6]
λ> shrinkIntegral (-7)
[7,0,-4,-6]
Here’s the equivalent one in F#:
(* This has the type n:int -> seq<int> but we'll
come and fix this later on. *)
let shrinkNumber n =
n
|> Seq . unfold ( fun s -> Some ( n - s , s / 2 ))
|> Seq . tail
|> Seq . append [ 0 ]
|> Seq . takeWhile ( fun el -> abs n > abs el )
|> Seq . append ( if n < 0 then Seq . singleton - n
else Seq . empty )
|> Seq . distinct
I’m going to try this one with the same values as the ones used in Haskell:
> val shrinkNumber : n:int -> seq<int>
> shrinkNumber 1;;
val it : seq<int> = seq [0]
> shrinkNumber (-1);;
val it : seq<int> = seq [1; 0]
> shrinkNumber (-2);;
val it : seq<int> = seq [2; 0; -1]
> shrinkNumber (-3);;
val it : seq<int> = seq [3; 0; -2]
> shrinkNumber (-4);;
val it : seq<int> = seq [4; 0; -2; -3]
> shrinkNumber (-2);;
val it : seq<int> = seq [2; 0; -1]
> shrinkNumber 2;;
val it : seq<int> = seq [0; 1]
> shrinkNumber 3;;
val it : seq<int> = seq [0; 2]
> shrinkNumber 4;;
val it : seq<int> = seq [0; 2; 3]
> shrinkNumber (-700);;
val it : seq<int> = seq [700; 0; -350; -525; ...]
> shrinkNumber 700;;
val it : seq<int> = seq [0; 350; 525; 613; ...]
> shrinkNumber 7;;
val it : seq<int> = seq [0; 4; 6]
> shrinkNumber (-7);;
val it : seq<int> = seq [7; 0; -4; -6]
Shrinking not only integers, but floats, decimals, and so on
Here is again the shrinkNumber
number function that was ported from Haskell:
(* This has the type n:int -> seq<int> but we'll
come and fix this later on. *)
let shrinkNumber n =
n
|> Seq . unfold ( fun s -> Some ( n - s , s / 2 ))
|> Seq . tail
|> Seq . append [ 0 ]
|> Seq . takeWhile ( fun el -> abs n > abs el )
|> Seq . append ( if n < 0 then Seq . singleton - n
else Seq . empty )
|> Seq . distinct
Because of 2
, and 0
, the F# compiler infers that this function works with integers.
Fortunately, there’s a way to make this polymorphic with compile-time generics :
Here’s the end result:
open FSharp . Core . LanguagePrimitives
let inline shrinkNumber n =
let genericTwo = GenericOne + GenericOne
n
|> Seq . unfold ( fun s -> Some ( n - s , s / genericTwo ))
|> Seq . tail
|> Seq . append [ GenericZero ]
|> Seq . takeWhile ( fun el -> abs n > abs el )
|> Seq . append ( if n < GenericZero then Seq . singleton - n
else Seq . empty )
|> Seq . distinct
And now the type has become generic:
// Formatted , in order to be easier to read :
val inline shrinkNumber :
n : ^ a -> seq < ^ a >
when ^ a : ( static member get_Zero : -> ^ a ) and
^ a : ( static member ( - ) : ^ a * ^ a -> ^ a ) and
( ^ a or ^ b ) : ( static member ( / ) : ^ a * ^ b -> ^ a ) and
^ a : ( static member Abs : ^ a -> ^ a ) and
^ a : ( static member ( ~- ) : ^ a -> ^ a ) and
^ a : comparison and
^ c : ( static member get_One : -> ^ c ) and
( ^ c or ^ d ) : ( static member ( + ) : ^ c * ^ d -> ^ b ) and
^ d : ( static member get_One : -> ^ d )
Let’s try this one out:
> shrinkNumber 3.14;;
val it : seq<float> = seq [0.0; 1.57; 2.355; 2.7475; ...]
> shrinkNumber 4.0f;;
val it : seq<float32> = seq [0.0f; 2.0f; 3.0f; 3.5f; ...]
>shrinkNumber (-700.15M);;
val it : seq<decimal> = seq [700.15M; 0M; -350.075M; -525.1125M; ...]
>shrinkNumber 900s;;
val it : seq<int16> = seq [0s; 450s; 675s; 788s; ...]
This post is part of a series of posts on implementing a minimal version of QuickCheck from scratch. The source code is available on GitHub .
In this post I’ll be generating random 32-bit floating-point numbers.
In Haskell’s QuickCheck 1.2.0.1 (but also in version 2.8), random 32-bit floating-point numbers are generated as shown below:
instance Arbitrary Float where
arbitrary = liftM3 fraction arbitrary arbitrary arbitrary
coarbitrary x = ...
Two things are important in the above code:
Here’s the original fraction
function in Haskell:
fraction :: Fractional a => Integer -> Integer -> Integer -> a
fraction a b c = fromInteger a + ( fromInteger b / ( abs ( fromInteger c ) + 1 ))
It takes 3 integers and returns an a
which is a fractional (a numeric type that supports the ordinary division operator /
).
Here are some sample values generated by fraction:
λ > fraction 1 2 3
1.5
λ > fraction 2 2 2
2.6666666666666665
λ > fraction 7 8 9
7.8
Now, what I want to do is to call the fraction
function passing random integers, something like this (pseudo-code):
-- Pseudo-code
fraction Gen<int> Gen<int> Gen<int>
Here’s where liftM3
comes into play:
liftM3 :: Monad m => ( a1 -> a2 -> a3 -> r ) -> m a1 -> m a2 -> m a3 -> m r
a1
, a2
, and a3
, correspond to the arguments of fraction
r
corresponds to the return value of fraction
m a1
, m a2
, m a3
will be 3 generators for integers
m r
the return value (the random float).
So, in F#, a generator for floats can be written as:
(* Generates a random real number. *)
let float =
let fraction a b c = float a + float b / ( abs ( float c ) + 1 . 0 )
Gen . lift3 fraction Gen . int Gen . int Gen . int
And the lift3
function in F# can be written in terms of apply
and return
:
(* Unpacks a function wrapped inside a generator, applying it into a new
generator. *)
let apply f m =
Gen . bind f ( fun f' ->
Gen . bind m ( fun m' ->
Gen . init ( f' m' )))
(* Returns a new generator obtained by applying a function to three existing
generators. *)
let lift3 f m1 m2 m3 = Gen . apply ( Gen . apply ( Gen . apply ( Gen . init f ) m1 ) m2 ) m3
Finally, here are some sample floats:
> Gen . float |> Gen . generate ;;
val it : float = 3 . 466666667
> Gen . float |> Gen . generate ;;
val it : float = 9 . 352941176
> Gen . float |> Gen . generate ;;
val it : float = 18 . 14285714
> Gen . float |> Gen . generate ;;
val it : float = 9 . 4
> Gen . float |> Gen . generate ;;
val it : float = - 16 . 8
> Gen . float |> Gen . generate ;;
val it : float = - 1 . 5
> Gen . float |> Gen . generate ;;
val it : float = - 1 . 25
> Gen . float |> Gen . generate ;;
val it : float = - 16 . 94117647
This post is part of a series of posts on implementing a minimal version of QuickCheck from scratch. The source code is available on GitHub .
In this post I’ll be generating random strings from randomly selected characters. I will also describe a way of customizing the whole creation process.
The following generators are required for this:
Given the above, a generator for strings can be written as:
/// < summary >
/// Generates a random string .
/// </ summary >
let string =
Gen . char
|> Gen . list
|> Gen . map ( List . toArray >> System . String )
Here are some sample strings:
> Gen . string |> Gen . generate ;;
val it : String = "lof5ºÛ"
> Gen . string |> Gen . generate ;;
val it : String = "'fv*ì UÇ"
> Gen . string |> Gen . generate ;;
val it : String = "Ðê
Customizations
Generarting upper-case strings
let upperCase = Gen . choose ( 65 , 90 ) |> Gen . map Operators . char
val upperCase : Gen < char >
let customString g =
g
|> Gen . list
|> Gen . map ( List . toArray >> System . String )
val customString : g : Gen < char > -> Gen < String >
Sample output:
> upperCase |> customString |> Gen . generate ;;
val it : String = "DGVHAYFAWIHQBOD"
> upperCase |> customString |> Gen . generate ;;
val it : String = "HEDDZYBATTYL"
> upperCase |> customString |> Gen . generate ;;
val it : String = "XLYJSMEYYZXN"
Generating lower-case strings
let lowerCase = Gen . choose ( 97 , 122 ) |> Gen . map Operators . char
val lowerCase : Gen < char >
let customString g =
g
|> Gen . list
|> Gen . map ( List . toArray >> System . String )
val customString : g : Gen < char > -> Gen < String >
Sample output:
> lowerCase |> customString |> Gen . generate ;;
val it : String = "qsnj"
> lowerCase |> customString |> Gen . generate ;;
val it : String = "cltfvqckqxeirmuqvjn"
> lowerCase |> customString |> Gen . generate ;;
val it : String = "wzwfojfjlrjglu"
This post is part of a series of posts on implementing a minimal version of QuickCheck from scratch. The source code is available on GitHub .
In this post I’ll be generating lists of random length.
The maximum length of the list will depend on the runtime size parameter. See this previous post that explains how size works.
Two generators are required for this:
a generator that picks numbers with absolute value bounded by the size (that’s Gen’s choose
)
a generator that creates lists of a given length (that’s Gen’s vector
). The length will be the number obtained by the above generator
Gen’s choose
is already available. Porting Gen’s vector
, which essentially means porting replicateM
/// < summary >
/// Takes a list of generators of type ' a , evaluates each one of them , and
/// collect the result , into a new generator of type ' a list .
/// </ summary >
/// < param name = "l" > The list of generators of type ' a .</ param >
/// < remarks >
/// This is written so that the F # compiler will use a tail call , as shown in
/// the resulting excerpt of generated IL :
/// IL_0000 : nop
/// IL_0001 : call class [ FSharp . Core ] Microsoft . FSharp . Core . FSharpFunc ` 2 < cl ...
/// IL_0006 : ldarg . 0
/// IL_0007 : call class [ FSharp . Core ] Microsoft . FSharp . Collections . FSharpLi ...
/// IL_000c : call class LightCheck . Gen / Gen ` 1 <!! 0 > LightCheck . Gen :: ' init' < c ...
/// IL_0011 : tail .
/// IL_0013 : call !! 1 [ FSharp . Core ] Microsoft . FSharp . Collections . ListModule ...
/// IL_0018 : ret
/// See also :
/// http :// stackoverflow . com / a / 6615060 / 467754 ,
/// http :// stackoverflow . com / a / 35132220 / 467754
/// </ remarks >
let sequence l =
let k m m' =
Gen . bind m ( fun x ->
Gen . bind m' ( fun xs ->
Gen . init ( x :: xs )))
Gen . init [] |> List . foldBack k l
/// < summary >
/// Generates a list of the given length .
/// </ summary >
/// < param name = "n" > The number of elements to replicate .</ param >
/// < param name = "g" > The generator to replicate .</ param >
let vector n g =
Gen . sequence [ for _ in [ 1 .. n ] -> g ]
Creating a custom gen
computation expression
Most, if not all, monadic computations on the Gen<'a>
type can be written in terms of Gen.bind
and Gen.init
(return).
A computation expression just makes this a whole lot easier:
[< AutoOpen >]
module Builder =
type GenBuilder () =
member this . Bind ( g1 , g2 ) = Gen . bind g1 g2
member this . ReturnFrom ( f ) = f
let gen = GenBuilder ()
Given the above, a generator for lists of random length can be written as:
/// < summary >
/// Generates a list of random length . The maximum length of the list depends
/// on the size parameter .
/// </ summary >
/// < param name = "g" > The generator from which to create a list from .</ param >
let list g = Gen . sized ( fun s -> gen { let ! n = Gen . choose ( 0 , s )
return ! Gen . vector n g })
Finally, here are some sample lists of type int
and char
, but it can be any generator of type 'a
really
> Gen . int |> Gen . list |> Gen . generate ;;
val it : int list = [- 10 ; 1 ; 0 ; - 14 ; 11 ; - 2 ; - 7 ]
> Gen . int |> Gen . resize 1337 |> Gen . list |> Gen . generate ;;
val it : int list =
[- 1027 ; 739 ; - 571 ; 475 ; 979 ; 144 ; - 1239 ; - 1282 ; - 1012 ; - 932 ; - 952 ]
> Gen . char |> Gen . list |> Gen . generate
val it : char list = [ ' : ' ; ' e' ; ' « ' ]
> Gen . char |> Gen . list |> Gen . generate
val it : char list =
[ ' H' ; ' µ ' ; ' Ø ' ; ' ° ' ; ' ò ' ; ' k' ; ' < ' ; ' t' ; ' t' ; ' È ' ; '\\' ; '\151' ; ' Æ ' ; ' ¥ ' ;
' / ' ; '\137' ; ' é ' ; '\145' ; ' / ' ; ' Ì ' ; ' ï ' ; '\153' ; ' · ' ; ' 7 ' ]
This post is part of a series of posts on implementing a minimal version of QuickCheck from scratch. The source code is available on GitHub .
Two generators are required for this, which have been ported already on previous posts:
The long integers are going to be generated by the integer returned by the first generator and then multiplied by a 16-bit^{1} integer’s largest possible value.
Given the above, a long integer generator can be written as:
/// < summary >
/// Generates a 64 - bit integer ( with absolute value bounded by the generation
/// size multiplied by 16 - bit integer's largest possible value ).
/// </ summary >
let int64 = Gen . int |> Gen . map ( fun n -> Operators . int64 ( n * 32767 ))
val int64 : Gen < int64 >
Finally, here are some sample long integers:
> Gen . int64 |> Gen . generate ;;
val it : int64 = - 294903 L
> Gen . int64 |> Gen . generate ;;
val it : int64 = - 32767 L
> Gen . int64 |> Gen . generate ;;
val it : int64 = 163835 L
> Gen . int64 |> Gen . generate ;;
val it : int64 = 131068 L
> Gen . int64 |> Gen . generate ;;
val it : int64 = - 65534 L
> Gen . int64 |> Gen . generate ;;
val it : int64 = 229369 L
> Gen . int64 |> Gen . generate ;;
val it : int64 = 393204 L