# On the behavior of reversed iterators

**URL:** <https://discourse.julialang.org/t/on-the-behavior-of-reversed-iterators/102543>\
**Category:** General Usage\
**Created:** [August 5, 2023, 9:44pm UTC](https://discourse.julialang.org/t/on-the-behavior-of-reversed-iterators/102543 "2023-08-05T21:44:48Z")\
**Posts on this page:** 20\
**Page:** 2

<div class="post-metadata">

**Author:** ![Benny](https://avatars.discourse-cdn.com/v4/letter/b/49beb7/32.png) [@Benny](https://discourse.julialang.org/u/Benny)\
**Post date:** [August 6, 2023, 1:31am UTC](https://discourse.julialang.org/t/on-the-behavior-of-reversed-iterators/102543/21 "2023-08-06T01:31:35Z")

</div>

That’s `Iterators.reverse`, I was talking about `Base.reverse`.

---

<div class="post-metadata">

**Author:** ![Raf](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/raf/32/3383_2.png) [@Raf](https://discourse.julialang.org/u/Raf)\
**Post date:** [August 6, 2023, 1:32am UTC](https://discourse.julialang.org/t/on-the-behavior-of-reversed-iterators/102543/22 "2023-08-06T01:32:27Z")

</div>

But `Base.reverse` works by default as it collects the iterator? Thats also what `Seq.rev` does in F#

---

<div class="post-metadata">

**Author:** ![Benny](https://avatars.discourse-cdn.com/v4/letter/b/49beb7/32.png) [@Benny](https://discourse.julialang.org/u/Benny)\
**Post date:** [August 6, 2023, 1:33am UTC](https://discourse.julialang.org/t/on-the-behavior-of-reversed-iterators/102543/23 "2023-08-06T01:33:50Z")

</div>

I’m not sure if it’s because I haven’t updated as much as possible, but this is what happens when I attempt it:

```julia
julia> Base.reverse(zip(1:10, 1:2))
ERROR: MethodError: no method matching reverse(::Base.Iterators.Zip{Tuple{UnitRange{Int64}, UnitRange{Int64}}})

```

---

<div class="post-metadata">

**Author:** ![Raf](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/raf/32/3383_2.png) [@Raf](https://discourse.julialang.org/u/Raf)\
**Post date:** [August 6, 2023, 1:36am UTC](https://discourse.julialang.org/t/on-the-behavior-of-reversed-iterators/102543/24 "2023-08-06T01:36:02Z")

</div>

Ahh youre right its not you have to call `collect` - but it doesn’t really change my point on F#, its just doing that automatically for you.

---

<div class="post-metadata">

**Author:** ![algunion](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/algunion/32/51630_2.png) [@algunion](https://discourse.julialang.org/u/algunion)\
**Post date:** [August 6, 2023, 1:36am UTC](https://discourse.julialang.org/t/on-the-behavior-of-reversed-iterators/102543/25 "2023-08-06T01:36:36Z")

</div>

> [@Raf](#):
>
> (From the F# docs `Seq.rev` appears not to be lazy - it consumes the whole sequence and reverses it)

It is lazy in the sense that the statement `Seq.rev mySeq` will not be evaluated until you actually start consuming elements from the reversed sequence.

Imagine the following:

```julia
let rand = System.Random()
let someSeq = 
    seq { 
            for i in 1 .. rand.Next(5, 10) do 
                if i % 2 = 0 
                then yield i + 1
                else
                    yield i + 1; 
                    yield i + 2 }

someSeq |> Seq.rev |> Seq.take 1

```

At least to me, it seems that the nature of sequences demands this kind of consumption.

Also, although an F# antipattern, you could generate a sequence using a mutable object (which does not support lazy evaluation) - so the only way to ensure correctness would be to actually evaluate all seq elements before even being able to know the last one (this is kinda similar with the actual snippet I posted).

However, I am really curious about Haskell implementation (because a similar approach can be used in F# to ensure the same result).

Are those snippets posted somewhere?

---

<div class="post-metadata">

**Author:** ![Raf](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/raf/32/3383_2.png) [@Raf](https://discourse.julialang.org/u/Raf)\
**Post date:** [August 6, 2023, 1:43am UTC](https://discourse.julialang.org/t/on-the-behavior-of-reversed-iterators/102543/26 "2023-08-06T01:43:31Z")

</div>

`Iterators.reverse` in julia is actually for iterators that _can_ be reversed lazily, like a range or vector - they are not collected, they are just iterated in reverse.

> <https://github.com/JuliaLang/julia/blob/3e04129d61e19fe2957680b39e03b350db8e8c0d/base/iterators.jl#L93-L108>

> Also, although an F# antipattern, you could generate a sequence using a mutable object (which does not support lazy evaluation) - so the only way to ensure correctness would be to actually evaluate all seq elements before even being able to know the last one.

This sounds similar to whats happening in the juila bug in question.

---

<div class="post-metadata">

**Author:** ![Benny](https://avatars.discourse-cdn.com/v4/letter/b/49beb7/32.png) [@Benny](https://discourse.julialang.org/u/Benny)\
**Post date:** [August 6, 2023, 2:29am UTC](https://discourse.julialang.org/t/on-the-behavior-of-reversed-iterators/102543/27 "2023-08-06T02:29:25Z")

</div>

> [@Raf](#):
>
> `Iterators.reverse` in julia is actually for iterators that _can_ be reversed lazily, like a range or vector - they are not collected, they are just iterated in reverse.

The disagreement is precisely on what is lazily reversible according to `Iterators.reverse`. Some types like ranges just do eager reversals because it’s cheap, so we don’t have to worry about those. The fallback Reverse iteration ~~looks sensible, it~~ uses `getindex` over a `reverse`ible `eachindex`, which could be a problem if `getindex` is impure, e.g. depends on how many times it was called. The following methods iterate backwards from the ends, which can be different from forwards iteration:

```julia
reverse(G::Generator) = Generator(G.f, reverse(G.iter))
reverse(z::Zip) = Zip(Base.map(reverse, z.is)) # n.b. we assume all iterators are the same length
reverse(f::Filter) = Filter(f.flt, reverse(f.itr))
reverse(it::Cycle) = Cycle(reverse(it.xs))
reverse(p::ProductIterator) = ProductIterator(Base.map(reverse, p.iterators))
reverse(f::Flatten) = Flatten(reverse(itr) for itr in reverse(f.it))

```

Besides the comment assuming `zip`’s iterators are all the same length, it seems like a deliberate deviation from the eager versions. Taking the `RollingMax(0)` example from the issue, the eager `filter` and `reverse` do not commute, but the lazy versions were defined so. All the possible combinations here:

```julia
julia> Iterators.filter(RollingMax(0), Iterators.reverse([1,3,2,5,4])) |> collect
2-element Vector{Int64}:
 4
 5

julia> Iterators.filter(RollingMax(0), reverse([1,3,2,5,4])) |> collect
2-element Vector{Int64}:
 4
 5

julia> filter(RollingMax(0), reverse([1,3,2,5,4]))
2-element Vector{Int64}:
 4
 5

julia> Iterators.reverse(Iterators.filter(RollingMax(0), [1,3,2,5,4])) |> collect
2-element Vector{Int64}:
 4
 5

julia> Iterators.reverse(filter(RollingMax(0), [1,3,2,5,4])) |> collect
3-element Vector{Int64}:
 5
 3
 1

julia> reverse(filter(RollingMax(0), [1,3,2,5,4]))
3-element Vector{Int64}:
 5
 3
 1

```

---

<div class="post-metadata">

**Author:** ![algunion](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/algunion/32/51630_2.png) [@algunion](https://discourse.julialang.org/u/algunion)\
**Post date:** [August 6, 2023, 2:42am UTC](https://discourse.julialang.org/t/on-the-behavior-of-reversed-iterators/102543/28 "2023-08-06T02:42:11Z")

</div>

> [@Raf](#):
>
> This sounds similar to whats happening in the juila bug in question.

Yes, but it is worth mentioning that F# does not allow this kind of bug: `Seq.rev` is lazy in the sense that it only consumes the complete input sequence when you attempt to consume elements from the reversed sequence (otherwise digesting is not taking place).

My understanding is this is motivated by the versatile ways in which you can create `Seq`s in F#.

Also, I think we are kinda comparing apples to oranges here: F# `Seq` associated functions are not merely iterators over collections (`Seq.rev` included). This opens a whole new chapter that is not really relevant to the discussed subject.

A reversed lazy iterator will produce the same issue for F# as the one we observe in Julia: however, if one is aware that the impure filter function is dependent on the evaluation order (which is by default an F# antipattern), the implementation would be done using [`continuation passing style`](https://fsharpforfunandprofit.com/posts/computation-expressions-continuations/#continuation-passing-style) (if we are to be loyal to functional programming approach) - and the bug would be averted.

It seems to me that the bug obtained in Julia is only possible in F# (and likely Haskell) if one is actually trying to produce the bug in the first place. Otherwise, being aware of what you want to achieve (and especially the impure function), the correctness issue would never occur.

---

<div class="post-metadata">

**Author:** ![bertschi](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/bertschi/32/33462_2.png) [@bertschi](https://discourse.julialang.org/u/bertschi)\
**Post date:** [August 6, 2023, 8:29am UTC](https://discourse.julialang.org/t/on-the-behavior-of-reversed-iterators/102543/29 "2023-08-06T08:29:10Z")

</div>

For the record, here are the code snippets I had used for my table:

C++23

```plaintext
#include <ranges>
#include <iostream>
#include <vector>

int main() {
  auto even = [](int i) { return 0 == i % 2; };
  int m = 0;
  auto rollmax = [&m](int i) {
    if (i > m) {
      m = i;
      return true;
    } else {
      return false;
    }
  };
  std::vector<int> v = {1,3,2,5,4};
  auto u = std::views::iota(1, 10);

  for (auto e : std::views::zip(u, v)
	 | std::views::reverse)
    std::cout << '(' << std::get<0>(e) << ',' << std::get<1>(e) << ')' << ' ';
  std::cout << '\n';

  for (float x : std::views::filter(v, even)
	 | std::views::reverse)
    std::cout << x << ' ';
  std::cout << '\n';

  // The following segfaults on g++ -std=c++2b
  for (float x : std::views::filter(v, rollmax)
	 | std::views::reverse)
    std::cout << x << ' ';
  std::cout << '\n';  
}

```

Clojure

```plaintext
(def v [1 3 2 5 4])
(def u (range 1 10))

(def zip (partial map vector))
  
(println (reverse (zip u v)))
(println (reverse (filter even? v)))

(defn rollmax [s]
  (let [m (atom s)]
    (fn [i]
      (if (> i @m)
        (do (reset! m i)
            true)
        false))))

(println (reverse (filter (rollmax 0) v)))

```

Haskell

```haskell
import Control.Monad as CM
import Control.Monad.State as CMS

v = [1,3,2,5,4]
u = [1..9]

rollmax i =
  CMS.get >>= \m ->
  if i > m
  then CMS.put i >>
       return True
  else return False

main = do
  putStrLn $ show $ reverse $ zip u v
  putStrLn $ show $ reverse $ filter even v
  putStrLn $ show $ runState (fmap reverse $ CM.filterM rollmax v) 0

```

---

<div class="post-metadata">

**Author:** ![bertschi](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/bertschi/32/33462_2.png) [@bertschi](https://discourse.julialang.org/u/bertschi)\
**Post date:** [August 6, 2023, 8:34am UTC](https://discourse.julialang.org/t/on-the-behavior-of-reversed-iterators/102543/30 "2023-08-06T08:34:45Z")

</div>

> [@algunion](#):
>
> A reversed lazy iterator will produce the same issue for F# as the one we observe in Julia: however, if one is aware that the impure filter function is dependent on the evaluation order (which is by default an F# antipattern), the implementation would be done using [`continuation passing style`](https://fsharpforfunandprofit.com/posts/computation-expressions-continuations/#continuation-passing-style) (if we are to be loyal to functional programming approach) - and the bug would be averted.
> 
> It seems to me that the bug obtained in Julia is only possible in F# (and likely Haskell) if one is actually trying to produce the bug in the first place. Otherwise, being aware of what you want to achieve (and especially the impure function), the correctness issue would never occur.

Yes, Haskell essentially forces you to write impure functions in continuation-passing style – with the `do`-notation providing a bit of syntactic sugar. The type system also tracks where this is needed and usually you have to adapt the program when including impure parts, e.g., use `filterM` (which is designed to sequentially chain side-effects) instead of `filter` (which requires pure predicates).  
Due to this, I don’t think it would actually be possible to create that bug in Haskell – even if trying to.

---

<div class="post-metadata">

**Author:** ![Benny](https://avatars.discourse-cdn.com/v4/letter/b/49beb7/32.png) [@Benny](https://discourse.julialang.org/u/Benny)\
**Post date:** [August 6, 2023, 10:03am UTC](https://discourse.julialang.org/t/on-the-behavior-of-reversed-iterators/102543/31 "2023-08-06T10:03:55Z")

</div>

> [@Did Julia community do something to improve its correctness?](https://discourse.julialang.org/t/did-julia-community-do-something-to-improve-its-correctness/102515/64):
>
> > [@Raf](#):
> >
> > (From the F# docs `Seq.rev` appears not to be lazy - it consumes the whole sequence and reverses it)
> 
> It is lazy in the sense that the statement `Seq.rev mySeq` will not be evaluated until you actually start consuming elements from the reversed sequence.

I’m not sure what consume means here but if that means the reversed sequence collects the input sequence and iterates backwards, then the element allocation makes it incomparable to the reversal of iterators here, where only explicit `collect`s can allocate all the elements.

---

<div class="post-metadata">

**Author:** ![bertschi](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/bertschi/32/33462_2.png) [@bertschi](https://discourse.julialang.org/u/bertschi)\
**Post date:** [August 6, 2023, 12:15pm UTC](https://discourse.julialang.org/t/on-the-behavior-of-reversed-iterators/102543/32 "2023-08-06T12:15:12Z")

</div>

Just checked that also Clojure’s `reverse` is not lazy, i.e., collect all elements.  
On the other hand, a lazy reverse would only be of interest if you don’t want to realize any elements. As soon as you request a single element from the reverse iterator, all elements of the original need to be traversed and potentially stored somewhere – using iterator state boils down to building something like a linked list and will probably be less efficient than simply collecting the elements right away.  
Am I missing anything here?

---

<div class="post-metadata">

**Author:** ![bertschi](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/bertschi/32/33462_2.png) [@bertschi](https://discourse.julialang.org/u/bertschi)\
**Post date:** [August 6, 2023, 12:52pm UTC](https://discourse.julialang.org/t/on-the-behavior-of-reversed-iterators/102543/33 "2023-08-06T12:52:33Z")

</div>

From the source code of Julia 1.9.1 is appears that certain algebraic laws are expected to hold for reversed iterators:

```julia
reverse(f::Filter) = Filter(f.flt, reverse(f.itr))

```

I.e., this assumes the law (in Haskell notation): `reverse . filter f == filter f . reverse` which does hold for pure functions, but breaks otherwise.

```julia
reverse(z::Zip) = Zip(Base.map(reverse, z.is)) # n.b. we assume all iterators are the same length

```

I.e. assumes that `reverse . uncurry zip == uncurry zip . fmap reverse` which only holds if all argument iterators have the same length. This should not be implicitly assumed – especially if not documented except in this comment – but rather checked, i.e., using `broadcast` instead of `map` which requires same length arguments (formally interpreting scalars as infinite sequences which is the correct behavior according to the [applicative instance of `ZipList`](https://hackage.haskell.org/package/base-4.18.0.0/docs/Control-Applicative.html#t:ZipList) in Haskell).

---

<div class="post-metadata">

**Author:** ![Sukera](https://avatars.discourse-cdn.com/v4/letter/s/ce7236/32.png) [@Sukera](https://discourse.julialang.org/u/Sukera)\
**Post date:** [August 6, 2023, 2:43pm UTC](https://discourse.julialang.org/t/on-the-behavior-of-reversed-iterators/102543/34 "2023-08-06T14:43:30Z")

</div>

> [@bertschi](#):
>
> this assumes the law (in Haskell notation): `reverse . filter f == filter f . reverse` which does hold for pure functions, but breaks otherwise.

There is another hidden assumption: that the iterator itself is not stateful & actually reversible. In the general case, you can’t get around collecting the entire iterator, no matter whether the filtering function itself is free of sideeffects or not.

Unfortunately, this kind of thing happens often (though I don’t think other languages are better at this either):

- [Reported length of zip of stateful iterators wrong · Issue #47790 · JuliaLang/julia · GitHub](https://github.com/JuliaLang/julia/issues/47790)
- [Introduce iterator trait: IsStateful · Issue #43388 · JuliaLang/julia · GitHub](https://github.com/JuliaLang/julia/issues/43388)

---

<div class="post-metadata">

**Author:** ![algunion](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/algunion/32/51630_2.png) [@algunion](https://discourse.julialang.org/u/algunion)\
**Post date:** [August 6, 2023, 6:45pm UTC](https://discourse.julialang.org/t/on-the-behavior-of-reversed-iterators/102543/35 "2023-08-06T18:45:51Z")

</div>

> [@Benny](#):
>
> I’m not sure what consume means here, but if that means the reversed sequence collects the input sequence and iterates backwards, then the element allocation makes it incomparable to the reversal of iterators here, where only explicit `collect`s can allocate all the elements.

It is correct to say that in F# `collect` takes place, and the reverse function is actually returning elements after the filter function was called in the order dictated by the original order of elements.

```julia
let sq = 
    seq { for i in 1 .. 10 do 
                    printfn "i: %A" i
                    yield i }

let revsq = sq |> Seq.rev

// no evaluation/allocation above this point

// but this will trigger the complete allocation 
// of `sq` before applying `Seq.rev` and returning the first
// element of reversed sequence
revsq |> Seq.take 1

```

---

<div class="post-metadata">

**Author:** ![Raf](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/raf/32/3383_2.png) [@Raf](https://discourse.julialang.org/u/Raf)\
**Post date:** [August 6, 2023, 6:47pm UTC](https://discourse.julialang.org/t/on-the-behavior-of-reversed-iterators/102543/36 "2023-08-06T18:47:37Z")

</div>

So it looks like most other languages dont let you lazily reverse filtered iterators.

- Haskel does it properly because monads intrinsically separate mutating and pure functions
- C++ lets you and segfaults for mutating functions
- julia works for the pure function case and gives the wrong answer for mutating functions
- Edit: and Rust does what Julia does, allowing the same bug

@Sukera its actually a thing to rely on zip not being in order… which would break this use case anyway [Reported length of zip of stateful iterators wrong · Issue #47790 · JuliaLang/julia · GitHub](https://github.com/JuliaLang/julia/issues/47790)

---

<div class="post-metadata">

**Author:** ![algunion](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/algunion/32/51630_2.png) [@algunion](https://discourse.julialang.org/u/algunion)\
**Post date:** [August 6, 2023, 6:49pm UTC](https://discourse.julialang.org/t/on-the-behavior-of-reversed-iterators/102543/37 "2023-08-06T18:49:56Z")

</div>

All developers writing impure filter functions deserve to be punished: Julia is ensuring the punishment fits the crime 🙂

---

<div class="post-metadata">

**Author:** ![adienes](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/adienes/32/37459_2.png) [@adienes](https://discourse.julialang.org/u/adienes)\
**Post date:** [August 6, 2023, 6:55pm UTC](https://discourse.julialang.org/t/on-the-behavior-of-reversed-iterators/102543/38 "2023-08-06T18:55:04Z")

</div>

> [@Raf](#):
>
> its actually a thing to rely on zip not being in order

wait, what?

it should iterate through its constituent iterators in order until one of them halts, right?

---

<div class="post-metadata">

**Author:** ![Raf](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/raf/32/3383_2.png) [@Raf](https://discourse.julialang.org/u/Raf)\
**Post date:** [August 6, 2023, 7:13pm UTC](https://discourse.julialang.org/t/on-the-behavior-of-reversed-iterators/102543/39 "2023-08-06T19:13:30Z")

</div>

But you can iterate the last iterator before the first one… it doesn’t say anywhere that they happen in argument order.

---

<div class="post-metadata">

**Author:** ![adienes](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/adienes/32/37459_2.png) [@adienes](https://discourse.julialang.org/u/adienes)\
**Post date:** [August 6, 2023, 7:14pm UTC](https://discourse.julialang.org/t/on-the-behavior-of-reversed-iterators/102543/40 "2023-08-06T19:14:28Z")

</div>

ahh, ok. that makes sense given that argument order evaluation isn’t guaranteed in any context afaik

[Previous page](https://discourse.julialang.org/t/on-the-behavior-of-reversed-iterators/102543.md?page=1)

[Next page](https://discourse.julialang.org/t/on-the-behavior-of-reversed-iterators/102543.md?page=3)