Immutable versions of mutable data structures

[alex-snezhko]

As alluded to in #1383, it would be a good idea to include immutable variants for the currently existing mutable data structures (namely Set and Map). Here is my proposal for these:

• Implement both as balanced binary trees
• ImmutableSet API (mostly mimics existing set):
  • make() -> ImmutableSet<a>
  • add(val: a, set) -> ImmutableSet<a>: create a new set with given value inside of it if it doesn't already exist
  • contains(set) -> Bool
  • remove(val: a, set) -> ImmutableSet<a>: creates new set w/o given value if it exists
  • size(set) -> Number,
  • isEmpty(set) -> Bool,
  • forEach(fn: (a -> Void), set) -> Void (will do an in-order traversal)
  • reduce(fn: ((a, b) -> a), init: a, set) -> a (will do an in-order traversal)
  • filter(fn: (a -> Bool), set) -> ImmutableSet<a>: creates new set with only elements in original that fulfill predicate
  • reject(fn: (a -> Bool), set) -> ImmutableSet<a>: creates new set with only elements in original that don't fulfill predicate
  • toList, fromList, toArray, fromArray: same as in Set (toList/toArray will do in-order traversal)
  • union(set1, set2) -> ImmutableSet<a>
  • diff(set1, set2) -> ImmutableSet<a>
  • intersect(set1, set2) -> ImmutableSet<a>
• ImmutableMap API (mostly mimics existing map)
  • make() -> ImmutableMap<k, v>
  • set(key: k, val: v, map) -> ImmutableMap<k, v> (maybe another name would be more appropriate, "set" kind of implies mutation in my mind although I can't think of a better name)
  • get(key: k, map) -> Option<v>
  • contains(key: k, map) -> Bool
  • remove(key: k, map) -> ImmutableMap<k, v>
  • update(key: k, fn: (Option<v> -> Option<v>), map)
  • size(map) -> Number
  • isEmpty(map) -> Bool
  • forEach(fn: ((k, v) -> Void), map) -> Void (will do an in-order traversal)
  • reduce(fn: ((a, k, v) -> a), init: a, map) -> a (will do an in-order traversal); another note on this: while looking through Map.reduce I was expecting the reducer function to take 2 arguments with a tuple of (key, value) as the second argument rather than 3 arguments; the former seems a bit more intuitive to me. Was this debate already had and the 3-argument option was chosen, or is this still something up in the air?
  • keys(map) -> List<k>
  • values(map) -> List<v>
  • filter(fn: ((k, v) -> Bool), map) -> ImmutableMap<k, v>: creates new map with only elements in original that fulfill predicate
  • reject(fn: ((k, v) -> Bool), set) -> ImmutableMap<k, v>: creates new map with only elements in original that don't fulfill predicate
  • toList, fromList, toArray, fromArray: same as in Map (toList/toArray will do in-order traversal)

Let me know what you think.

[ospencer]

This API looks great to me!

[phated]

I concur with @ospencer!

To answer some of your inline questions/comments:

(maybe another name would be more appropriate, "set" kind of implies mutation in my mind although I can't think of a better name)

I wonder if we should name it insert and rename the mutable Map's function to insert (and deprecate set). @ospencer WDYT?

I was expecting the reducer function to take 2 arguments with a tuple of (key, value) as the second argument rather than 3 arguments; the former seems a bit more intuitive to me. Was this debate already had and the 3-argument option was chosen, or is this still something up in the air?

I don't think it was ever discussed, but all other functions that provide "value" and "index" are separate arguments. I generally don't like tuples in an API because they just add params and are harder to document/name (similar to our destructure discussion in your Priority queue PR). Perhaps we can revisit when we look into the enumerate concept.

[ospencer]

I personally really like get/set, the classic pair! I do see how it could kind of imply mutation, but I'm not too worried about it. To me insert also implies mutation a bit. OCaml uses add/mem/find which some variation of which could maybe work well. Haskell uses insert/member/lookup which I don't think is my favorite.

I think I still prefer get/set/contains for the immutable versions though.

[alex-snezhko]

Following up on this, should both a mutable and immutable version for all data structures be made? If so, should the module naming convention of Immutable___ for the immutable versions and just the structure name for the mutable version be upheld? This would cause breaking changes for Queue and Stack. I'm also not sure how to square this naming scheme with List, since it is immutable but is also arguably the most important data structure in the language, so prepending Immutable to it may make it seem less important than simply List if another module named List would exist (at least to me). Maybe make List an exception and create a MutableList for it?

[phated]

It would be fine to make them but they shouldn't be named like you suggested. We plan to change all of that once the new module system is implemented.

[phated]

@alex-snezhko which other Immutable data structures do you have planned? If you've completed them all, we can close this.

[alex-snezhko]

I think all of the main useful ones have been done now so you can close this issue out.