# 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
[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; ...]
```