Where Are the Hashes, 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.

References

--

--

--

I love seafood, exploring new cities, board games and learning to love to code. https://github.com/sarakhandaker/portfolio

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

C# | Assembly, EXE and DLL

A Generic PHP Singleton: The Long Of It

The 1 approach that helped us add QR scanning to a video conference app while drastically reducing…

Setup develop environment on Mac

The Pyramid of Reliable Software

Password Validator With Code

The Zen of grinding LeetCode problems: Day 3 — Getting easier

Key Differences & When to Use Each

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Sara Khandaker

Sara Khandaker

I love seafood, exploring new cities, board games and learning to love to code. https://github.com/sarakhandaker/portfolio

More from Medium

Why not to overload functions in Common Lisp

Operator Overloading in VHDL

Witness the power of Intel® iGPU with Azure IoT Edge for Linux on Windows(EFLOW) & OpenVINO™…