# 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

The first way involves using Haskell’s Tuples and Lists. We can model a key-value pair as a Tuple:

`('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

Another way to model a hash in Haskell is to use the Data.Map module. The Data.Map module is an implementation of map from keys to values using size*-*balanced binary trees under the hood. It's just a fancier (more optimized) version of what we were doing with the lists of tuples.

`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

One thing to note is that the runtime of both these hash implementations. One of the benefits of using a hash/ dictionary structure is that they provide **constant-time** O(1) lookup, regardless of the size or number of key-value pairs. In the first Haskell implementation the runtime will be **linear** O(n) since you need to traverse the entire list and in the second implementation the lookup runtime will be **logarithmic** O(logn) since it uses a binary tree. Therefore, both these implementations are still less optimized than a standard hash in JavaScript.