Where Are the Hashes, Haskell?

How to Model a Hash Data Structure in Haskell

It's true, Haskell doesn’t have hashes. In terms of data types with multiple values, Haskell offers only two: Lists and Tuples. Lists offer an ordered array of elements (all of the same type) and Tuples have a fixed number of elements that are immutable but can be of varying types. Neither of these offers the key-value pair data type that a hash or dictionary does.

Coming from a Javascript background, this was rather strange. After all, Javascript uses the “object” or hash data structure for almost everything… even an array in JavaScript is just a hash with the indices as the keys.

Below are two ways you can use model a key-value pair data structure and look up the values.

Using Tuples and Lists

('key', 'value')

And we can store multiple pairs in a List of these Tuples. This will essentially be our hash:

[('key1', 'value1'), ('key2', 'value2'), ('key3', 'value3')]

Now to look up a value from a key. You can create a search function to find the matching values for a key:

search :: [(String, String)] -> String -> Maybe Answer
search [] key = Nothing
search ((k,v):xs) key = if key == k
then Just v
else search xs key

Actually, Haskell already has a built-in lookup function. It takes in a list of tuples and will return the values that match or nothing if there are no matches. See the example below:

lookup 'key3' [('key1', 'value1'), ('key2', 'value2'), ('key3', 'value3')]Output: Just 'value3'

Using Data.Map

import Data.Map

First, we want to create a map. This will allow us to store key-value pairs and search in them. So a map from Data.Map is essentially a hash in that it stores key-value pairs. However, it's not like a JavaScript hash since it uses a binary tree and not hashing.

To create your map you can either convert a list of tuples like the one above using the fromList function or you can manually add each key-value pair using the insert function:

hash = [(1, "one"), (2, "two"), (3, "three")]

mapFromList = Data.Map.fromList hash

mapManual =
Data.Map.insert 2 "two" .
Data.Map.insert 1 "one" .
Data.Map.insert 3 "three" $ Map.empty

Now we have our map (or essentially hash but really a tree…). To search for values we can simply use the lookup function again with the key we are interested in.

lookup 2 mapFromListOutput: Just 'two'

Runtime Analysis

References