Specifying a restricted lifetime


#1

Hi,

Thanks for building this great community and keeping it alive, and sorry if I’m duplicating an existing question!

So I’m trying to do some functional programming in Rust and I thought I’d use chained iterators instead of creating new vectors that are copies of the old vectors with just a single value added. I thought it’d be easy - pass an iterator as the “accumulator” parameter to a function, let the function create a iter::once() with the new value, chain the two and pass the result to the next iteration. Yeah, well, it turns out that I still don’t understand lifetimes in Rust very well :slight_smile: (no big surprise there)

So for a simple demonstration of what I’m trying to do, here’s some working code without iterators:

https://is.gd/Lmipvz

And here’s what I’m actually trying to do::

https://is.gd/ESZHCv

The compiler complains that “digit” doesn’t live long enough, and I kind of understand its reasoning: obviously, “digit” is only valid until the function ends, but the 'a lifetime for the passed-in iterator is waaay longer. However, I do not want to use the 'a lifetime; how do I tell the compiler that the iter::once(&digit).chain(acc) iterator should be considered to have the same lifetime as digit, and not the same lifetime as the passed-in acc?

Or am I misunderstanding something, and is there a way that chaining two iterators could somehow leave a trace beyond the lifetime of the chain itself? I really don’t think it should matter - I’m only passing the buit-up chain to another instance of the convert() function, so I ought to be able to tell it to use the shorter lifetime of digit for the recursive invocation of convert()… shouldn’t I?

I tried playing around with HRTB a bit (both for and 'b: 'a), but I can’t seem to hit on the correct syntax. Help? :slight_smile:

G’luck,
Peter


#2

Ah, that’s a bit complicated… First of all, char is a small copy type, so there’s no reason to use &char, just use char instead.

However, even with this change the code won’t compile because of how generics work in Rust. Rust uses monomorphisation, which means that there is a separate instance of generic function for each type parameter used in the program.

And types of xs and xs.chain(ys) differ: they both implement Iterator, but if xs is X and ys is Y, then xs.chain(ys) is Chain<X, Y>. So, this recursive call convert(number / base, base, iter::once(digit).chain(acc)) will cause compiler to generate infinite number of monomorphizations of convert, which it can’t do.


#3

Thanks a lot for the explanation! Indeed, it makes sense now. Well, of course, I’d still like an answer for the more general case when the type is a data structure and not a simple char, but let me tackle this one for now.

I guess creating my own iterator type would do the trick, right? sigh let me try that and get back to you… and thanks again!

G’luck,
Peter


#4

To solve the particular problem at hand you can use dynamic dispatch and pass &Iterator to convert.

But would say that in general one rarely uses recursion to process sequential data in Rust: it’s not as pleasant in Rust as in more functional languages, and there’s no guaranteed tall call optimization. For this function, a loop collecting digits into a fixed sized buffer on the stack would be more idiomatic.

I think a more fun and natural way of combining functional programming and Rust would be implementing persistent data structures, like xi-rope does: https://docs.rs/xi-rope/0.1.0/xi_rope/struct.Rope.html