# Write you some QuickCheck - Shrinking numbers

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
``````

Let’s try this one out first:

``````
λ> :t shrinkIntegral
shrinkIntegral :: Integral a => a -> [a]

λ> shrinkIntegral 1


λ> 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 

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

``````