Patch combinators: A library for patching functions and data structures
A patch can be, for example
- a type constraint (an identity function with a specific type)
- a surjective function extending the domain of a function (e.g. turning a function on natural numbers into a function defined for any integer)
A typical use-case is to constrain the types of a QuickCheck property. Let's say we have a property to check associativity of addition:
prop_addAssoc :: (Num a, Ord a) => a -> a -> a -> Bool prop_addAssoc a b c = (a + b) + c == a + (b + c)
In order to check that this property holds for Int8
, we just say:
*Data.Patch> quickCheck (prop_addAssoc -:: tI8 >-> id)
Note that we only had to give a partial type annotation since all arguments are required to have the same type.
Sometimes properties are only defined for a sub-set of the possible
arguments. Consider the following property of enumFromTo
:
prop_enum m n = enumFromTo 0 m !! n == n
This property is only valid when m
and n
are natural numbers and n<=m
.
Instead of rewriting the property to account for arbitrary integers, we can
simply apply a patch:
quickCheck (prop_enum -:: name (\m -> abs >-> (min (abs m) . abs) >-> id))
Here name
allows us to bind the first argument generated by QuickCheck.
The patch uses abs
to make sure that the values passed to the property are
natural numbers, and
to ensure that the second argument
does not exceed the first.
min
(abs
m)
The library has some similarities with Semantic editor combinators:
http://conal.net/blog/posts/semantic-editor-combinators
The main difference is that semantic editors are about locating and changing
a small part of a data structure, while patches are about changing all parts
of the structure. (For partial updates, use the id
patch to leave
sub-structures untouched.)
- type Patch a b = a -> b
- (-::) :: a -> Patch a b -> b
- (>->) :: Patch c a -> Patch b d -> Patch (a -> b) (c -> d)
- name :: (c -> Patch (a -> b) (c -> d)) -> Patch (a -> b) (c -> d)
- tup2 :: Patch a1 b1 -> Patch a2 b2 -> Patch (a1, a2) (b1, b2)
- tup3 :: Patch a1 b1 -> Patch a2 b2 -> Patch a3 b3 -> Patch (a1, a2, a3) (b1, b2, b3)
- tup4 :: Patch a1 b1 -> Patch a2 b2 -> Patch a3 b3 -> Patch a4 b4 -> Patch (a1, a2, a3, a4) (b1, b2, b3, b4)
- tup5 :: Patch a1 b1 -> Patch a2 b2 -> Patch a3 b3 -> Patch a4 b4 -> Patch a5 b5 -> Patch (a1, a2, a3, a4, a5) (b1, b2, b3, b4, b5)
- tup6 :: Patch a1 b1 -> Patch a2 b2 -> Patch a3 b3 -> Patch a4 b4 -> Patch a5 b5 -> Patch a6 b6 -> Patch (a1, a2, a3, a4, a5, a6) (b1, b2, b3, b4, b5, b6)
- tup7 :: Patch a1 b1 -> Patch a2 b2 -> Patch a3 b3 -> Patch a4 b4 -> Patch a5 b5 -> Patch a6 b6 -> Patch a7 b7 -> Patch (a1, a2, a3, a4, a5, a6, a7) (b1, b2, b3, b4, b5, b6, b7)
- tBool :: Patch Bool Bool
- tWord :: Patch Word Word
- tInt :: Patch Int Int
- tW8 :: Patch Word8 Word8
- tI8 :: Patch Int8 Int8
- tW16 :: Patch Word16 Word16
- tI16 :: Patch Int16 Int16
- tW32 :: Patch Word32 Word32
- tI32 :: Patch Int32 Int32
- tInteger :: Patch Integer Integer
- tFloat :: Patch Float Float
- tComplex :: Patch a a -> Patch (Complex a) (Complex a)
- tCon :: Patch a a -> Patch (c a) (c a)
Patch combinators
(>->) :: Patch c a -> Patch b d -> Patch (a -> b) (c -> d)Source
Function patch
The first patch is applied to the argument and the second patch to the result.
name :: (c -> Patch (a -> b) (c -> d)) -> Patch (a -> b) (c -> d)Source
A patch that depends on the first argument of the resuting function
tup2 :: Patch a1 b1 -> Patch a2 b2 -> Patch (a1, a2) (b1, b2)Source
Pair patch (a specialized version of ***
)
tup3 :: Patch a1 b1 -> Patch a2 b2 -> Patch a3 b3 -> Patch (a1, a2, a3) (b1, b2, b3)Source
Analogous to tup2
tup4 :: Patch a1 b1 -> Patch a2 b2 -> Patch a3 b3 -> Patch a4 b4 -> Patch (a1, a2, a3, a4) (b1, b2, b3, b4)Source
Analogous to tup2
tup5 :: Patch a1 b1 -> Patch a2 b2 -> Patch a3 b3 -> Patch a4 b4 -> Patch a5 b5 -> Patch (a1, a2, a3, a4, a5) (b1, b2, b3, b4, b5)Source
Analogous to tup2
tup6 :: Patch a1 b1 -> Patch a2 b2 -> Patch a3 b3 -> Patch a4 b4 -> Patch a5 b5 -> Patch a6 b6 -> Patch (a1, a2, a3, a4, a5, a6) (b1, b2, b3, b4, b5, b6)Source
Analogous to tup2
tup7 :: Patch a1 b1 -> Patch a2 b2 -> Patch a3 b3 -> Patch a4 b4 -> Patch a5 b5 -> Patch a6 b6 -> Patch a7 b7 -> Patch (a1, a2, a3, a4, a5, a6, a7) (b1, b2, b3, b4, b5, b6, b7)Source
Analogous to tup2