fixed length circular buffer in haskell

Question

I want to create a fixed length circular buffer of some general type in Haskell. The items in the buffer need to be located one after another in physical memory (not linked list). I want this specific structure because it will improve the chances of all the data getting to the L2 cache on the CPU together. I have read about how Haskell allows for new data types, however it looks like types created using "data" are little more that glorified c structs with pattern matching and associated methods. Is it possible to create low level data structures like the one described above completely in Haskell.

Answer 1

You want a mutable array-like structure, and you particularly want an unboxed one so that the underlying array stores not only pointers to your data, but the items themselves.

Data.Array from the standard array library gives you a version of that, but especially high-performance arrays are available from the vector library: http://hackage.haskell.org/package/vector

The vector library, like ByteString, Text, and a few others, uses a fair amount of low-level ghc-specific primitives under the hood. To just use the library, you shouldn't have to worry about such things yourself. But if you decide that the library doesn't give you what you need, then you can also learn a fair amount in the way of tricks and techniques by reading through its source code for yourself.

Answer 2

Yes, this is certainly possible. The chapter creating a bloom filter from Real World Haskell should be a very good example for these kinds of implementations.