Hacker News Reader

Comment by falcolas | Hacker News Reader

What order do you expect the output to be in when you run flatmap? In doing research on it, I've seen at least three distinct orders. One, results are interleaved. Two, results are depth first. Three, results are breadth first.

If the final order of the output is important (and it frequently is), you have to understand not only "map, then flatten", but the order in which the flatten occurs. And that appears to be implementation dependent.

View on HN

Hmm I would expect the results to be based on the data structure holding the values you're flattening. An in-order depth first traversal if the data structure you're applying it to has an inherent order (e.g a List) and in an undefined order if it's something unordered like a Set.

  List(List(1,2), List(3,4), List(5,6)).flatten -> List(1, 2, 3, 4, 5, 6)
  Set(Set(1,2), Set(3,4), Set(5,6)).flatten -> Set(5, 1, 6, 2, 3, 4)

I would agree, but have a look at this:

http://reactivex.io/documentation/operators/flatmap.html

Granted, this refers to a higher level abstraction on a sequence of realtime events, but as we delve more into green threads and lazy evaluation, these kinds of solutions will become more common.

I really don't believe that there is no obvious way to guarantee the ordering of a given flatten command without looking into its implementation. Of course, I'm admittedly partial to Python's solution - use an explicit list comprehension:

    >>> g = lambda i: (i, -i)
    >>> [x for y in [1, 2, 3] for x in g(y)]
    [1, -1, 2, -2, 3, -3]

If I cared what the order was, I'd expect that I'd have to order it myself, e.g.:

  var foo = things.SelectMany(thing=>thing.SubThings).OrderBy(subthing=>subthing.PropertyICareAbout)

Particularly if things is some interface that I don't know the details of, like IEnumerable, ICollection or IDictionary.

Reply on news.ycombinator.com