hamtmap: A purely functional and persistent hash map

[ bsd3, data-structures, library ] [ Propose Tags ]

A port of Clojure's efficient persistent and hash map data structure to Haskell

[Skip to Readme]




Note: This package has metadata revisions in the cabal description newer than included in the tarball. To unpack the package including the revisions, use 'cabal get'.

Maintainer's Corner

Package maintainers

For package maintainers and hackage trustees


  • No Candidates
Versions [RSS] 0.2, 0.3
Dependencies array (<0.5), base (>=4 && <4.5), deepseq (>=1.1 && <1.5), hashable (>=1.0 && <1.3) [details]
License BSD-3-Clause
Author Kevin Wu Won
Maintainer Kevin Wu Won <exclipy@gmail.com>
Revised Revision 1 made by HerbertValerioRiedel at 2017-03-21T09:36:43Z
Category Data Structures
Home page https://github.com/exclipy/pdata
Uploaded by KevinWuWon at 2011-01-20T07:39:42Z
Reverse Dependencies 1 direct, 0 indirect [details]
Downloads 2363 total (8 in the last 30 days)
Rating (no votes yet) [estimated by Bayesian average]
Your Rating
  • λ
  • λ
  • λ
Status Docs uploaded by user
Build status unknown [no reports yet]

Readme for hamtmap-0.3

[back to package description]

Hash Array Mapped Tries

One of the prominent features of the Clojure language are a set of immutable data structures with efficient manipulation operations. One of the most innovative and important is the persistent hash map based on the hash array mapped trie (HAMT).

This project is a port of this structure to Haskell, as Data.HamtMap. The interface has been kept as consistent as possible with Data.Map.

Basic usage

Here's a demo of what you can do with a HamtMap:

ghci> :m + Data.HamtMap
ghci> empty Data.HashTable.hashString
        -- an empty HamtMap (requires a key hash function)
fromList hashFn []

ghci> insert "foo" 1 it
fromList hashFn [("foo",1)]

ghci> insert "bar" 42 it
fromList hashFn [("foo",1),("bar",42)]

ghci> insert "qux" 123 it
fromList hashFn [("qux",12),("foo",1),("bar",42)]

ghci> insert "qux" 13 it  -- inserting an existing key overwrites by default
fromList hashFn [("qux",13),("foo",1),("bar",42)]

ghci> let a = it
ghci> a ! "foo"

ghci> a ! "baz"  -- using (!) is unsafe
*** Exception: array index out of range: element not in the map

ghci> Data.HamtMap.lookup "bar" a
Just 42

ghci> Data.HamtMap.lookup "baz" a  -- 'lookup' returns a safe Maybe

ghci> adjust succ "foo" a  -- apply a function to a value
fromList hashFn [("qux",13),("foo",2),("bar",42)]

ghci> Data.HamtMap.map succ a  -- apply a function to all values
fromList hashFn [("qux",14),("foo",2),("bar",43)]

ghci> keys a

ghci> elems a

ghci> fromList Data.HashTable.hashString [("a", 1), ("b", 2), ("c", 3)]
fromList hashFn [("b",2),("c",3),("a",1)]

ghci> toList it


To try it yourself, just do the usual:

$ runghc Setup.hs configure --user
$ runghc Setup.hs build
$ runghc Setup.hs install


The single-element operations for the hash map have logarithmic asymtotic runtime complexity. However, it is implemented as a 32-ary tree, which means it never exceeds a depth of 7 nodes, so you can treat them as constant-time operations (for relatively large constants).

How it works

I wrote this code after reading the following explanatory blog posts on how the Clojure version works. They should also provide a decent birds-eye overview of my Haskell implementation.

To do

  • Match Data.Map in completeness
  • Performance tuning
    • Efficient implementations of (//), etc. based on fromList