Recursive lazy list

help
1

Referring to "Recursive" lazy list processing in Rust?

Specifically referring to this reply, I'm wondering if there are any crates which support this kind of pattern?

I was trying to implement this: The Fibonacci sequence - HaskellWiki

Sure enough, with a straightforward implementation I've got worse performance than naive recursion (lol): rust-exercises/main.rs at a8167358d29445abaaffd30a9bf0be5328674a23 · teohhanhui/rust-exercises · GitHub

2

Seems to be related:

3

The one thing that stands out to me in the code is the Box<dyn Iterator>. This will basically prevent Rust from optimizing this iterator efficiently. Normally Rust can run optimizations on iterators to the point that they turn into efficient loops. This code turns the iterator into a object on the heap be hide what you could think of as on opaque pointer that it can't optimize. This will force rust to go through a lot of indirection.

Further more, because these Iterators are boxed and recursive, you have to do A LOT of memory allocations, which are massively slow compared the actual math involved here.

To make this worse, on each call to next on this iterator is recursive.

To make this faster, you could remove the Box<dyn Iterator>. Here is an example:

fn fibonacci_iterator_without_recursion(n: u8) -> u128 {
    fn fib() -> impl Iterator<Item = u128> {
        let mut a = 0;
        let mut b = 1;
        iter::once(0 as u128).chain(iter::once(1 as u128)).chain(iter::repeat_with(move || {
            let v = a + b;
            a = b;
            b = v;
            v
        }))
    }

    fib().nth(usize::from(n)).unwrap()
}

Here is how I arrived at this solution:

  • Box<dyn Iterator> is inefficient and the compiler can't optimize it. Let's replace it with impl Iterator which will be a concrete type that the compiler can optimize. Also get ride of the Box.
  • Oh, wait. This is recursively calling itself. This means that it is a recursive datatype that rust can't handle without box.
  • Let me get rid of the recursion.
    I also tried Box<impl Iterator> without any other changes, which would have been a little more efficient, but this is also a recursive data type that Rust can't handle.

It looks like the only way to make this efficient is to get rid of the recursion.

From this example I would say that recursive iterators are inefficient. If you think about it, you could have a recursive function or a complex recursive data structure that lazily evaluates itself. The second is just so complex. If the compiler was smart enough to optimize this it would just create a recursive function.

I would say it is better to think of iterators as looping structures. Iterators can be efficient as lazy loops not as lazy recursion.

This was an interesting question and it made me think a lot. Thanks for asking it.

4

Sorry, I got carried away looking at your implementation that I forgot about the original question. Sorry, I don't know about any crates.

5

I already have an efficient implementation if you look here. I'm trying to find other elegant ways of implementing the same, and that's when I came across the entry on the Haskell wiki. But if you know of other cool ways of doing this, please do share (preferably without the code, as I'd like to take it as an exercise).

6

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