Random testing of purely functional abstract datatypes

Algebraic specification, equational reasoning, and property-based random testing provide functional programmers with a powerful yet reasonably lightweight framework for reasoning about abstract datatypes and assuring the quality of their concrete implementations. However, as it turns out, naïvely implementing property-based random testing for purely functional abstract datatypes is prone to subtle errors and may well leave unaware practitioners with a false sense of security about their datatype implementations. In this paper, we pinpoint one particular pitfall, namely overlooking the need to take into account the invariance of datatype operations under an implied equivalence relation on concreate datatype values, and discuss how to systematically avoid it. Presented in the context of a concrete case study, the proposed technique generalises nicely into a common design principle for engineering random tests of purely functional datastructures.