How to map over arbitrary Iterables?

Question

I wrote a reduce function for Iterables and now I want to derive a generic map that can map over arbitrary Iterables. However, I have encountered an issue: Since Iterables abstract the data source, map couldn't determine the type of it (e.g. Array, String, Map etc.). I need this type to invoke the corresponding identity element/concat function. Three solutions come to mind:

1. pass the identity element/concat function explicitly const map = f => id => concat => xs (this is verbose and would leak internal API though)
2. only map Iterables that implement the monoid interface (that were cool, but introducing new types?)
3. rely on the prototype or constructor identity of ArrayIterator,StringIterator, etc.

I tried the latter but isPrototypeOf/instanceof always yield false no matter what a do, for instance:

Array.prototype.values.prototype.isPrototypeOf([].values()); // false
Array.prototype.isPrototypeOf([].values()); // false

My questions:

• Where are the prototypes of ArrayIterator/StringIterator/...?
• Is there a better approach that solves the given issue?

Edit: [][Symbol.iterator]() and ("")[Symbol.iterator]() seem to share the same prototype:

Object.getPrototypeOf(Object.getPrototypeOf([][Symbol.iterator]())) ====
Object.getPrototypeOf(Object.getPrototypeOf(("")[Symbol.iterator]()))

A distinction by prototypes seems not to be possible.

Edit: Here is my code:

const values = o => keys(o).values();
const next = iter => iter.next();

const foldl = f => acc => iter => {
  let loop = (acc, {value, done}) => done
   ? acc
   : loop(f(acc) (value), next(iter));

  return loop(acc, next(iter));
}


// static `map` version only for `Array`s - not what I desire

const map = f => foldl(acc => x => [...acc, f(x)]) ([]);


console.log( map(x => x + x) ([1,2,3].values()) ); // A

console.log( map(x => x + x) (("abc")[Symbol.iterator]()) ); // B

The code in line A yields the desired result. However B yields an Array instead of String and the concatenation only works, because Strings and Numbers are coincidentally equivalent in this regard.

Edit: There seems to be confusion for what reason I do this: I want to use the iterable/iterator protocol to abstract iteration details away, so that my fold/unfold and derived map/filter etc. functions are generic. The problem is, that you can't do this without also having a protocol for identity/concat. And my little "hack" to rely on prototype identity didn't work out.

@redneb made a good point in his response and I agree with him that not every iterable is also a "mappable". However, keeping that in mind I still think it is meaningful - at least in Javascript - to utilize the protocol in this way, until maybe in future versions there is a mappable or collection protocol for such usage.

Answer 1

Using iter-ops library, you can apply any processing logic, while iterating only once:

import {pipe, map, concat} from 'iter-ops';

// some arbitrary iterables:
const iterable1 = [1, 2, 3];
const iterable2 = 'hello'; // strings are also iterable

const i1 = pipe(
    iterable1,
    map(a => a * 2)
);

console.log([...i1]); //=> 2, 4, 6

const i2 = pipe(
    iterable1,
    map(a => a * 3),
    concat(iterable2)
);

console.log([...i2]); //=> 3, 6, 9, 'h', 'e', 'l', 'l', 'o'

There's a plethora of operators in the library that you can use with iterables.

Answer 2

I know this question was posted quite a while back, but take a look at https://www.npmjs.com/package/fluent-iterable

It supports iterable maps along with ~50 other methods.

Answer 3

Pass the identity element/concat function explicitly const map = f => id => concat => xs

Yes, this is almost always necessary if the xs parameter doesn't expose the functionality to construct new values. In Scala, every collection type features a builder for this, unfortunately there is nothing in the ECMAScript standard that matches this.

only map Iterables that implement the monoid interface

Well, yes, that might be one way to got. You don't even need to introduce "new types", a standard for this already exists with the Fantasyland specification. The downsides however are

• most builtin types (String, Map, Set) don't implement the monoid interface despite being iterable
• not all "mappables" are even monoids!

On the other hand, not all iterables are necessarily mappable. Trying to write a map over arbitrary iterables without falling back to an Array result is doomed to fail.

So rather just look for the Functor or Traversable interfaces, and use them where they exist. They might internally be built on an iterator, but that should not concern you. The only thing you might want to do is to provide a generic helper for creating such iterator-based mapping methods, so that you can e.g. decorate Map or String with it. That helper might as well take a builder object as a parameter.

rely on the prototype or constructor identity of ArrayIterator, StringIterator, etc.

That won't work, for example typed arrays are using the same kind of iterator as normal arrays. Since the iterator does not have a way to access the iterated object, you cannot distinguish them. But you really shouldn't anyway, as soon as you're dealing with the iterator itself you should at most map to another iterator but not to the type of iterable that created the iterator.

Where are the prototypes of ArrayIterator/StringIterator/...?

There are no global variables for them, but you can access them by using Object.getPrototypeOf after creating an instance.

Answer 4

You could compare the object strings, though this is not fool proof as there have been known bugs in certain environments and in ES6 the user can modify these strings.

console.log(Object.prototype.toString.call(""[Symbol.iterator]()));
console.log(Object.prototype.toString.call([][Symbol.iterator]()));

Update: You could get more reliable results by testing an iterator's callability of an object, it does require a fully ES6 spec compliant environment. Something like this.

var sValues = String.prototype[Symbol.iterator];
var testString = 'abc';

function isStringIterator(value) {
  if (value === null || typeof value !== 'object') {
    return false;
  }
  try {
    return value.next.call(sValues.call(testString)).value === 'a';
  } catch (ignore) {}
  return false;
}

var aValues = Array.prototype.values;
var testArray = ['a', 'b', 'c'];

function isArrayIterator(value) {
  if (value === null || typeof value !== 'object') {
    return false;
  }
  try {
    return value.next.call(aValues.call(testArray)).value === 'a';
  } catch (ignore) {}
  return false;
}

var mapValues = Map.prototype.values;
var testMap = new Map([
  [1, 'MapSentinel']
]);

function isMapIterator(value) {
  if (value === null || typeof value !== 'object') {
    return false;
  }
  try {
    return value.next.call(mapValues.call(testMap)).value === 'MapSentinel';
  } catch (ignore) {}
  return false;
}

var setValues = Set.prototype.values;
var testSet = new Set(['SetSentinel']);

function isSetIterator(value) {
  if (value === null || typeof value !== 'object') {
    return false;
  }
  try {
    return value.next.call(setValues.call(testSet)).value === 'SetSentinel';
  } catch (ignore) {}
  return false;
}

var string = '';
var array = [];
var map = new Map();
var set = new Set();
console.log('string');
console.log(isStringIterator(string[Symbol.iterator]()));
console.log(isArrayIterator(string[Symbol.iterator]()));
console.log(isMapIterator(string[Symbol.iterator]()));
console.log(isSetIterator(string[Symbol.iterator]()));
console.log('array');
console.log(isStringIterator(array[Symbol.iterator]()));
console.log(isArrayIterator(array[Symbol.iterator]()));
console.log(isMapIterator(array[Symbol.iterator]()));
console.log(isSetIterator(array[Symbol.iterator]()));
console.log('map');
console.log(isStringIterator(map[Symbol.iterator]()));
console.log(isArrayIterator(map[Symbol.iterator]()));
console.log(isMapIterator(map[Symbol.iterator]()));
console.log(isSetIterator(map[Symbol.iterator]()));
console.log('set');
console.log(isStringIterator(set[Symbol.iterator]()));
console.log(isArrayIterator(set[Symbol.iterator]()));
console.log(isMapIterator(set[Symbol.iterator]()));
console.log(isSetIterator(set[Symbol.iterator]()));

<script src="https://cdnjs.cloudflare.com/ajax/libs/es6-shim/0.35.1/es6-shim.js"></script>

Note: included ES6-shim because Chrome does not currently support Array#values

Answer 5

There's no clean way to do this for arbitrary iterable. It is possible to create a map for built-in iterables and refer to it.

const iteratorProtoMap = [String, Array, Map, Set]
.map(ctor => [
  Object.getPrototypeOf((new ctor)[Symbol.iterator]()),
  ctor]
)
.reduce((map, entry) => map.set(...entry), new Map);

function getCtorFromIterator(iterator) {
  return iteratorProtoMap.get(Object.getPrototypeOf(iterator));
}

With a possibility of custom iterables an API for adding them can also be added.

To provide a common pattern for concatenating/constructing a desired iterable a callback can be provided for the map instead of a constructor.

Answer 6

I have not used the iterable protocol before, but it seems to me that it is essentially an interface designed to let you iterate over container objects using a for loop. The problem is that you are trying to use that interface for something that it was not designed for. For that you would need a separate interface. It is conceivable that an object might be "iterable" but not "mappable". For example, imagine that in an application we are working with binary trees and we implement the iterable interface for them by traversing them say in BFS order, just because that order makes sense for this particular application. How would a generic map work for this particular iterable? It would need to return a tree of the "same shape", but this particular iterable implementation does not provide enough information to reconstruct the tree.

So the solution to this is to define a new interface (call it Mappable, Functor, or whatever you like) but it has to be a distinct interface. Then, you can implement that interface for types that makes sense, such as arrays.