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.

Joist

What is the origin of those Iterable/ArrayIterator/StringIterator interfaces you are referring to? Are they from some standard javascript framework? Have you defined them yourself? – Benediction

there is no ArrayIterator or StringIterator prototype, there are iteration protocols: developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/… – Flour

@Flour @Benediction [].values() logs ArrayIterator {} in my chromium browser. Is this merely chrome specific behavior? – Joist

("")[Symbol.iterator]() logs StringIterator {}. – Joist

Is this what you are looking for? ecma-international.org/ecma-262/6.0/… – Necessitate

These are just some internal objects which implement the Iterator protocol, consider reading the link that I sent in the previous comment – Flour

@Necessitate Object.getPrototypeOf(Object.getPrototypeOf([][Symbol.iterator]())).isPrototypeOf([].values()) indeed yields true, as well as ("")[Symbol.iterator]() (instead of [].values()). Hence we can't distinguish them by their prototype. – Joist

The prototype is not generally exposed to the user, as @Flour said they are internal objects. I'm not sure that you are dealing with the problem in the correct way, hard to tell without more of your actual code. – Necessitate

Source code is pretty much mumbo jumbo. To keep it simple - are you trying to 'guess' a constructor by its iterator? Not sure what A distinction by prototypes seems not to be possible is supposed to mean. Sure, both iterator protos share the common proto (as almost every object). – Disyllable

@estus ??? Oh, I just saw that you use Angular, that makes sense. – Joist

Should it be a veiled insult? I don't see how a liking for frontend frameworks affects a general JS question. The question isn't clear enough on the problem that you have with your implementation (apart from non-relevant parts like map function). And the implementation isn't self-documented to explain this, foldl function just adds extra complexity and doesn't really help to get the gist of it. If you're trying the guess the proper constructor for relevant iterator (instead of []), the only way to do this is to stringify an iterator... looks fragile to me. – Disyllable

@estus It is not meant to be an insult but a appropriate response to your comment. – Joist

Answer 1

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.

Benediction

I did not understand your answer back then. map is an operation that forms a functor and functors have to preserve the structure of the data they map over. To be iterable is a prerequisite for mapping but it is not sufficient. Thanks! – Joist

Answer 2

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.

Berwickupontweed

"You don't even need to introduce "new types" - I didn't mean to specify new types but to implement them for builtins, e.g. class MonoidalString extends String { concat() {} empty() {} }. It looks weird but is amazingly powerful. Thanks for your answer! – Joist

I guess one would better polyfill String.empty even if that's modifying builtins. – Berwickupontweed

Provided that I get your blessing I'll modify them :D – Joist

I bless you to do so :-) The odds that some library will conflict with the Fantasyland meaning of .empty are relatively small. – Berwickupontweed

"as soon as you're dealing with the iterator itself you should at most map to another iterator" - I'm doing exactly that in my own response. It's an exciting topic. – Joist

Answer 3

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

Necessitate

Sure, I could do this, but I really shouldn't. It is too "hacky", sorry. Thanks for your contribution anyway! – Joist

I wouldn't call it "hacky" (otherwise 99% of the libraries out there are a "hack"), but "not reliable". :) – Necessitate

Answer 4

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.

Supermundane

Answer 5

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.

Campos

Answer 6

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.

Disyllable

This works indeed: Object.getPrototypeOf(Array.prototype[Symbol.iterator]()).isPrototypeOf([].values()) and Object.getPrototypeOf((new Set)[Symbol.iterator]()).isPrototypeOf(new Set([1]).values()). Thanks! – Joist