While studying various approaches to prefix trees (“tries”), I wrote a small memory and time benchmark of four implementations. Long story short,
generic-trie seems to be the best choice, at least for a
fromList pair, but I was curious to see how very diverse implementation techniques, notably one based on recursion schemes and another using an arrow type internally, lead to different space and time scaling behaviours.
I would love to hear any feedback regarding for example the use of randomized inputs (https://github.com/ocramz/trie-perf/blob/master/bench/Time.hs#L21), and any other improvements.