[Haskell-cafe] Compressed Data.Map for more efficient RAM usage?

[Antoine Latter]

On Thu, Feb 16, 2012 at 3:51 PM, Jeremy Shaw <jeremy at n-heptane.com> wrote:
> Sometimes we  want to store very large collection types in RAM -- such as a
> Data.Map or Data.IxSet.
>
> It seems like we could trade-off some speed for space savings by compressing
> the values in RAM.
>
> Lemmih has previously created compact-map:
>
>  http://hackage.haskell.org/package/compact-map
>
> which mightybyte used to create:
>
> https://github.com/mightybyte/compact-ixset
>
> compact-map converts the Haskell values to a more compact binary
> representation. But could we do even better by compressing the bytestrings?
>
> Here is a useless implementation:
>
> http://hpaste.org/63836
>

You could have a re-implemented HashMap which would un-pack the
payload's ByteString constructor into the leaves of the HashMap type
itself.

Then you would save on both the keys and the values.

This assumes you're not using the ordering provided by Data.Map.

Antoine