aboutsummaryrefslogtreecommitdiff
path: root/examples/Hash.hs
diff options
context:
space:
mode:
Diffstat (limited to 'examples/Hash.hs')
-rw-r--r--examples/Hash.hs45
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
+