Difficulty: *
This exercise was about building an implementation of Hash Array Mapped Tries (HAMTs) in Haskell. I wanted to ensure that the resulting code mirrored that of a highly tuned implementation in your language of choice. Thus, students had to implement bitmaps and hash indexing using via bit twiddling, using Data.Bits. My original solution also used arrays to perform constant-time subtree indexing, and to implement clash sets, but I decided to resort to lists in the end, as I don’t cover arrays in the lectures. It’s trivial to change data types and replace !! with !, for example, if you want to use arrays instead.
The key design decision revolves around what to do when you get a clash in the leaves of the trie. I contemplated a version that extends the trie using a separate hashing function, but that gets quite messy and isn’t guaranteed to solve the problem anyway. So I elected to stick with clashes, here using lists.
Students were given a crib sheet on how to use Data.Bits the day before the test, which is included here with the spec. The test is similar in nature to an interim test that was sat before the Christmas break. Therefore, I felt that students were especially well prepared for this test, which is why I’ve rated it one-star.
The exercise was generally well done: 17 students out of 188 scored full marks, with the average being around 73%. Lots of students (around 40) scored 90%+, so the distribution was lumped quite significantly to the right compared with past tests. The hardest part seemed to revolve around having to re-hash when you need to re-insert an item into the tree.
The version here, including the marking scheme, is exactly as was sat, with the exception of a small fix to one of the diagrams.
Background reading (Data.Bits)
Specification
Template
Types module
HashFunctions module
Test Data module
More Information
HAMTs are a relatively recent ‘discovery’, although the main ideas are essentially elaborations on established textbook algorithms and data structures. There are lots of on-line resources describing HAMTs and their variants, which can easily be found using a search engine. In preparing the exercise I found the Youtube video of Phil Nash’s talk at C++ Now, 2017, particularly useful. Thank you, Phil!