9

I want to create a HashTable in Haskell, insert hash values inside and look up in this HashTable.

I found this documentation but I just started Haskell and therefore I don't really know how to ue these functions.

If some of you could show me some lines of code it would be perfect.

1
  • 1
    I agree with @Ingo, learn the language, then try to make a HashTable, because it's a fairly complicated data structure. Its also a bit more difficult to get it efficient in a language like Haskell if you don't know your way around the language and concepts of FP. Check out the Learn You a Haskell tutorial and then work through Real World Haskell (both are available online for free), together they make a pretty good introduction to the language.
    – bheklilr
    Dec 10, 2013 at 15:38

3 Answers 3

18

I second Ingo's comment about starting with something simpler. However, I'll break down a few things in a bit of detail.

First of all, I assume you've installed the latest Haskell Platform. In the website for the Platform there is a page with collected documentation for the libraries included with it. Any library that's not in that page would be something you'd need to install separately.

The Platform does include Data.HashTable, so you don't need to install anything, but if you look at the latest Platform's documentation on it, you'll see that it's deprecated and going to be removed soon. So I would not use that module.

The Haskell Platform comes with the two most popular Haskell implementations of a map/dictionary data structure:

  • Data.Map. (Most of the documentation for this is in Data.Map.Lazy.) This implements a map as a kind of balanced search tree, which means that the keys need to be an ordered type—a type that implements the Ord class. A lot of the built-in Haskell types already implement this class, so this would probably be your easiest choice at first.
  • The Data.HashMap module hierarchy, with two variants; Data.HashMap.Lazy would be a good starting point. This implements maps as a kind of hash table, so the keys need to implement the Hashable class. This class is newer and not as popular as Ord, so often you might need to implement this class for your key types.

So Data.Map is the easier type to use. But to use it effectively you're going to need to understand a few things beside the most basic language constructs:

  1. How to import a module in a source file.
  2. How to use qualified imports—Data.Map has function names that collide with many of the built-in ones in Haskell, which requires some special syntax.
  3. How to load a module into the ghci interpreter.
  4. How to compile a project that uses the containers library where Data.Map lives (using the cabal tool).

Once you have that down, the easiest way to build a map is from a list of key/value pairs:

module MyModule where

import Data.Map (Map)             -- This just imports the type name
import qualified Data.Map as Map  -- Imports everything else, but with names 
                                  -- prefixed with "Map." (with the period).

-- Example: make a Map from a key/value pair
ages :: Map String Integer
ages = Map.fromList [("Joe", 35), ("Mary", 37), ("Irma", 16)]

A few examples on how to use maps:

-- Example: look up somebody and return a message saying what their age is.
-- 'Nothing' means that the map didn't have the key.
findAge :: String -> String
findAge name = case Map.lookup name ages of
                 Nothing  -> "I don't know the age of " ++ name ++ "."
                 Just age -> name ++ " is " ++ show age ++ " years old."

-- Example: make a map with one extra entry compared to `ages` above.
moreAges :: Map String Integer
moreAges = Map.insert "Steve" 23 ages

-- Example: union of two maps.
evenMoreAges :: Map String Integer
evenMoreAges = Map.union moreAges anotherMap
    where anotherMap = Map.fromList [("Metuselah", 111), ("Anuq", 3)]
5

As a complement to Ingo's answer, consider using the purely function Data.Map.

 import qualified Data.Map as M

 myMap :: M.Map Int String
 myMap = M.fromList $ zip [1..10] ['a'..'j']

 insertedMap :: M.Map Int String
 insertedMap = M.insert 11 "fizzbuzz" oldMap

 at11 :: Maybe String
 at11 = M.lookup 11 insertedMap

Then you can use M.lookup, M.insert, and many other functions to modify/query the map. This datastructure is also purely functional/persistant (notice how IO is nowhere in the types). That means that we can do something like

  let newMap = M.insert key val oldMap
  in M.union oldMap otherMap

See how we can still use the older version of the map even after inserting something? That's "persistance", we never destroy the older versions of our data structure.

1
  • With the implementation given, myMap will have signature myMap :: M.Map Int Char Oct 29, 2014 at 23:16
4

Just so to avoid someone calling the haskell community arrogant, here is a short break down of the first function you'll need:

new :: (key -> key -> Bool) -> (key -> Int32) -> IO (HashTable key val)

This tells us the following: to create a HashTable for a specific key type key you need to pass a function that checks equality on keys, and a function that computes a hash value for keys. So, if eq and hashit would be the desired functions, the following:

new eq hashit

gives you an empty HashTable in the IO-Monad.

An easier way could be to create a HashTable from a list using one of the predefined hash functions:

 fromList hashInt [(42, "forty-two"), (0, "zero")]

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.