Pre-RFC: `fold_ok` is composable internal iteration

Itertools is actually bluss’ own project. :wink:

And Itertools::fold_while, which I added to rust-itertools a while back (for making an ML optimizer loop let mut-free), was the direct inspiration for fold_ok, afaik.

So as far as I understand bluss’ intentions for fold_ok are basically to promote/move fold_while into the stdlib, making the former obsolete (deprecated and removed even at some point?).

3 Likes

After some experiments, I think that the “new carrier (QuestionMark)” version of fold_ok does not work well in practice (for fallible operations): type inference fails too often. So it doesn’t just need the inject(x) -> Self function, I think it needs a real monad trait for good type inference.

Which is to say, it puts the horizon of generalization too far away, let’s try to base this on Result only.

This hasn’t moved for some reasons, for example christmas, but also that the following does not compile without additional type hints.

It’s more or less so that any nested use of try!() or ? will have this kind of issue.

Hence my quipping some late night that I wanted a try operator that didn’t convert errors, let’s say expr=? for example, that would have to be used inside fold_ok's closure here.

#![feature(fold_ok)]

use std::io::{BufRead, stdin, self};

fn try_main() -> Result<(), io::Error> {
    let s = stdin();
    let r = s.lock();
    let lines = r.lines().fold_ok(Vec::new(), |mut v, line| {
        v.push(line?);
        Ok(v)
    })?;
    println!("lines: {:?}", lines);
    Ok(())
}

fn main() {
    try_main().unwrap();
}

I hate suggesting things like this, but…

IIUC, the problem is that type inference hits what amounts to <io::Error as From>::<X>::from(From::<Y>::from(line)), and it can’t work out what X is. Could the language be extended so that you can mark the From trait such that when type inference sees this pattern, it just assumes that X = Y and moves on? Does the algorithm allow you to mark a type variable as "if all else fails, just assume Y"?

This is actually one of the major pain points with closures: propagating errors inside to outside via try!.

So I saw a talk at a conference that seems pretty relevant to this. The strymonas project is a “stream fusion” compiler in o’caml. It is able to eliminate a lot of the inefficiencies that would be involved in a naive implementation of Iterator. We are also able to do so, but they do more. =) It seems worth a look to see if any of the lessons they learn can be included into this proposal.

5 Likes

Someone asked a question about how to do this in one pass https://www.reddit.com/r/rust/comments/6jpbtl/how_do_i_make_this_code_efficient_and_idiomatic/

Do I understand correctly that under this proposal you can write this code with iterators in one pass?

Does Try fix any of the problems Carrier caused in this? Something like this:

fn try_fold<F, T: Try>(self, init: T::Ok, mut f: F) -> T where
    Self: Sized, F: FnMut(T::Ok, Self::Item) -> T,
{
    let mut accum = init;
    for x in self {
        accum = f(accum, x)?;
    }
    Try::from_ok(accum)
}

Since the closure constructs a concrete impl Try, the experiment I tried had the method inferring fine.

1 Like

Thinking more about this, it seems to me that instead of a traditional internal iterator, what’s really wanted here is the dual of a generator, i.e. some sort of “sink”.

With flexible enough generators, one could write yield to suspend and receive the next value when the generator is resumed.

The take example could look like this:

trait Iterator {
    fn sink_into<G, R>(&mut self, mut g: G) -> R
        where G: Generator<Option<Self::Item>, Yield=(), Return=R>
    {
        loop {
            match g.resume(self.next()) {
                Yield(()) => {},
                Return(x) => return x
            }
        }
    }

    fn try_fold<F, T: Try>(self, init: T::Ok, mut f: F) -> T
        where Self: Sized, F: FnMut(T::Ok, Self::Item) -> T,
    {
        let mut accum = init;
        self.sink_into(|| {
            while let Some(next) = yield {
                accum = f(accum, next)?;
            }
            Try::from_ok(accum)
        })
    }
}

struct Take<I> {
    n: usize,
    iter: I,
}

impl<I> Iterator for Take<I> where I: Iterator {
    fn sink_into<G, R>(&mut self, mut g: G) -> R
        where G: Generator<Option<Self::Item>, Yield=(), Return=R>
    {
        if self.n == 0 {
            return iter::empty().sink_into(g);
        }
        let n = &mut self.n;
        self.iter.sink_into(move || {
            *n -= 1;
            loop {
                match g.resume(yield) {
                    Yield(()) => {
                        if *n == 0 {
                            return iter::empty().sink_into(g);
                        }
                    }
                    Return(x) => return x
                }
            }
        })
    }
}

Moreover, I’m now wondering if generators could automatically be used to generate code like this, i.e. transform yield x to g.resume(x), alongside the next method, from the same source, i.e. you’d only write:

    fn take(self, mut n: usize) -> impl Iterator<Item=Self::Item> {
        if n == 0 {
            return;
        }
        for x in self {
            n -= 1;
            yield x;
            if n == 0 {
                break;
            }
        }
    }
2 Likes

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.

This topic was automatically closed 180 days after the last reply. New replies are no longer allowed.