The library encourages and documentation suggests a bad method for shrinking records

TL;DR

The docs should never recommend using Lazy.List.map or Lazy.List.andMap (and they probably ought to be pulled out of the module provides eventually). Instead the docs should recommend exploiting the provided tuple shrinker to build multi-field values.

Gory details

(Apologies, this is going to be long. I'm deliberately including lots of code so that the problem is clear and it's as easy as possible for people to fix their own programs from examples here.)

The documentation suggests writing a shrinker for a multi-field Mario as follows:

type alias Mario =
  { position  : Vector
  , velocity  : Vector
  , direction : Direction
  }

type alias Vector =
  { x : Float
  , y : Float
  }

type Direction
  = Left
  | Right

mario : Shrinker Mario
mario m =
  Mario
    `map`    vector m.position
    `andMap` vector m.velocity
    `andMap` direction m.direction

This defines a shrinker that performs very poorly, often finding no way to shrink obviously shrinkable values:

mario { position = Vector 1 1, velocity = Vector 2 2, direction = Right }
-- --> [{ position = { x = 0, y = 0 }, velocity = { x = 0, y = 0 }, direction = Left }]
mario { position = Vector 1 1, velocity = Vector 2 2, direction = Left }
-- --> []
mario { position = Vector 1 1, velocity = Vector 2 0, direction = Right }
-- --> []

The issue is that the map / andMap style of computing multiple shrinks succeeds at shrinking a field only if all subfields are shrinkable, so as soon as any field gets "zeroed out" the whole think is considered irreducible. A better strategy (and the one used in Haskell quickcheck) is to attempt to shrink just a single field at a time rather than all at once. The tuple, tuple3, etc shrinkers provided already do that. For instance, here's a function that does such a thing, reusing the implementation of tuple shrinkers that already have this behavior:

shrinkRecord3 : (field1 -> field2 -> field3 -> obj)
             -> (obj -> field1, Shrinker field1)
             -> (obj -> field2, Shrinker field2)
             -> (obj -> field3, Shrinker field3)
             -> Shrinker obj
shrinkRecord3 constructor (field1, shrinkField1) (field2, shrinkField2) (field3, shrinkField3) =
  Shrink.convert
    (\(f1, f2, f3) -> constructor f1 f2 f3)
    (\obj -> (field1 obj, field2 obj, field3 obj))
    (tuple3 (shrinkField1, shrinkField2, shrinkField3))
-- and similar for shrinkRecord1, 2, etc

-- sample usage

vector' : Shrinker Vector
vector' =
  shrinkRecord2
    Vector
    (.x, float)
    (.y, float)

mario' : Shrinker Mario
mario' =
  shrinkRecord3
    Mario
    (.position, vector')
    (.velocity, vector')
    (.direction, direction)

mario' { position = Vector 1 1, velocity = Vector 2 2, direction = Right }
{- 
--> 
[ { position = { x = 1, y = 1 }, velocity = { x = 2, y = 2 }, direction = Left }
, { position = { x = 1, y = 1 }, velocity = { x = 2, y = 0 }, direction = Right }
, { position = { x = 1, y = 1 }, velocity = { x = 2, y = 1 }, direction = Right }
, ... 
]
-}

mario' { position = Vector 1 1, velocity = Vector 2 2, direction = Left }
{-
-->
[ { position = { x = 1, y = 1 }, velocity = { x = 2, y = 0 }, direction = Left }
, { position = { x = 1, y = 1 }, velocity = { x = 2, y = 1 }, direction = Left }
, { position = { x = 1, y = 1 }, velocity = { x = 2, y = 1.5 }, direction = Left }
, ...
]
-}

mario'  { position = Vector 1 1, velocity = Vector 2 0, direction = Right }
{-
-->
[ { position = { x = 1, y = 1 }, velocity = { x = 2, y = 0 }, direction = Left }
, { position = { x = 1, y = 1 }, velocity = { x = 0, y = 0 }, direction = Right }
, { position = { x = 1, y = 1 }, velocity = { x = 1, y = 0 }, direction = Right }
, ...
]
-}

This improved ability to shrink produces dramatically better counterexamples in elm-check. Here's a little example of a binary search tree test that demonstrates the issue:

type Tree a = Leaf | Branch a (Tree a) (Tree a)

search : comparable -> Tree comparable -> Bool
search target tree =
  case tree of
    Leaf -> False
    Branch val left right ->
      if target == val then True
      else if target < val then search target left
      else search target left  -- oops! Meant to search the _right_ subtree!

-- using the current recommended shrinking method
mapBasedTreeShrinker : Shrinker a -> Shrinker (Tree a)
mapBasedTreeShrinker shrinkValue t =
  case t of
    Leaf -> empty
    Branch v l r ->
      Branch
        `map` shrinkValue v
        `andMap` mapBasedTreeShrinker shrinkValue l
        `andMap` mapBasedTreeShrinker shrinkValue r

-- using the tuple method
tupleBasedTreeShrinker : Shrinker a -> Shrinker (Tree a)
tupleBasedTreeShrinker shrinkValue t =
  case t of
    Leaf -> empty
    Branch v l r ->
      Leaf :::
        Lazy.List.map
        (\(v, l, r) -> Branch v l r)
        ((tuple3 (shrinkValue, (tupleBasedTreeShrinker shrinkValue), (tupleBasedTreeShrinker shrinkValue)))
         (v, l, r))

searchClaim : Investigator (Tree Int) -> Claim
searchClaim investigator =
  claimTrue
    "Search finds inserted values"
    (\(number, tree) -> insert number tree |> search number)
    (Check.Investigator.tuple ((Check.Investigator.rangeInt -100 100), investigator))

quickCheck (searchClaim (mapBasedTreeShrinker (Random.int 0 70) int))
{- produces counterexample:
(3,Branch 7 (Branch 2 Leaf (Branch 3 Leaf (Branch 4 Leaf Leaf))) (Branch 63 (Branch 12 Leaf (Branch 21 (Branch 18 Leaf Leaf) (Branch 32 (Branch 22 Leaf Leaf) (Branch 43 (Branch 40 (Branch 37 Leaf Leaf) Leaf) Leaf)))) Leaf))
-}

quickCheck (searchClaim (tupleBasedTreeShrinker (Random.int 0 70) int))
{- produces counterexample:
(1,Branch 0 Leaf Leaf)
-}

The map-based method produces a much larger-than-necessary counterexample, whereas the tuple-based method produces the minimal counterexample.

So basically, the docs and library methods provide a way of writing shrinkers that is bad, but in a subtle way that makes the library much less useful than it could be without breaking it outright. The docs should be updated to recommend the approach outlined here, relying on tuple instead of lazy list mapping, and eventually the lazy list map and andMap functions should be removed from Shrinker's exports entirely.

noredink / elm-shrink Goto Github PK

elm-shrink's People

Contributors

Watchers

Forkers

elm-shrink's Issues

The library encourages and documentation suggests a bad method for shrinking records

TL;DR

Gory details

Recommend Projects

React

Vue.js

Typescript

TensorFlow

Django

Laravel

D3

Recommend Topics

javascript

web

server

Machine learning

Visualization

Game

Recommend Org

Facebook

Microsoft

Google

Alibaba

D3

Tencent