<p>There are high order function on lists, such as map, find, reduce, in some languages. If the result of one such function is piped into another such function, there are multiple possible evaluation orders. In practice, it might be wise to only use them with functions without side effects. But if the programmer doesn't follow this guideline, have there been languages seriously document what would happen, even if it only says the behavior is undefined?</p>
<p>I restrict the question to only languages using enumerables, iterables, iterators, or the like, at least sometimes, because before they were invented, only one evaluation order is expected. And of course, it only applies to languages that side effects are possible.</p>
<p>One example is Python 3, where the apparently similar <code>map</code> and list comprehension have different evaluation orders:</p>
<pre class="lang-python prettyprint-override"><code>def regen(x):
  global k
  k=k+1
  return k

k=0;print(list(map(regen,map(regen,range(10)))))
k=0;print([regen(x) for x in [regen(x) for x in range(10)]])
</code></pre>
<p><a href="https://tio.run/##K6gsycjPM/7/PyU1TaEoNT01T6NC04pLQSE9Jz8pMUchG8jMts3WNgTSRaklpUV5QCGubFsD64KizLwSjZzM4hKN3MQCDbBeHQSrKDEvPVXD0EATBJA0RMMsUUjLL1KoUMjMU8AiBNcdG6v5/z8A" rel="nofollow noreferrer" title="Python 3 – Try It Online">Try it online!</a></p>
<p>Output:</p>
<pre><code>[2, 4, 6, 8, 10, 12, 14, 16, 18, 20]
[11, 12, 13, 14, 15, 16, 17, 18, 19, 20]
</code></pre>
<p>Even though it is not a very reasonable difference, I don't think it surprises anyone who had an idea of how Python 3 uses lists and iterators. But there are theoretical optimizations that may prefer another evaluation order. Have there been languages promised absolute or relative stability on one particular evaluation order, explicitly stated they might be changed later, or had any notes on this problem at all?</p>

<undefined-behavior><iterators><lazy-evaluation>
Has there been languages that explicitly document the order of evaluation of high order functions on enumerables?
CC BY-SA 4.0
2024-01-29T15:16:13.347Z
[The Haskell version](https://gist.github.com/roboguy13/4f0c7a0ff93ba24d19110266e7fa5dd8) would use `traverse`, which is [specified to run the *effects* left-to-right in the data structure](https://hackage.haskell.org/package/base-4.19.0.0/docs/Data-Traversable.html#v:traverse). Also, `=<<` will generally "perform the effects" of the right argument before the left argument. This is slightly different than the _evaluation_ order, but I think this is still what you're talking about because this is the order in which it will perform effects. Not sure if this counts as "an iterable," though.
David Young
CC BY-SA 4.0
2024-01-29T15:34:18.607Z
The behavior of the first one can be obtained like this (but note that the effects in the traversal is still happening in the same order): `print =<< traverse (regen <=< regen) [0..9]`. One way to think of `<=<` is as the composition operator for "effectful" functions. So, writing in Haskell, it looks like Python is automatically turning `traverse f =<< traverse g xs` into `traverse (f <=< g) xs`. This is a perfectly fine transformation if `f` and `g` are non-effectful. But if they are effectful, those two things will be different in general.
David Young
CC BY-SA 4.0
2024-01-29T15:48:09.840Z
Incidentally, this also shows why Python would do this: after Python does its "transformation," it only performs one list traversal. This process seems very similar to what's called ["list fusion" (or "stream fusion")](https://www.researchgate.net/publication/221241130_Stream_Fusion_From_Lists_to_Streams_to_Nothing_at_All). In Haskell terms, this transformation is valid for something like `map` (since, in Haskell, we aren't able to perform effects when we are `map`ing), however it would change the meaning of the program if we applied something like it to `traverse`.
David Young
CC BY-SA 4.0
2024-01-29T16:14:00.953Z
I'm not sure if this matches the spirit of the question, but enums usually define a traversal in order of definition and from that the answer to your question is a straight-forward derivation, right? So my question would be would it make sense to talk about that combination explicitly?
feldentm
CC BY-SA 4.0
2024-01-29T16:25:29.713Z
@DavidYoung The map version is the obvious default implementation if you choose the input and output to be iterators, because if you access and generate data in the later part of the list that haven't been requested yet, you lose the advantage of using iterators compared to lists. Or we could say it's a lazy iterator. They don't need to consider optimization to make it work like this. The question is whether they want to stick with this if some future optimizations work best with another order.  On the other hand, in Python 2 map returns a list, so the output agrees with list comprehension.
user23013
CC BY-SA 4.0
2024-01-29T16:32:38.470Z
@feldentm Maybe I was not clear. The question is basically about, if a list is mapped two times, what's the order of executing the unit operations, like element-wise or map-layer-wise? It obviously works in one way but is it formally stable? I don't think it's related to enums, but I don't quite understand your comment. (What is "that combination"?)
user23013
CC BY-SA 4.0
2024-01-29T17:40:16.643Z
The example doesn’t really seem to have anything to do with *higher-order functions*, but evaluation of lists and generators. Is that what the question is meant to be about? e.g. the same result comes from `k=0;print(list(regen(x) for x in (regen(x) for x in range(10))))` for I think obvious reasons that it couldn’t do anything else (same for the list comprehension). Is this specifically about the `map` function, which as a lazy generator must be exactly equivalent? Or is there another example (different higher-order function?)  that makes your purpose clearer?
Michael Homer
CC BY-SA 4.0
2024-01-29T18:28:58.637Z
@user23013 I think you got my point anyway. The combination of how the functions work and how the specific enumerables work are independent. Hence, I do not see the point. Having observable side-effects in an API inspired by functional programming almost always means digging into the implementation to see what happens in that case. I will not provide an answer as I do not share the perception underlying the question.
feldentm
CC BY-SA 4.0
2024-01-29T19:44:35.993Z
@feldentm I don't get the previous comment. But yes, it is "having observable side-effects in an API inspired by functional programming", probably advisable to not do that in practical programming. But the question is whether someone has made the advise official, like the C++ undefined behaviors.
user23013
CC BY-SA 4.0
2024-01-29T19:56:52.260Z
@MichaelHomer Yes, the existence of generators is crucial to the question. High order functions refer to `regen` as a parameter to `map` or list comprehension, which must also exist to get a real difference. I said in a previous comment that this is the obvious default implementation with iterators. But it might not be the most efficient one, and I want to know if there is any saying about what is definitely stable and what may change.
user23013
CC BY-SA 4.0
2024-01-29T19:59:00.910Z
@MichaelHomer An example is the Python 2 to Python 3 transition. It has changed map from list to generator. It's currently the most obvious behavior of generators. But it may not be expected if you are in the Python 2 era, unless someone documents something similar.
user23013
CC BY-SA 4.0
2024-01-29T20:09:00.930Z
@MichaelHomer Comparing map and list comprehension might be a distraction. I intended to show both behaviors existed somewhere. But the real question is, for one usage, say map, completely unrelated to list comprehension, whether there is a saying that it could potentially change to something else, not like Python 3 generators, and not like Python 2 lists, but something new, like how C++ says something is undefined and the implementations could be different, or whether there is a saying that it would not ever make such a change again in versions that is backward compatible to a certain degree.
user23013
CC BY-SA 4.0
2024-01-29T20:41:10.777Z
@MichaelHomer I referred to "enumerables", a .NET term, which is more general, instead of generators in the title. An example that is neither list or lazy generator is shell scripts, working on streams of characters in parallel. It has annoying edge cases such as sometimes you have to use `stdbuf` to unbuffer a coproc, and another command following `head -n` may not be reliable because `head` may consume some more characters and could not put them back. But new general purpose languages tend to special-case string operations instead of making a version based on iterators as efficient.
user23013
CC BY-SA 4.0
2024-01-29T21:50:49.800Z
I don't quite understand... I mean, they could always *theoretically* add a new feature that completely changes existing code. I don't see how that is related to undefined behavior, since you *can't* give a definition for behavior that only hypothetically exists in the future.
David Young
CC BY-SA 4.0
2024-02-03T18:01:46.290Z
@DavidYoung If you can't give a definition yet, you can leave it undefined and say exactly it is undefined, to make it more permissive. But I think you are right. This question might be not as useful as I thought. But I'm leave it here, because saying a function would return a set of elements with unspecified computation order is an useful and understandable expression, and it's plausible that some languages would do that in some rare cases.
user23013
<p>Python from your examples defines this order, but any lazy system produces the same result and other languages also provide it. .NET is an example of defining it for what are strictly higher-order operations, if that is the critical element.</p>

<p>First, note that this is really the order of a <em>generator</em>, not particularly about higher-order functions. Using a generator directly:</p>
<pre class="lang-python prettyprint-override"><code>&gt;&gt;&gt; k=0;print(list(regen(x) for x in (regen(x) for x in range(10))))
[2, 4, 6, 8, 10, 12, 14, 16, 18, 20]
</code></pre>
<p>produces the same order as your <code>map</code> example, and it's clear why it has to: each generator asks its source for the next value before producing its own. There isn't anywhere for a backlog of values to go, and no way to generate ahead of time, so this is the only possible ordering.</p>
<p>The list-comprehension version, which just swaps some parentheses for square brackets, necessarily produces the list object <em>first</em> — it's a single expression producing one value — so that the iterator of the list can be obtained.</p>
<p><code>map</code> is, from Python 3, a generator, so it has the on-demand behaviour of a generator. This is necessary to allow mapping over infinite streams, for example (which was the purpose of making it into a generator):</p>
<pre class="lang-python prettyprint-override"><code>&gt;&gt;&gt; for v in map(lambda x,y: (x,y), 'abc', itertools.count())): print(v)
...
('a', 0)
('b', 1)
('c', 2)
</code></pre>
<p>While not explicitly defined as such for <code>map</code> because the translation is not simple when mapping over multiple functions, it <em>is</em> <a href="https://docs.python.org/3/library/functions.html#filter" rel="nofollow noreferrer">documented for its higher-order friend <code>filter</code></a>:</p>
<blockquote>
<p>Note that <code>filter(function, iterable)</code> is equivalent to the generator expression <code>(item for item in iterable if function(item))</code> if function is not <code>None</code> and <code>(item for item in iterable if item)</code> if function is <code>None</code>.</p>
</blockquote>
<p>However, <code>map</code> <em>is</em> defined to stop when the shortest iterable does, so it does need to work one step at a time, which has essentially the same result.</p>
<hr />
<p>This is the order you would expect for any lazy generator in any language, not specifically something with higher-order functions. This is also the order you get from C#'s LINQ operations, for example:</p>
<pre class="lang-csharp prettyprint-override"><code>k = 0; Console.WriteLine(String.Join(&quot;,&quot;, Enumerable.Range(1,10).Select(regen).Select(regen)));
k = 0; Console.WriteLine(String.Join(&quot;,&quot;, from x in (from x in Enumerable.Range(1, 10) select regen(x)) select regen(x)));
k = 0; Console.WriteLine(String.Join(&quot;,&quot;, Enumerable.Select(Enumerable.Select(Enumerable.Range(1,10), regen), regen)));
</code></pre>
<pre class="lang-none prettyprint-override"><code>2,4,6,8,10,12,14,16,18,20
2,4,6,8,10,12,14,16,18,20
2,4,6,8,10,12,14,16,18,20
</code></pre>
<p>In .NET, this arises from the implementation of <a href="https://learn.microsoft.com/en-us/dotnet/api/system.linq.enumerable.range?view=net-8.0" rel="nofollow noreferrer">Enumerable.Range</a> and IEnumerable's <a href="https://learn.microsoft.com/en-us/dotnet/api/system.linq.enumerable.select?view=net-8.0" rel="nofollow noreferrer">Select extension method</a>, which do explicitly guarantee deferred execution.</p>
<hr />
<p>This ordering is a necessity of lazy evaluation, which is what generators are for, and those systems do specifically not consume more values than asked for. It's not really about higher-order functions, as the literal generator expression from Python shows.</p>

CC BY-SA 4.0
2024-01-29T19:47:20.707Z
2024-01-29T19:47:20.707Z
Michael Homer
# Has there been languages that explicitly document the order of evaluation of high order functions on enumerables?
Posted by: username_0 on 2024-01-29
There are high order function on lists, such as map, find, reduce, in some languages. If the result of one such function is piped into another such function, there are multiple possible evaluation orders. In practice, it might be wise to only use them with functions without side effects. But if the programmer doesn't follow this guideline, have there been languages seriously document what would happen, even if it only says the behavior is undefined?
I restrict the question to only languages using enumerables, iterables, iterators, or the like, at least sometimes, because before they were invented, only one evaluation order is expected. And of course, it only applies to languages that side effects are possible.
One example is Python 3, where the apparently similar map and list comprehension have different evaluation orders:
def regen(x):
  global k
  k=k+1
  return k

k=0;print(list(map(regen,map(regen,range(10)))))
k=0;print([regen(x) for x in [regen(x) for x in range(10)]])

Try it online!
Output:
[2, 4, 6, 8, 10, 12, 14, 16, 18, 20]
[11, 12, 13, 14, 15, 16, 17, 18, 19, 20]

Even though it is not a very reasonable difference, I don't think it surprises anyone who had an idea of how Python 3 uses lists and iterators. But there are theoretical optimizations that may prefer another evaluation order. Have there been languages promised absolute or relative stability on one particular evaluation order, explicitly stated they might be changed later, or had any notes on this problem at all?
**Tags:** undefined-behavior iterators lazy-evaluation
> **Comments:**
> **username_1**: [The Haskell version](https://gist.github.com/roboguy13/4f0c7a0ff93ba24d19110266e7fa5dd8) would use `traverse`, which is [specified to run the *effects* left-to-right in the data structure](https://hackage.haskell.org/package/base-4.19.0.0/docs/Data-Traversable.html#v:traverse). Also, `=<<` will generally "perform the effects" of the right argument before the left argument. This is slightly different than the _evaluation_ order, but I think this is still what you're talking about because this is the order in which it will perform effects. Not sure if this counts as "an iterable," though.  
> **username_1**: The behavior of the first one can be obtained like this (but note that the effects in the traversal is still happening in the same order): `print =<< traverse (regen <=< regen) [0..9]`. One way to think of `<=<` is as the composition operator for "effectful" functions. So, writing in Haskell, it looks like Python is automatically turning `traverse f =<< traverse g xs` into `traverse (f <=< g) xs`. This is a perfectly fine transformation if `f` and `g` are non-effectful. But if they are effectful, those two things will be different in general.  
> **username_1**: Incidentally, this also shows why Python would do this: after Python does its "transformation," it only performs one list traversal. This process seems very similar to what's called ["list fusion" (or "stream fusion")](https://www.researchgate.net/publication/221241130_Stream_Fusion_From_Lists_to_Streams_to_Nothing_at_All). In Haskell terms, this transformation is valid for something like `map` (since, in Haskell, we aren't able to perform effects when we are `map`ing), however it would change the meaning of the program if we applied something like it to `traverse`.  
> **username_2**: I'm not sure if this matches the spirit of the question, but enums usually define a traversal in order of definition and from that the answer to your question is a straight-forward derivation, right? So my question would be would it make sense to talk about that combination explicitly?  
> **username_0**: @DavidYoung The map version is the obvious default implementation if you choose the input and output to be iterators, because if you access and generate data in the later part of the list that haven't been requested yet, you lose the advantage of using iterators compared to lists. Or we could say it's a lazy iterator. They don't need to consider optimization to make it work like this. The question is whether they want to stick with this if some future optimizations work best with another order.  On the other hand, in Python 2 map returns a list, so the output agrees with list comprehension.  
> **username_0**: @feldentm Maybe I was not clear. The question is basically about, if a list is mapped two times, what's the order of executing the unit operations, like element-wise or map-layer-wise? It obviously works in one way but is it formally stable? I don't think it's related to enums, but I don't quite understand your comment. (What is "that combination"?)  
> **username_3**: The example doesn’t really seem to have anything to do with *higher-order functions*, but evaluation of lists and generators. Is that what the question is meant to be about? e.g. the same result comes from `k=0;print(list(regen(x) for x in (regen(x) for x in range(10))))` for I think obvious reasons that it couldn’t do anything else (same for the list comprehension). Is this specifically about the `map` function, which as a lazy generator must be exactly equivalent? Or is there another example (different higher-order function?)  that makes your purpose clearer?  
> **username_2**: @user23013 I think you got my point anyway. The combination of how the functions work and how the specific enumerables work are independent. Hence, I do not see the point. Having observable side-effects in an API inspired by functional programming almost always means digging into the implementation to see what happens in that case. I will not provide an answer as I do not share the perception underlying the question.  
> **username_0**: @feldentm I don't get the previous comment. But yes, it is "having observable side-effects in an API inspired by functional programming", probably advisable to not do that in practical programming. But the question is whether someone has made the advise official, like the C++ undefined behaviors.  
> **username_0**: @MichaelHomer Yes, the existence of generators is crucial to the question. High order functions refer to `regen` as a parameter to `map` or list comprehension, which must also exist to get a real difference. I said in a previous comment that this is the obvious default implementation with iterators. But it might not be the most efficient one, and I want to know if there is any saying about what is definitely stable and what may change.  
> **username_0**: @MichaelHomer An example is the Python 2 to Python 3 transition. It has changed map from list to generator. It's currently the most obvious behavior of generators. But it may not be expected if you are in the Python 2 era, unless someone documents something similar.  
> **username_0**: @MichaelHomer Comparing map and list comprehension might be a distraction. I intended to show both behaviors existed somewhere. But the real question is, for one usage, say map, completely unrelated to list comprehension, whether there is a saying that it could potentially change to something else, not like Python 3 generators, and not like Python 2 lists, but something new, like how C++ says something is undefined and the implementations could be different, or whether there is a saying that it would not ever make such a change again in versions that is backward compatible to a certain degree.  
> **username_0**: @MichaelHomer I referred to "enumerables", a .NET term, which is more general, instead of generators in the title. An example that is neither list or lazy generator is shell scripts, working on streams of characters in parallel. It has annoying edge cases such as sometimes you have to use `stdbuf` to unbuffer a coproc, and another command following `head -n` may not be reliable because `head` may consume some more characters and could not put them back. But new general purpose languages tend to special-case string operations instead of making a version based on iterators as efficient.  
> **username_1**: I don't quite understand... I mean, they could always *theoretically* add a new feature that completely changes existing code. I don't see how that is related to undefined behavior, since you *can't* give a definition for behavior that only hypothetically exists in the future.  
> **username_0**: @DavidYoung If you can't give a definition yet, you can leave it undefined and say exactly it is undefined, to make it more permissive. But I think you are right. This question might be not as useful as I thought. But I'm leave it here, because saying a function would return a set of elements with unspecified computation order is an useful and understandable expression, and it's plausible that some languages would do that in some rare cases.  
---
## 1 answers
### Answer by username_3 on 2024-01-29. Score: 3
Python from your examples defines this order, but any lazy system produces the same result and other languages also provide it. .NET is an example of defining it for what are strictly higher-order operations, if that is the critical element.
First, note that this is really the order of a generator, not particularly about higher-order functions. Using a generator directly:
>>> k=0;print(list(regen(x) for x in (regen(x) for x in range(10))))
[2, 4, 6, 8, 10, 12, 14, 16, 18, 20]

produces the same order as your map example, and it's clear why it has to: each generator asks its source for the next value before producing its own. There isn't anywhere for a backlog of values to go, and no way to generate ahead of time, so this is the only possible ordering.
The list-comprehension version, which just swaps some parentheses for square brackets, necessarily produces the list object first — it's a single expression producing one value — so that the iterator of the list can be obtained.
map is, from Python 3, a generator, so it has the on-demand behaviour of a generator. This is necessary to allow mapping over infinite streams, for example (which was the purpose of making it into a generator):
>>> for v in map(lambda x,y: (x,y), 'abc', itertools.count())): print(v)
...
('a', 0)
('b', 1)
('c', 2)

While not explicitly defined as such for map because the translation is not simple when mapping over multiple functions, it is documented for its higher-order friend filter:

Note that filter(function, iterable) is equivalent to the generator expression (item for item in iterable if function(item)) if function is not None and (item for item in iterable if item) if function is None.

However, map is defined to stop when the shortest iterable does, so it does need to work one step at a time, which has essentially the same result.

This is the order you would expect for any lazy generator in any language, not specifically something with higher-order functions. This is also the order you get from C#'s LINQ operations, for example:
k = 0; Console.WriteLine(String.Join(",", Enumerable.Range(1,10).Select(regen).Select(regen)));
k = 0; Console.WriteLine(String.Join(",", from x in (from x in Enumerable.Range(1, 10) select regen(x)) select regen(x)));
k = 0; Console.WriteLine(String.Join(",", Enumerable.Select(Enumerable.Select(Enumerable.Range(1,10), regen), regen)));

2,4,6,8,10,12,14,16,18,20
2,4,6,8,10,12,14,16,18,20
2,4,6,8,10,12,14,16,18,20

In .NET, this arises from the implementation of Enumerable.Range and IEnumerable's Select extension method, which do explicitly guarantee deferred execution.

This ordering is a necessity of lazy evaluation, which is what generators are for, and those systems do specifically not consume more values than asked for. It's not really about higher-order functions, as the literal generator expression from Python shows.
---
