Write you some QuickCheck - Shrinking numberss

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:

Replace 0 with GenericZero
Replace 2 with GenericOne + GenericOne
Apply the inline modifier to the function

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; ...]