it is explicitly defined as
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
I’m not sure how this would be done, in any language, easily and generically over both pure and impure functions
Maybe with Base.infer_effects
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.
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.
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).
In the given case of zipped UnitRanges, it should be possible to reverse in O(1) time and space.
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 |
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)
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.
Rust looks good:
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)]
Good, added to the table. What about filter?
Yes, Haskell looks good. The type system also distinguishes between pure and impure functions, i.e., implemented via its famous monads.
What about clojure? is it the right answer or just letting you hit the bug?
Clojure gives the right answers as far as my tiny test shows.
F# also works:
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)]
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]
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]
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?
I will (slightly) eat my words a bit, as Rust can be wrangled into similarly bad behavior
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.
Nope, see the update.
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)
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.
What do you mean, it’s not implemented for Zip and Filter.