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 mapFromList
Output: 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.

References

• Haskell : lookup
• Data.Map
• Chapter 13. Data Structures