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
|
-- Our use of genericLength in easyList will cause our function to loop
-- infinitely if we supply an infinite list. Fix this.
-- It is not possible to decide whether a list has been defined as infinite. For
-- this, there would have to be some reflection capabilities in the
-- language. Only a finite limit on the list max. length can be set and checked.
-- I was compiling the code of this chapter by 'cabal build'. There were some
-- warnings and errors. I have fixed only the errors.
--
-- - in BloomFilter/Hash.hs, a part of the import statement for CSize had to
-- be changed from '(CSize)' to '(CSize(..))' to import the data
-- constructor, not only the type constructor.
--
-- - in BloomFilter.hs in the fromList function, the 'B hash . runSTUArray $'
-- had to be changed to 'B hash $ runSTUArray $' for the code to compile.
-- For testing, I was loading the code into ghci. For it to be able to find
-- symbols from the lookup3.o file, I needed to convert it to a shared library
--
-- gcc ./dist-newstyle/build/x86_64-linux/ghc-9.6.7/rwh-bloomfilter-0.1/build/cbits/lookup3.o -shared -o liblookup3.so
--
-- and load the shared library on start of ghci
--
-- stack ghci --ghci-options "-L$(pwd) -llookup3"
import BloomFilter.Easy
import BloomFilter.Hash (Hashable, doubleHash)
import Data.List (genericLength)
import qualified BloomFilter as B
-- Helper function for forcing evaluation of the easyList and fixedEasyList
-- return value
easyListLength l =
case l of
Left err -> error err
Right b -> BloomFilter.Easy.length b
-- Short length for more illustrative testing
maxLength = 10
fixedEasyList errRate values =
if isLongerThan values maxLength
then
Left $ "List longer than " ++ (show maxLength) ++ " elements"
else
case suggestSizing (genericLength values) errRate of
Left err -> Left err
Right (bits,hashes) -> Right filt
where filt = B.fromList (doubleHash hashes) bits values
isLongerThan values max = isLongerThan' values 0 max
where
isLongerThan' [] l max = False
isLongerThan' (v:vs) l max
| (l + 1) > max = True
| otherwise = isLongerThan' vs (l + 1) max
-- ghci> :l 26_a_1.hs
-- [1 of 7] Compiling BloomFilter.Hash ( BloomFilter/Hash.hs, interpreted )
-- ... <omitted warnings here>
-- [2 of 7] Compiling BloomFilter.Internal ( BloomFilter/Internal.hs, interpreted )
-- [3 of 7] Compiling BloomFilter.Mutable ( BloomFilter/Mutable.hs, interpreted )
-- [4 of 7] Compiling BloomFilter ( BloomFilter.hs, interpreted )
-- [5 of 7] Compiling BloomFilter.Easy ( BloomFilter/Easy.hs, interpreted )
-- [6 of 7] Compiling Main ( 26_a_1.hs, interpreted )
-- Ok, six modules loaded.
-- ghci> l = easyList 0.2 [1..]
-- ghci> easyListLength l
-- *** Exception: stack overflow
-- ghci> l = fixedEasyList 0.2 [1..]
-- ghci> easyListLength l
-- *** Exception: List longer than 10 elements
-- CallStack (from HasCallStack):
-- error, called at 26_a_1.hs:40:17 in main:Main
-- ghci> l = fixedEasyList 0.2 [1..10]
-- ghci> easyListLength l
-- 34
|
