Repository: sanctuary-js/sanctuary
Pull request #214 (2016-05-08 22:11:56)

Add S.keys, S.values and S.pairs
Creating a type-safe version of `R.keys` was mentioned in #142 and now that `StrMap` is available I thought I'd road test it a bit. The implementation of this will probably provoke discussion, firstly because I'm using an ES5 only implementation: I find the Ramda implementation far too complicated for what should be a simple function. Secondly, I've chosen not to implement `S.values` in terms of `S.keys` because I don't think it makes sense to pay the penalty of type checking the object twice.

davidchambers: I'm excited to see these functions; they'll make great additions to the library!

I'd also like to provide `pairs :: StrMap a -> Array (Pair String a)`. I'd like `pairs`, `keys`, and `values` to guarantee consistent ordering. This would mean one could apply `keys` and `values` to a value independently and later zip the results, confident that the pairs will align correctly.

We could rely on the default behaviour of `Array#sort`.

> The implementation of this will probably provoke discussion, firstly because I'm using an ES5 only implementation: I find the Ramda implementation far too complicated for what should be a simple function.

The Ramda implementation is complicated because it works around bugs in certain old browser versions. We needn't do this. The ES3-compatible implementations needn't be complex:

```javascript
//  keys :: StrMap a -> Array String
var keys = function(strMap) {
  var ks = [];
  for (var k in strMap) if (has(k, strMap)) ks.push(k);
  return ks.sort();
}

//  values :: StrMap a -> Array a
var values = function(strMap) {
  var ks = keys(strMap);
  var vs = [];
  for (var idx = 0; idx < ks.length; idx += 1) {
    vs.push(strMap[ks[idx]]);
  }
  return vs;
};

//  pairs :: StrMap a -> Array (Pair String a)
var pairs = function(strMap) {
  var ks = keys(strMap);
  var kvs = [];
  for (var idx = 0; idx < ks.length; idx += 1) {
    kvs.push([ks[idx], strMap[ks[idx]]]);
  }
  return kvs;
}
```

> I don't think it makes sense to pay the penalty of type checking the object twice.

Type checking is currently very slow. I'm confident we can reduce the cost by at least 90%. Once one of us spends a few days making the type checking less naive we'll hopefully be able to stop worrying about paying the cost twice.

kedashoe: > I'd like pairs, keys, and values to guarantee consistent ordering.

What about using @svozza's implementations for these names, and also adding `sortedKeys`, `sortedValues`, `sortedPairs` for when consistent ordering is needed? Iterating over a collection 3-ish times to get `values` feels like a bit much to me.

And what about a simple `for (key in obj)` to get the values in `values`?
davidchambers: I'm open to providing "fast" versions of these functions as well, but I'd like to name them `keys_`, `values_`, and `pairs_`. I'd like the "nice" versions of the functions to have the nice names.

The other option is to sidestep the ordering problem by defining Set and Bag types. We could then define:

```haskell
keys   :: StrMap a -> Set String
values :: StrMap a -> Bag a
pairs  :: StrMap a -> Set (Pair String a)
```

I'd like to stick with arrays, though, so we could guarantee this property:

    forall m :: StrMap a. R.zip(S.keys(m), S.values(m)) = S.pairs(m)

kedashoe: For me the faster versions make sense with the plain names because

1. I almost never care about the order of these functions
2. It seems more natural to me to think "do I care about order here" than "do I care about performance here"

But I see the appeal of ordered results to these functions.. I'm okay either way :shrug:
davidchambers: I might be on the wrong side of the fence here. :)

What do others think? @Avaq? @benperez? @scott-christopher? I'm also interested in your thoughts on the matter, @CrossEye, since we've discussed this in Ramda threads several times.

svozza: I've ES3-ified the implementation. Do you want me to add `pairs` to this PR?

Regarding sorting the keys, it seems odd to impose an the order of keys in a map, if the user really cares she should just sort the result herself.
davidchambers: > I've ES3-ified the implementation.

Thanks. We're still relying on `Array#map` in `values`, though.

> Do you want me to add `pairs` to this PR?

If you'd like to do so, sure! It's up to you. :)

> Regarding sorting the keys, it seems odd to impose an order of keys in a map, if the user really cares she should just sort the result herself.

Sorting the array returned by `keys` is not so important: as you rightly point out the caller can do this after the fact. She cannot, though, sort the values *by their keys* after the fact, as the keys are gone.

The question is whether to support diverging/converging pipelines such as this:

```javascript
                          {x: 0, y: 42}
                               / \
                              /   \
                             /     \
                            /       \
                           /         \
                          /           \
         ['x', 'y'] <=  keys        values  => [0, 42]
                         |             |
                         |             |
                         |             |
                         |             |
                         |             |
                         |             |
     ['X', 'Y'] <=  map(toUpper)   map(inc)  => [1, 43]
                          \           /
                           \         /
                            \       /
                             \     /
                              \   /
                               \ /
                               zip  => [['X', 1], ['Y', 43]]
                                |
                                |
                                |
                                |
                                |
                                |
                            fromPairs  => {X: 1, Y: 43}
```

If we decide not to guarantee consistent ordering, the user can of course use this approach instead:

```javascript
                          {x: 0, y: 42}
                                |
                                |
                                |
                                |
                              pairs  => [['x', 0], ['y', 42]]
                                |
                                |
                                |
                                |
                 map(over(lensIndex(0), toUpper))  => [['X', 0], ['Y', 42]]
                                |
                                |
                                |
                                |
                   map(over(lensIndex(1), inc))  => [['X', 1], ['Y', 43]]
                                |
                                |
                                |
                                |
                            fromPairs  => {X: 1, Y: 43}
```

Both approaches seem fine to me. If we support both, users are free to use whichever feels more natural. Forcing users to *think* about such flows in a certain way doesn't appeal to me (though I realize Sanctuary is an opinionated library which forces users to think a certain way in many other contexts).

Does this clarify my position, @svozza? As I say, I might be on the wrong side of this disagreement. ;)

svozza: I can see where you're coming from with the sorted keys but to me I think if you care about how the elements line up your far more likely to work on them as pairs, as per your second example and probably more like this:

```js
const f = (pair) => [R.toUpper(pair[0]), R.inc(pair[1])];

map(f, toPairs({x: 1, y: 2}));
```

I have a slight preference for leaving the resulting arrays unsorted as iterating over the list three times (if you include the `hasOwnProperty` check) seems like overkill but I'm happy to go with the consensus.
rjmk: On the one hand, I think that it would be nice if Sanctuary avoided non-deterministic functions. On the other hand, it seems odd for Sanctuary to impose arbitrary structure on values. I think I like the `Set` / `Bag` solution most. I think if people want the values ordered by the keys, but don't want to `map
svozza: `S.toPairs` added!
davidchambers: > `S.toPairs` added!

Very exciting! I'm not sure about the name, though. In [Data.HashMap][1] the three functions are named [`keys`][2], [`elems`][3], and [`assocs`][4]/[`toList`][5] (I don't know why there are two names for this one).

Since all the Sanctuary functions live in a single namespace `S.toArray` is not an option. I like `S.pairs`, though, rather than than `S.toPairs`. It matches `S.keys` and `S.values` (which are not `S.toKeys` and `S.toValues` after all). What do you think?


[1]: https://hackage.haskell.org/package/hashmap-1.3.0.1/docs/Data-HashMap.html
[2]: https://hackage.haskell.org/package/hashmap-1.3.0.1/docs/Data-HashMap.html#v:keys
[3]: https://hackage.haskell.org/package/hashmap-1.3.0.1/docs/Data-HashMap.html#v:elems
[4]: https://hackage.haskell.org/package/hashmap-1.3.0.1/docs/Data-HashMap.html#v:assocs
[5]: https://hackage.haskell.org/package/hashmap-1.3.0.1/docs/Data-HashMap.html#v:toList

svozza: Yep, I prefer `S.pairs`, the only reason I had it the other way was because I was following Ramda. 
svozza: :zap: Think I've everything except adding `.sort()` to the docs.

Patch:
diff --git a/index.js b/index.js
index b0dcde5..aa39e98 100644
--- a/index.js
+++ b/index.js
@@ -27,6 +27,8 @@
 //.
 //.     R.map(S.toUpper, S.head(words))
 //.
+//. Sanctuary is designed to work in Node.js and in ES5-compatible browsers.
+//.
 //. ## Types
 //.
 //. Sanctuary uses Haskell-like type signatures to describe the types of
@@ -2746,6 +2748,52 @@
         return filter(is(type), Just(x));
       });
 
+  //# keys :: StrMap a -> Array String
+  //.
+  //. Returns the keys of the given string map, in arbitrary order.
+  //.
+  //. ```javascript
+  //. > S.keys({b: 2, c: 3, a: 1}).sort()
+  //. ['a', 'b', 'c']
+  //. ```
+  S.keys =
+  def('keys',
+      {},
+      [$.StrMap(a), $.Array($.String)],
+      Object.keys);
+
+  //# values :: StrMap a -> Array a
+  //.
+  //. Returns the values of the given string map, in arbitrary order.
+  //.
+  //. ```javascript
+  //. > S.values({a: 1, c: 3, b: 2}).sort()
+  //. [1, 2, 3]
+  //. ```
+  S.values =
+  def('values',
+      {},
+      [$.StrMap(a), $.Array(a)],
+      function(strMap) {
+        return Object.keys(strMap).map(function(key) { return strMap[key]; });
+      });
+
+  //# toPairs :: StrMap a -> Array (Pair String a)
+  //.
+  //. Returns the key–value pairs of the given string map, in arbitrary order.
+  //.
+  //. ```javascript
+  //. > S.pairs({b: 2, a: 1, c: 3}).sort()
+  //. [['a', 1], ['b', 2], ['c', 3]]
+  //. ```
+  S.pairs =
+  def('pairs',
+      {},
+      [$.StrMap(a), $.Array($.Pair($.String, a))],
+      function(strMap) {
+        return Object.keys(strMap).map(function(k) { return [k, strMap[k]]; });
+      });
+
   //. ### Number
 
   //# negate :: ValidNumber -> ValidNumber


Test patch:
diff --git a/test/keys.js b/test/keys.js
new file mode 100644
index 0000000..b8f6eaf
--- /dev/null
+++ b/test/keys.js
@@ -0,0 +1,59 @@
+'use strict';
+
+var throws = require('assert').throws;
+
+var eq = require('./utils').eq;
+var errorEq = require('./utils').errorEq;
+var S = require('..');
+
+
+describe('keys', function() {
+
+  it('is a unary function', function() {
+    eq(typeof S.keys, 'function');
+    eq(S.keys.length, 1);
+  });
+
+  it('type checks its arguments', function() {
+    throws(function() { S.keys('xxx'); },
+           errorEq(TypeError,
+                   'Invalid value\n' +
+                   '\n' +
+                   'keys :: StrMap a -> Array String\n' +
+                   '        ^^^^^^^^\n' +
+                   '           1\n' +
+                   '\n' +
+                   '1)  "xxx" :: String\n' +
+                   '\n' +
+                   'The value at position 1 is not a member of ‘StrMap a’.\n'));
+
+    throws(function() { S.keys({a: '1', b: 2, c: '3'}); },
+           errorEq(TypeError,
+                   'Type-variable constraint violation\n' +
+                   '\n' +
+                   'keys :: StrMap a -> Array String\n' +
+                   '               ^\n' +
+                   '               1\n' +
+                   '\n' +
+                   '1)  "1" :: String\n' +
+                   '    2 :: Number, FiniteNumber, NonZeroFiniteNumber, Integer, ValidNumber\n' +
+                   '    "3" :: String\n' +
+                   '\n' +
+                   'Since there is no type of which all the above values are members, the type-variable constraint has been violated.\n'));
+  });
+
+  it("returns an array of the given object's own keys", function() {
+    eq(S.keys({}), []);
+    eq(S.keys({a: 1, b: 2, c: 3}).sort(), ['a', 'b', 'c']);
+  });
+
+  it('does not include prototype properties', function() {
+    var proto = {a: 1, b: 2};
+    var obj = Object.create(proto);
+    obj.c = 3;
+    obj.d = 4;
+
+    eq(S.keys(obj).sort(), ['c', 'd']);
+  });
+
+});
diff --git a/test/pairs.js b/test/pairs.js
new file mode 100644
index 0000000..edb80c6
--- /dev/null
+++ b/test/pairs.js
@@ -0,0 +1,63 @@
+'use strict';
+
+var throws = require('assert').throws;
+
+var eq = require('./utils').eq;
+var errorEq = require('./utils').errorEq;
+var S = require('..');
+
+
+describe('toPairs', function() {
+
+  var comparePairsAsc = function(a, b) {
+    return a[0] < b[0] ? -1 : a[0] > b[0] ? 1 : 0;
+  };
+
+  it('is a unary function', function() {
+    eq(typeof S.pairs, 'function');
+    eq(S.pairs.length, 1);
+  });
+
+  it('type checks its arguments', function() {
+    throws(function() { S.pairs('xxx'); },
+           errorEq(TypeError,
+                   'Invalid value\n' +
+                   '\n' +
+                   'pairs :: StrMap a -> Array (Pair String a)\n' +
+                   '         ^^^^^^^^\n' +
+                   '            1\n' +
+                   '\n' +
+                   '1)  "xxx" :: String\n' +
+                   '\n' +
+                   'The value at position 1 is not a member of ‘StrMap a’.\n'));
+
+    throws(function() { S.pairs({a: '1', b: 2, c: '3'}); },
+           errorEq(TypeError,
+                   'Type-variable constraint violation\n' +
+                   '\n' +
+                   'pairs :: StrMap a -> Array (Pair String a)\n' +
+                   '                ^\n' +
+                   '                1\n' +
+                   '\n' +
+                   '1)  "1" :: String\n' +
+                   '    2 :: Number, FiniteNumber, NonZeroFiniteNumber, Integer, ValidNumber\n' +
+                   '    "3" :: String\n' +
+                   '\n' +
+                   'Since there is no type of which all the above values are members, the type-variable constraint has been violated.\n'));
+  });
+
+  it('returns an array with the key value pairs of each property of the object', function() {
+    eq(S.pairs({}), []);
+    eq(S.pairs({a: 1, b: 2, c: 3}).sort(comparePairsAsc), [['a', 1], ['b', 2], ['c', 3]]);
+  });
+
+  it('does not include prototype properties', function() {
+    var proto = {a: 1, b: 2};
+    var obj = Object.create(proto);
+    obj.c = 3;
+    obj.d = 4;
+
+    eq(S.pairs(obj).sort(comparePairsAsc), [['c', 3], ['d', 4]]);
+  });
+
+});
diff --git a/test/values.js b/test/values.js
new file mode 100644
index 0000000..d01bb43
--- /dev/null
+++ b/test/values.js
@@ -0,0 +1,59 @@
+'use strict';
+
+var throws = require('assert').throws;
+
+var eq = require('./utils').eq;
+var errorEq = require('./utils').errorEq;
+var S = require('..');
+
+
+describe('values', function() {
+
+  it('is a unary function', function() {
+    eq(typeof S.values, 'function');
+    eq(S.values.length, 1);
+  });
+
+  it('type checks its arguments', function() {
+    throws(function() { S.values('xxx'); },
+           errorEq(TypeError,
+                   'Invalid value\n' +
+                   '\n' +
+                   'values :: StrMap a -> Array a\n' +
+                   '          ^^^^^^^^\n' +
+                   '             1\n' +
+                   '\n' +
+                   '1)  "xxx" :: String\n' +
+                   '\n' +
+                   'The value at position 1 is not a member of ‘StrMap a’.\n'));
+
+    throws(function() { S.values({a: '1', b: 2, c: '3'}); },
+           errorEq(TypeError,
+                   'Type-variable constraint violation\n' +
+                   '\n' +
+                   'values :: StrMap a -> Array a\n' +
+                   '                 ^\n' +
+                   '                 1\n' +
+                   '\n' +
+                   '1)  "1" :: String\n' +
+                   '    2 :: Number, FiniteNumber, NonZeroFiniteNumber, Integer, ValidNumber\n' +
+                   '    "3" :: String\n' +
+                   '\n' +
+                   'Since there is no type of which all the above values are members, the type-variable constraint has been violated.\n'));
+  });
+
+  it("returns an array of the given object's own values", function() {
+    eq(S.values({}), []);
+    eq(S.values({a: 1, b: 2, c: 3}).sort(), [1, 2, 3]);
+  });
+
+  it('does not include prototype values', function() {
+    var proto = {a: 1, b: 2};
+    var obj = Object.create(proto);
+    obj.c = 3;
+    obj.d = 4;
+
+    eq(S.values(obj).sort(), [3, 4]);
+  });
+
+});