diff options
author | simonmar <unknown> | 2002-06-03 14:16:56 +0000 |
---|---|---|
committer | simonmar <unknown> | 2002-06-03 14:16:56 +0000 |
commit | 466922c82316cecf75a3cc7b31e9331a60c40625 (patch) | |
tree | 1201f34a27588d24719a0fc102171e8d9ff7f58a | |
parent | 854f4914bf3b9678f1be84c44db7993103d53a01 (diff) |
[haddock @ 2002-06-03 14:16:56 by simonmar]
Example from the paper
-rw-r--r-- | examples/Hash.hs | 45 |
1 files changed, 45 insertions, 0 deletions
diff --git a/examples/Hash.hs b/examples/Hash.hs new file mode 100644 index 00000000..b399b129 --- /dev/null +++ b/examples/Hash.hs @@ -0,0 +1,45 @@ +{- | + 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 Array + +-- | 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) + +-- | Inserts a new element into the hash table +insert :: (Eq key, Hash key) => key -> val -> IO () + +-- | 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) + +-- | 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 + |