Sanctuary: Support Native Map Type

[svozza]

Someone recently commented on an old Ramda issue about supporting the native Map type and it got me thinking whether we should do so in Sanctuary. I'm not quite sure how that would look given that the StrMap type we have is more specific that the general JS type but I'm interested to hear everyone's thoughts.

[davidchambers]

I like the idea of a Map k v type, but I'm not sure the built-in Map type makes sense in a world of value-based equality. Consider this example:

> new Map([[[1, 2, 3], 'foo'], [[1, 2, 3], 'bar']])
Map { [ 1, 2, 3 ] => 'foo', [ 1, 2, 3 ] => 'bar' }

Map k v and StrMap v can happily coexist. In fact, StrMap v and Map String v are _conceptually_ equivalent.

[svozza]

Yes. I see what you mean. I guess one way to go would be to change our StrMap functions to also accept Map String v objects. Another would be to only support Maps that use primitive values as keys.

[davidchambers]

I'm happy to leave the role of working with wonky JavaScript constructs to Ramda. It seems inevitable to me that we will eventually provide sanctuary-list, sanctuary-map, and sanctuary-set packages to provide "immutable" data structures with value-based equality semantics.

Friday will be my last day at Plaid. I then intend to be unemployed for three months while my girlfriend and I decide where to live in Europe, so I should have time to create these packages. :)

🇩🇪 🇸🇪 🇳🇱

[davidchambers]

I posted a question on Stack Overflow: Custom equality semantics for Immutable.js data structures. After writing the post I'm almost convinced we could get our desired behaviour by wrapping the native Map type. It could look something like this:

Map k v = { negativeZero :: Maybe v
          , value :: NativeMap k v
          , fantasy-land/equals :: Map k v ~> Map k v -> Boolean
          , fantasy-land/map :: Map k v ~> (k -> a) -> Map a v
          , fantasy-land/bimap :: Map k v ~> (k -> a, v -> b) -> Map a b
          , ...
          }

@scott-christopher wrapped the native Set type in ramda/ramda#1639 (for internal use only). Is there a reason we cannot use a similar approach for externally visible maps and sets in Sanctuary?

[scott-christopher]

Is there a reason we cannot use a similar approach for externally visible maps and sets in Sanctuary?

The only issue I see is that we would probably want to treat it as an immutable structure, which will end up with a bunch of instance cloning to work around the underlying mutable structure.

I've a got a bit of time free over the next week or two and was already looking at implementing some persistent Map and Set types to get a better understanding of a paper I saw recently, so providing that goes to plan they could potentially live under the Sanctuary banner if there's interest.

[davidchambers]

if there's interest

There's most definitely interest! :)

We get into all sorts of trouble treating arrays as sets in Ramda. Once we have access to a Set type we'll be able to define clean versions of functions such as keys, values, and intersection.

[davidchambers]

@scott-christopher, I created sanctuary-js/sanctuary-map and sanctuary-js/sanctuary-set. You're welcome to work on a feature branch of one of these repositories.

[scott-christopher]

I've pushed some code to https://github.com/sanctuary-js/sanctuary-set/tree/pre-0.0.1 which contains an initial pass of implementing two variants of immutable sets, one based on balanced AVL trees and the other is specialised for Int32 values using Patricia tries. It is severely lacking in documentation and the code could do with a good clean-up and sanity check, though I figured it would be good to get some eyes over it sooner rather than later.

I've also got some Map versions of the same implementations which I'll tidy up a bit over the coming days and push up to the other repository.