Barely Functional #3

Tries and Failures

Well, time flies! It’s well over a year ago that I promised to continue my writeups on the ethereum-haskell project with some notes on the merkle trie implementation – but it’s been a long time since I’ve had time or inclination to chip at that project, and my notes have been collecting dust.

Since I’d rather not keep that promise alive for another year, here’s the next best thing: slides from a presentation I gave to Haskell Montreal last year.

The slides are fairly vanilla haskell, running through a few themes and variations on mapping types in Haskell: association lists, tries, Patricia tries, and then on to Merkle tries and other fancy things. One thing I explore a little bit in the slides, but have never totally fleshed out in real life, is the idea of “abstracting over a reference.” At the end of the day, a Merkle tree is just a regular tree with an unusual reference creation / following procedure – and by abstracting those out, you can write algorithms don’t have to care what type of tree they’re working with at all.

I always feel a little bad throwing slides around on the internet, since they suffer a lot without context – if you have any questions, or you’re just interested in talking about how to write extensions to Pandoc in Haskell, feel free to get in touch!