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
|
{-# LANGUAGE Haskell2010 #-}
{- |
Implementation of fixed-size hash tables, with a type
class for constructing hash values for structured types.
-}
module Hash (
-- * The @HashTable@ type
HashTable,
-- ** Operations on @HashTable@s
new, insert, lookup,
-- * The @Hash@ class
Hash(..),
) where
import Data.Array
import Prelude hiding (lookup)
-- | A hash table with keys of type @key@ and values of type @val@.
-- The type @key@ should be an instance of 'Eq'.
data HashTable key val = HashTable Int (Array Int [(key,val)])
-- | Builds a new hash table with a given size
new :: (Eq key, Hash key) => Int -> IO (HashTable key val)
new = undefined
-- | Inserts a new element into the hash table
insert :: (Eq key, Hash key) => key -> val -> IO ()
insert = undefined
-- | Looks up a key in the hash table, returns @'Just' val@ if the key
-- was found, or 'Nothing' otherwise.
lookup :: Hash key => key -> IO (Maybe val)
lookup = undefined
-- | A class of types which can be hashed.
class Hash a where
-- | hashes the value of type @a@ into an 'Int'
hash :: a -> Int
instance Hash Int where
hash = id
instance Hash Float where
hash = trunc
instance (Hash a, Hash b) => Hash (a,b) where
hash (a,b) = hash a `xor` hash b
trunc = undefined
xor = undefined
|
