This series is a rather lazy exploration of how to work with sparse data in Morton order. Along the way we'll be composing a number of useful data structures and twiddling a lot of bits.
Revisiting Matrix Multiplication
As of March 2020, School of Haskell has been switched to read-only mode.
Part I: Bit Shuffling with Lenses and Isomorphisms 25 Aug 2013Edward Kmett
This post shows how we can define Morton Order via bit shuffling operations.Part II: The Zen of Z-Ordering 25 Aug 2013Edward Kmett
This post shows how you can perform bit shuffling by not actually shuffling at all.Part III: Extending Vector 25 Aug 2013Edward Kmett
This post is an exploration of how to extend the Vector package with hybrid vectors and custom stream fusion combinators.Part IV: IntMap!? 25 Aug 2013Edward Kmett
This post explores how you can use the notion of a "most significant difference" to power a data structure like the venerable Data.IntMap.Part V: Heaps of Performance 16 Nov 2014Edward Kmett
This post focuses on introducing pairing heaps and how to bootstrap a data structure.Part VI: A Most Significant Comparison 25 Aug 2013Edward Kmett
This post summarizes what we've learned so far about Morton ordering, and compacts all of the bit twiddling of the first 2 parts into a `compare` like operator for most significant bits.
