## Blog: Mr. Mathiesen

A SAFE and idiomatic (no corner cutting or strange stuff under the hood) implementation of an immutable array in Haskell aiming for an idiomatic low memory footprint by storing chunks of 256 elements in a fixed vector (data VF256 a = VF … , i00 :: a, … , iFF :: a }) by sharing a single constructor. A side-effect of this approach, is that we achieve O(log₂₅₆ n) asymptotic time complexity for most operations.

Futhermore, in order to avoid the usage of the following pattern data Present a = Yes a | No for when an element is present as it will add a constructor (overhead) for each element. This is achieved with the usage of ⊥ (bottom) combined with Haskells lazy nature as well as a bitmap, where each of the 256 elements presence are stored as a single bit.

Remark: Please see the References below for Simon Marlows answer at Stack Overflow with regard of memory footprint of Haskell data types.

### References:

• Stack Overflow:
• GitLab - Glasgow Haskell Compiler:
• GitLab - SPISE MISU ApS: