Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Create HashTable in Haskell

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.

like image 220
user3087459 Avatar asked Dec 10 '13 15:12

user3087459


1 Answers

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)]
like image 176
Luis Casillas Avatar answered Sep 27 '22 19:09

Luis Casillas