purescript-object-maps

Map-like data structure with stable insertion order

An ObjectMap k v represents maps from keys of type k to values of type v. It keeps its insertion order and has efficient lookups. The insertion performance however is O(n), equal to the underlying Object but there's also an ST version available with constant insertion performance.

Keys need an instance of EncodeJson for most operations.

Consider the following sample object:

sample :: ObjectMap Int String
sample = OM.empty
  # OM.insert 2 "2"
  # OM.insert 3 "3"
  # OM.insert 1 "1"

The REPL output shows that the order is preserved.

> toArray sample  
[(Tuple 2 "2"),(Tuple 3 "3"),(Tuple 1 "1")]

As previously said, insert has O(n) time complexity. If you want better performance, you can use the function poke of the module Data.ObjectMap.ST which has O(1) average time complexity.

import Data.ObjectMap (ObjectMap)
import Data.ObjectMap.ST as STOM

sample :: ObjectMap Int String
sample = STOM.run do
  m <- STOM.new
  for_ (1..10000) \n -> do
    void $ STOM.poke i (show i) m
  pure m

Since ES2015 JavaScript object properties are guaranteed to preserve insertion order for string keys. This library ensures that every property is interpreted as string by the JavaScript engine. Thus the order can be relied on.

Lookups in native ES5 Maps would rely on JavaScript's equality model which is very different from PureScript's.

Keys are stored twice, in encoded and in raw format. Thus there is no need to decode them back. This was done to avoid relying on roundtrip implementations for the two instances.

This would have been possible too. However, EncodeJson was chosen because it was considered to be more likely that those instances already exist. This is opinionated, though.

It's planned to port more useful functions from Foreign.Object and Data.Map. Any PR's are welcome.