blob: 28119cd93f288d52bc7ec773afe319bbf8fc3f60 (
plain)
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
|
(.module:
[lux #*
["%" data/text/format (#+ format)]
["_" test (#+ Test)]
[abstract
[monad (#+ do)]
[equivalence (#+ Equivalence)]
[order (#+ Order)]
{[0 #test]
[/
["$." equivalence]]}]
[data
["." product]
[number
["." nat]]
[collection
["." set]
["." list ("#@." functor)]]]
[math
["r" random (#+ Random) ("#@." monad)]]]
{1
["." /]})
(def: #export (dictionary order gen-key gen-value size)
(All [k v]
(-> (Order k) (Random k) (Random v) Nat (Random (/.Dictionary k v))))
(case size
0
(r@wrap (/.new order))
_
(do r.monad
[partial (dictionary order gen-key gen-value (dec size))
key (r.filter (function (_ candidate)
(not (/.contains? candidate partial)))
gen-key)
value gen-value]
(wrap (/.put key value partial)))))
(def: #export test
Test
(<| (_.context (%.name (name-of /.Dictionary)))
(do r.monad
[size (|> r.nat (:: @ map (n/% 100)))
keys (r.set nat.hash size r.nat)
values (r.set nat.hash size r.nat)
extra-key (|> r.nat (r.filter (|>> (set.member? keys) not)))
extra-value r.nat
#let [pairs (list.zip2 (set.to-list keys)
(set.to-list values))
sample (/.from-list nat.order pairs)
sorted-pairs (list.sort (function (_ [left _] [right _])
(n/< left right))
pairs)
sorted-values (list@map product.right sorted-pairs)
(^open "/@.") (/.equivalence nat.equivalence)]]
($_ _.and
($equivalence.spec (/.equivalence nat.equivalence) (..dictionary nat.order r.nat r.nat size))
(_.test "Can query the size of a dictionary."
(n/= size (/.size sample)))
(_.test "Can query value for minimum key."
(case [(/.min sample) (list.head sorted-values)]
[#.None #.None]
#1
[(#.Some reference) (#.Some sample)]
(n/= reference sample)
_
#0))
(_.test "Can query value for maximum key."
(case [(/.max sample) (list.last sorted-values)]
[#.None #.None]
#1
[(#.Some reference) (#.Some sample)]
(n/= reference sample)
_
#0))
(_.test "Converting dictionaries to/from lists cannot change their values."
(|> sample
/.entries (/.from-list nat.order)
(/@= sample)))
(_.test "Order is preserved."
(let [(^open "list@.") (list.equivalence (: (Equivalence [Nat Nat])
(function (_ [kr vr] [ks vs])
(and (n/= kr ks)
(n/= vr vs)))))]
(list@= (/.entries sample)
sorted-pairs)))
(_.test "Every key in a dictionary must be identifiable."
(list.every? (function (_ key) (/.contains? key sample))
(/.keys sample)))
(_.test "Can add and remove elements in a dictionary."
(and (not (/.contains? extra-key sample))
(let [sample' (/.put extra-key extra-value sample)
sample'' (/.remove extra-key sample')]
(and (/.contains? extra-key sample')
(not (/.contains? extra-key sample''))
(case [(/.get extra-key sample')
(/.get extra-key sample'')]
[(#.Some found) #.None]
(n/= extra-value found)
_
#0)))
))
))))
|
