# 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:** 1

<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 5, 2023, 9:44pm UTC](https://discourse.julialang.org/t/on-the-behavior-of-reversed-iterators/102543/1 "2023-08-05T21:44:48Z")

</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/38):
>
> I thought that the thing with composability was that `reverse(filter(...))` would work _without_ there being any explicit such method.
> 
> So either this particular example is not a composability issue

in [https://github.com/JuliaLang/julia/blob/3e04129d61e19fe2957680b39e03b350db8e8c0d/base/iterators.jl#L530](https://github.com/JuliaLang/julia/blob/3e04129d61e19fe2957680b39e03b350db8e8c0d/base/iterators.jl#L530)

it is explicitly defined as

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

```

I don’t think this is correct, and I don’t think it can really be salvaged into something correct (without somehow inferring the side-effects of the filter?), so the method should be removed

> [@Did Julia community do something to improve its correctness?](https://discourse.julialang.org/t/did-julia-community-do-something-to-improve-its-correctness/102515/37):
>
> we do actually want to know in what language you can both
> 
> 1. do that easily  
> and
> 2. it correctly handles the distinction between a pure function and an impure function
> 
> Then we have a clear comparison to make, and maybe something to learn from

I’m not sure how this would be done, in _any_ language, easily and generically over both pure and impure functions

---

<div class="post-metadata">

**Author:** ![jar1](https://avatars.discourse-cdn.com/v4/letter/j/c0e974/32.png) [@jar1](https://discourse.julialang.org/u/jar1)\
**Post date:** [August 5, 2023, 9:49pm UTC](https://discourse.julialang.org/t/on-the-behavior-of-reversed-iterators/102543/2 "2023-08-05T21:49:30Z")

</div>

Maybe with [`Base.infer_effects`](https://aviatesk.github.io/posts/effects-analysis/index.html)

---

<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 5, 2023, 10:05pm UTC](https://discourse.julialang.org/t/on-the-behavior-of-reversed-iterators/102543/3 "2023-08-05T22:05:03Z")

</div>

But does that mean that no language allows that at all? That would contradict what @Sukera said. I would guess, with zero research, that a few do have it, and they have the same bug Julia has.

Maybe some compiled functional languages with great type systems and traits can both allow it and prevent the bug?

It would actually be good to know the answer to this.

---

<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 5, 2023, 10:10pm UTC](https://discourse.julialang.org/t/on-the-behavior-of-reversed-iterators/102543/4 "2023-08-05T22:10:08Z")

</div>

To me this goes beyond reversing a filter or zip or whatever, it’s whenever an iteration would be different backwards. The issue then comes down to this: do we want to reverse the result (impossible to do lazily) or the iteration (the way it is)? IMO I think it’s fine to have the latter as a feature (though I’d rather reverse first for clarity) and documenting that it’s not the same as the eager version, though I wouldn’t mind losing or being warned away from the feature.

I do have ideas on improving the code example in the github issue (shorter deterministic input `[1,3,2,5,4]`, calls involving the eager versions), but this particular issue should probably be split to a separate thread first. This is a good example that “correctness” can be more a matter of opinion, and it’s really not relevant to newcomers.

> [@Raf](#):
>
> I would guess, with zero research, that a few do have it, and they have the same bug Julia has.

Just checked Python’s builtin lazy `reversed`, `filter`, and `zip`, filter and zip objects are not implemented to be reversible and will throw an error saying so. Julia on the other hand implements `Iterators.reverse(::Filter)` and `Iterators.reverse(::Zip)`, though not with the eager `Base.reverse` (`Filter` and `Zip` being the lazy types, which eager evaluation doesn’t need).

---

<div class="post-metadata">

**Author:** ![jar1](https://avatars.discourse-cdn.com/v4/letter/j/c0e974/32.png) [@jar1](https://discourse.julialang.org/u/jar1)\
**Post date:** [August 5, 2023, 10:22pm UTC](https://discourse.julialang.org/t/on-the-behavior-of-reversed-iterators/102543/5 "2023-08-05T22:22:38Z")

</div>

> [@Benny](#):
>
> do we want to reverse the result (impossible to do lazily)

In the given case of zipped `UnitRange`s, it should be possible to reverse in O(1) time and space.

---

<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 5, 2023, 11:16pm UTC](https://discourse.julialang.org/t/on-the-behavior-of-reversed-iterators/102543/6 "2023-08-05T23:16:14Z")

</div>

Ok, let me start a list of other languages (to be extended):

| | `reverse(zip` | `reverse(filter(puref` | `reverse(filter(impuref` |
| --- | --- | --- | --- |
| Python\[1\] | no (error) | no (error) | no (error) |
| C++23\[2\] | yes | yes | no (segfault\[3\]) |
| Haskell | yes | yes | yes\[4\] |
| Clojure | yes | yes | yes |
| Rust\[5\] | yes | | |

* * *

1. Checked by @Benny 

2. `std::ranges::views::zip` requires C++23 

3. Compiles without warnings on g++ 

4. Code needs to be changed between pure `reverse . filter pred` and impure `fmap reverse . filterM pred` predicates. 

5. Checked by @jar1

---

<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 5, 2023, 11:21pm UTC](https://discourse.julialang.org/t/on-the-behavior-of-reversed-iterators/102543/7 "2023-08-05T23:21:35Z")

</div>

Segfaulting is a nice way to prevent silent bugs 😃

(Also looks like haskell may get the right answer in both cases? there’s my “compiled function language with a great type system” that gets it right)

---

<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 5, 2023, 11:35pm UTC](https://discourse.julialang.org/t/on-the-behavior-of-reversed-iterators/102543/8 "2023-08-05T23:35:13Z")

</div>

also, just want to note, no matter what the “correct” choice of `reverse(filter` should be, what’s _documented_ in Julia is simply not possible (and does not match the implementation). So even if the code is correct the docs will still need to change.

---

<div class="post-metadata">

**Author:** ![jar1](https://avatars.discourse-cdn.com/v4/letter/j/c0e974/32.png) [@jar1](https://discourse.julialang.org/u/jar1)\
**Post date:** [August 5, 2023, 11:37pm UTC](https://discourse.julialang.org/t/on-the-behavior-of-reversed-iterators/102543/9 "2023-08-05T23:37:54Z")

</div>

Rust looks good:

```julia
fn main() {
    let range1 = 0..2;
    let range2 = 0..10;

    let zipped = range1.zip(range2);
    let reversed: Vec<_> = zipped.rev().collect();

    println!("{:?}", reversed);
}

Output:
[(1, 1), (0, 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 5, 2023, 11:40pm UTC](https://discourse.julialang.org/t/on-the-behavior-of-reversed-iterators/102543/10 "2023-08-05T23:40:21Z")

</div>

Good, added to the table. What about filter?

---

<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 5, 2023, 11:42pm UTC](https://discourse.julialang.org/t/on-the-behavior-of-reversed-iterators/102543/11 "2023-08-05T23:42:09Z")

</div>

Yes, Haskell looks good. The type system also distinguishes between pure and impure functions, i.e., implemented via its famous monads.

---

<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 5, 2023, 11:47pm UTC](https://discourse.julialang.org/t/on-the-behavior-of-reversed-iterators/102543/12 "2023-08-05T23:47:54Z")

</div>

What about clojure? is it the right answer or just letting you hit the bug?

---

<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 5, 2023, 11:49pm UTC](https://discourse.julialang.org/t/on-the-behavior-of-reversed-iterators/102543/13 "2023-08-05T23:49:09Z")

</div>

Clojure gives the right answers as far as my tiny test shows.

---

<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, 12:01am UTC](https://discourse.julialang.org/t/on-the-behavior-of-reversed-iterators/102543/14 "2023-08-06T00:01:32Z")

</div>

F# also works:

### reverse(zip…

```julia-auto
let r1 = seq{0..1}
let r2 = seq{0..10}

let zipped = Seq.zip r1 r2
let reversed = Seq.rev zipped |> Seq.toList

printfn "output: %A" reversed
// output: [(1, 1); (0, 0)]

```

### reverse(filter(puref…

```julia-auto
let mySeq = seq{0..10}
let filtered = mySeq |> Seq.filter (fun x -> x % 2 = 0)

let revFiltered = Seq.rev filtered |> Seq.toList

printfn "%A" revFiltered
// output: [10; 8; 6; 4; 2; 0]

```

### reverse(filter(impuref…

```julia-auto
type RollingMax = { mutable m: float }

let fmut (rm: RollingMax) =
    fun x ->
        //printfn "x: %A" x

        match rm.m, x with
        | m, x when x > m ->
            rm.m <- x
            true
        | _ -> false

let rand = System.Random()
let mys = [for _ in 1..10 -> rand.NextDouble()]

let mySeq = seq mys
let filtered = mySeq |> Seq.filter (fmut { m = 0.0 })

printfn "filtered impure: %A" (filtered |> Seq.toList)
// filtered impure: [0.6818975786; 0.9381464454; 0.9763493644]

let reversed = mySeq |> Seq.filter (fmut { m = 0.0 }) |> Seq.rev |> Seq.toList

printfn "filtered rev impure: %A" reversed
//filtered rev impure: [0.9763493644; 0.9381464454; 0.6818975786]

```

---

<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, 12:20am UTC](https://discourse.julialang.org/t/on-the-behavior-of-reversed-iterators/102543/15 "2023-08-06T00:20:19Z")

</div>

Julia `zip` is looking pretty bad…

But julia has the same anwser for `filter`. will F# hit the same bug as julia if your functor has mutable states like the issue?

> <https://github.com/JuliaLang/julia/issues/50440>
>
> From docstring of \`reverse\` 
> \> \`reverse(itr)\` is an iterator over the
> same col…lection but in the reverse order.
> 
> yet consider
> \`\`\`
> julia\> mutable struct RollingMax
> m
> end
> 
> julia\> function (rm::RollingMax)(x)
> if x \> rm.m
> rm.m = x
> return true
> else
> return false
> end
> end
> 
> julia\> arr = rand(10);
> 
> julia\> Iterators.filter(RollingMax(0), arr) |\> collect
> 5-element Vector{Float64}:
> 0.20543016348395104
> 0.40777744342276
> 0.6118207748963927
> 0.6765659450947831
> 0.8719846507332757
> 
> julia\> Iterators.filter(RollingMax(0), arr) |\> Iterators.reverse |\> collect
> 2-element Vector{Float64}:
> 0.839252025474182
> 0.8719846507332757
> \`\`\`
> 
> personally I think \`reverse(f::Filter)\` should just be removed; it cannot be implemented correctly without knowing the purity of the predicate. another option is to add a warning in the docs? or maybe a third option is to somehow dispatch \`reverse\` only when \`flt\` can be proven pure---not sure how this is technically possible though.

---

<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, 12:47am UTC](https://discourse.julialang.org/t/on-the-behavior-of-reversed-iterators/102543/16 "2023-08-06T00:47:54Z")

</div>

I will (slightly) eat my words a bit, as Rust can be wrangled into similarly bad behavior

```julia
use std::cell::RefCell;

struct RollingMax {
    max_value: RefCell<Option<i32>>,
}

impl RollingMax {
    fn new() -> RollingMax {
        RollingMax { max_value: RefCell::new(None) }
    }

    fn call(&self, x: i32) -> bool {
        let mut max_value_borrowed = self.max_value.borrow_mut();
        match *max_value_borrowed {
            None => {
                *max_value_borrowed = Some(x);
                true
            },
            Some(y) => {
                if x > y {
                    *max_value_borrowed = Some(x);
                    true
                } else {
                    false
                }
            }
        }
    }
}

fn main() {
    let v = vec![1,2,3,4,5];
    let rolling_max = RollingMax::new();
    
    let iter = v.into_iter().filter(move |&x| rolling_max.call(x));

    for num in iter.rev() {
        println!("{}", num);
    }
    // prints 5
}

```

But I believe this is pretty unidiomatic… I think it’s considered “cleaner” to create a new iterator type, upon which if you want to call `.rev()` you have to explicitly implement the `DoubleEndedIterator` trait. Also, I think the verbosity of this implementation kind of mitigates the badness since it should be clear there is mischief afoot.

---

<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, 12:59am UTC](https://discourse.julialang.org/t/on-the-behavior-of-reversed-iterators/102543/17 "2023-08-06T00:59:59Z")

</div>

> [@Raf](#):
>
> will F# hit the same bug as julia if your functor has mutable states like the issue?

Nope, see the [update](https://discourse.julialang.org/t/did-julia-community-do-something-to-improve-its-correctness/102515/53).

---

<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:03am UTC](https://discourse.julialang.org/t/on-the-behavior-of-reversed-iterators/102543/18 "2023-08-06T01:03:33Z")

</div>

Thanks for posting that, feels like we are getting to a more accurate assessment of how bad these problems are. `zip` is clearly bad, but filter reverse has problems in lots of places.

We could also argue the code in your issue is pretty wrangled julia, passing a mutable functor to `Iterators.filter` isn’t at all an idomatic thing to do in Julia.

@algunion interesting. But is `Seq.rev` actually lazy? `Base.reverse` will also give you the right anser in julia - the lazy `Iterators.reverse` method is the problem.

I’m trying to understand how it could be lazy for the pure function and not for the impure function - clearly haskel can handle that with monads, but how does F# ?

(From the F# docs `Seq.rev` appears not to be lazy - it consumes the whole sequence and reverses it)

---

<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:30am UTC](https://discourse.julialang.org/t/on-the-behavior-of-reversed-iterators/102543/19 "2023-08-06T01:30:12Z")

</div>

Can’t really say for all the languages mentioned so far without code examples to look up, but so far it looks like only reversed zipped unit-ranges are being looked at, and as jar1 pointed out earlier, those could be lazily reversed the same way it’s eagerly reversed. But the Julia methods we’re looking at are applied to all iterables, and it’s probably more important to ask what those other languages do then.

> [@Raf](#):
>
> `Base.reverse` will also give you the right anser in julia - the lazy `Iterators.reverse` method is the problem.

What do you mean, it’s not implemented for `Zip` and `Filter`.

---

<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, 1:31am UTC](https://discourse.julialang.org/t/on-the-behavior-of-reversed-iterators/102543/20 "2023-08-06T01:31:00Z")

</div>

> [@Benny](#):
>
> What do you mean, it’s not implemented for `Zip` and `Filter`.

yes it is [https://github.com/JuliaLang/julia/blob/3e04129d61e19fe2957680b39e03b350db8e8c0d/base/iterators.jl#L530](https://github.com/JuliaLang/julia/blob/3e04129d61e19fe2957680b39e03b350db8e8c0d/base/iterators.jl#L530)

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