Add *WithIndex instances for StrMap

[Rufflewind]

Add FunctorWithIndex, FoldableWithIndex, and TraversableWithIndex instances for StrMap.

[Rufflewind]

Um, so I tried adding a test that relates foldMapWithIndex f to traverseWithIndex (\k v -> tell (f k v)), but traverseWithIndex kept giving me the reverse of what I expect.

I think traverse is broken:

> runWriter (traverse_ tell ["1", "2", "3"])
(Tuple unit "123")
> runWriter (traverse_ tell (StrMap.fromFoldable [Tuple "a" "1", Tuple "b" "2", Tuple "c" "3"]))
(Tuple unit "321")
> fold (StrMap.fromFoldable [Tuple "a" "1", Tuple "b" "2", Tuple "c" "3"])
"123"

This seems to fix it:

-  traverse f ms = fold (\acc k v -> insert k <$> f v <*> acc) (pure empty) ms
+  traverse f ms = fold (\acc k v -> flip (insert k) <$> acc <*> f v) (pure empty) ms

I'm also a bit wary of sequence <<< mapWithKey as well. It seems to work, but the object is being recreated and JavaScript doesn’t necessarily guarantee the object is insertion-ordered, so this could break on some browsers. It might be better to just define traverse in terms of traverseWithIndex instead.

[paf31]

It might be better to just define traverse in terms of traverseWithIndex instead.

That seems fine to me.

Anyone else have comments here?

[paf31]

I don't know if it's broken, but a Traversable container should be ordered, so we need to pick some ordering, even if it's just alphabetical by key.

[hdgarrood]

At the moment I think it's whatever order the JS engine decides to use in a for-in loop, which is usually insertion order, not by key - but the order used in a for-in loop is not actually defined in the language spec AFAIK.

For example:

> entries = [Tuple "a" 1, Tuple "c" 3, Tuple "b" 2]
> m = SM.fromFoldable entries
> traverse_ logShow m
1
3
2

[paf31]

Seems like we could fix that easily enough by iterating over the sorted keys, right?

[hdgarrood]

Perhaps, but it's potentially quite a large performance cost. I don't see that there's a problem with the current Traversable behaviour or the behaviour in this PR, personally.

[hdgarrood]

If you want fast lookup, insert, & delete, and a traversal with a guaranteed order, you should be using Map String a, I think.

[natefaubion]

Maybe we should deprecate StrMap, and move it to a JavaScript specific module, with the caveat that it matches JS iteration semantics.

[paf31]

Obviously StrMap is unordered. But Foldable says it is ordered. Does that mean we can use fromFoldable :: _ ~> Array to observe the insertion order? That sounds like a bug to me.

[hdgarrood]

I'm not sure I'd agree StrMap is unordered; in my mind it's for JS objects which are being used like maps, and in particular where every property is of a fixed type. So a key part of the API in my mind is that a StrMap has this runtime representation.

JS objects necessarily have an ordering, in that a for-in loop has to iterate over them in some order, even if that order is unspecified and therefore unpredictable. It's maybe not ideal, but given that this is how they work, I think it would be strange for StrMap to do anything other than exhibit the same behaviour.

For the same reason, I'm not sure we should go as far as deprecating StrMap; it can be useful for interop, in particular. (Having said that, it would make me happier to see more Map String a usage where it is more appropriate than StrMap, which imo is most of the time.) It might make sense to move StrMap to a separate package but I'm not sure it would be worth the breakage.

[natefaubion]

I mean deprecating it as a part of purescript-maps. It's clearly useful, but it isn't a general purpose data structure. It only exists as a hack for JS interop. if you wrote FFI bindings for a different backend, would you expect to keep all the same JS semantics?

[natefaubion]

Also, it's frustrating that the API for it and Map are not kept in sync. People use it for very different use cases.

[hdgarrood]

Yes, that's a good point. If we were going to do this we should take the opportunity to rename it too, perhaps JSMap or something.

[hdgarrood]

Anyway we should probably move this to a separate issue at this point.

[Rufflewind]

foldableWithIndexStrMap?

Oops, should be fixed now.

[hdgarrood]

Great, thanks. So should we merge this, make a minor release, and open a new issue to decide what to do about StrMap?

[paf31]

Here is a demonstration of the bug

[Rufflewind]

Here is a demonstration of the bug

Maybe it's better to not think of StrMap as an ordinary unordered map at all, since insertion is not commutative. Rather it behaves more like an array in that regard. (Though technically the standards don't prescribe any ordering.)