[rust-dev] Iterators, lists, vectors

Graydon Hoare graydon at mozilla.com
Thu Jan 12 09:47:30 PST 2012


On 12/01/2012 7:30 AM, Rust wrote:

> i wonder how we will "replicate" Haskell's lazy lists.

I'm not in any hurry to do so. They're nice and composable, but they're 
an efficiency nightmare.

> For example: `str::split` splits a string and returns a list/vector of
> sub-strings.
>
> But maybe we don't want to duplicate those sub-strings in memory and we
> don't want to create such an intermediate list/vector
>
> if we just plan to iterate over it.
>
> We could add a `str::split_iter` which calls a block instead.
>
> But then we'd need to duplicate every function: one returning a
> list/vector, and the other taking a block.
>
> => interface explosion

Maybe for a few of the most-common APIs you get some duplication, yes.

More generally though, I think block-centric is best, and perhaps 
provide a standard vec method that appends-to-a-vec everything fed to 
it. Then use that (or hand-code a block):

   vec x = [];
   hashtbl.keys(bind x.append)      // with a helper
   hashtbl.keys() { |k| x += k; }   // manually

A lot of our existing APIs aren't block-centric because we wrote them 
before we had blocks. I mean, the one generalizes to the other pretty 
easily anyways.

Block-centric style is effectively having the programmer manually 
perform loop fusion or deforestation. I realize "human compiler" tasks 
like this are distasteful to people who want infinitely smart compilers, 
but IME a lot of things "smart" compilers advertise, they hit 
confounding requirements over, and have to de-optimize from their best 
case. For us, we can be sure that:

   hashtbl.keys() { |k|
       k.elts() { |e|
           if (e > x) { foo(e); }
       }
   }

will not allocate. That's actually pretty great, and I think we've 
boiled the syntax down to a level where it's no less readable than the 
vec-centric style:

    let ks = hashtbl.keys();
    for k in ks {
        let es = e.elts();
        for e in es {
             if (e > x) { foo(e); }
        }
    }

This style is actually longer, so ... I'm not terribly put off 
suggesting APIs follow the former style by preference.

> Am i missing something (e.g. that strings are immutable and the list of
> strings are just "pointers" to the orignal string)?

No. Though we'll be doing some optimizations around constants like that 
eventually. A dynamically constructed string is certainly not a constant!

> Do we need lazy sequences?

Please no.

> Any other idea?

I'm fine with a block-centric style.

-Graydon


More information about the Rust-dev mailing list