1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
|
{-# LANGUAGE PatternSynonyms #-}
{-# LANGUAGE ScopedTypeVariables #-}
{-# OPTIONS_GHC -fno-warn-orphans #-} -- because of the Arbitrary instances
{-# OPTIONS_GHC -Wno-incomplete-uni-patterns #-} -- https://github.com/nick8325/quickcheck/issues/344
-- | Tests for the 'Data.HashSet' module. We test functions by
-- comparing them to @Set@ from @containers@. @Set@ is referred to as a
-- /model/ for @HashSet@.
module Properties.HashSet (tests) where
import Data.Hashable (Hashable (hashWithSalt))
import Data.HashMap.Lazy (HashMap)
import Data.HashSet (HashSet)
import Data.Ord (comparing)
import Data.Set (Set)
import Test.QuickCheck (Fun, pattern Fn, (===), (==>))
import Test.Tasty (TestTree, testGroup)
import Test.Tasty.QuickCheck (Arbitrary (..), testProperty)
import Util.Key (Key, keyToInt)
import qualified Data.Foldable as Foldable
import qualified Data.HashMap.Lazy as HM
import qualified Data.HashSet as HS
import qualified Data.List as List
import qualified Data.Set as S
import qualified Test.QuickCheck as QC
instance (Eq k, Hashable k, Arbitrary k, Arbitrary v) => Arbitrary (HashMap k v) where
arbitrary = HM.fromList <$> arbitrary
shrink = fmap HM.fromList . shrink . HM.toList
instance (Eq a, Hashable a, Arbitrary a) => Arbitrary (HashSet a) where
arbitrary = HS.fromMap <$> arbitrary
shrink = fmap HS.fromMap . shrink . HS.toMap
------------------------------------------------------------------------
-- Helpers
type HSK = HashSet Key
toOrdSet :: Ord a => HashSet a -> Set a
toOrdSet = S.fromList . HS.toList
------------------------------------------------------------------------
-- Test list
tests :: TestTree
tests = testGroup "Data.HashSet"
[ -- Instances
testGroup "instances"
[ testGroup "Eq"
[ testProperty "==" $
\(x :: HSK) y -> (x == y) === (toOrdSet x == toOrdSet y)
, testProperty "== permutations" $
\(xs :: [Key]) (is :: [Int]) ->
let shuffle idxs = List.map snd
. List.sortBy (comparing fst)
. List.zip (idxs ++ [List.maximum (0:is) + 1 ..])
ys = shuffle is xs
in HS.fromList xs === HS.fromList ys
, testProperty "/=" $
\(x :: HSK) y -> (x /= y) === (toOrdSet x /= toOrdSet y)
]
, testGroup "Ord"
[ testProperty "compare reflexive" $
-- We cannot compare to `Data.Map` as ordering is different.
\(x :: HSK) -> compare x x === EQ
, testProperty "compare transitive" $
\(x :: HSK) y z -> case (compare x y, compare y z) of
(EQ, o) -> compare x z === o
(o, EQ) -> compare x z === o
(LT, LT) -> compare x z === LT
(GT, GT) -> compare x z === GT
(LT, GT) -> QC.property True -- ys greater than xs and zs.
(GT, LT) -> QC.property True
, testProperty "compare antisymmetric" $
\(x :: HSK) y -> case (compare x y, compare y x) of
(EQ, EQ) -> True
(LT, GT) -> True
(GT, LT) -> True
_ -> False
, testProperty "Ord => Eq" $
\(x :: HSK) y -> case (compare x y, x == y) of
(EQ, True) -> True
(LT, False) -> True
(GT, False) -> True
_ -> False
]
, testProperty "Read/Show" $
\(x :: HSK) -> x === read (show x)
, testProperty "Foldable" $
\(x :: HSK) ->
List.sort (Foldable.foldr (:) [] x)
===
List.sort (Foldable.foldr (:) [] (toOrdSet x))
, testProperty "Hashable" $
\(xs :: [Key]) (is :: [Int]) salt ->
let shuffle idxs = List.map snd
. List.sortBy (comparing fst)
. List.zip (idxs ++ [List.maximum (0:is) + 1 ..])
xs' = List.nub xs
ys = shuffle is xs'
x = HS.fromList xs'
y = HS.fromList ys
in x == y ==> hashWithSalt salt x === hashWithSalt salt y
]
-- Basic interface
, testProperty "size" $
\(x :: HSK) -> HS.size x === List.length (HS.toList x)
, testProperty "member" $
\e (s :: HSK) -> HS.member e s === S.member e (toOrdSet s)
, testProperty "insert" $
\e (s :: HSK) -> toOrdSet (HS.insert e s) === S.insert e (toOrdSet s)
, testProperty "delete" $
\e (s :: HSK) -> toOrdSet (HS.delete e s) === S.delete e (toOrdSet s)
-- Combine
, testProperty "union" $
\(x :: HSK) y -> toOrdSet (HS.union x y) === S.union (toOrdSet x) (toOrdSet y)
-- Transformations
, testProperty "map" $
\(Fn f :: Fun Key Key) (s :: HSK) -> toOrdSet (HS.map f s) === S.map f (toOrdSet s)
-- Folds
, testProperty "foldr" $
\(s :: HSK) ->
List.sort (HS.foldr (:) [] s) === List.sort (S.foldr (:) [] (toOrdSet s))
, testProperty "foldl'" $
\(s :: HSK) z0 ->
let f z k = keyToInt k + z
in HS.foldl' f z0 s === S.foldl' f z0 (toOrdSet s)
-- Filter
, testProperty "filter" $
\(Fn p) (s :: HSK) -> toOrdSet (HS.filter p s) === S.filter p (toOrdSet s)
-- Conversions
, testProperty "toList" $
\(xs :: [Key]) -> List.sort (HS.toList (HS.fromList xs)) === S.toAscList (S.fromList xs)
]
|
