src/doc/trpl/iterators.md

   1 % Iterators
   2
   3 Let's talk about loops.
   4
   5 Remember Rust's `for` loop? Here's an example:
   6
   7 ```rust
   8 for x in 0..10 {
   9     println!("{}", x);
  10 }
  11 ```
  12
  13 Now that you know more Rust, we can talk in detail about how this works.
  14 Ranges (the `0..10`) are 'iterators'. An iterator is something that we can
  15 call the `.next()` method on repeatedly, and it gives us a sequence of things.
  16
  17 Like this:
  18
  19 ```rust
  20 let mut range = 0..10;
  21
  22 loop {
  23     match range.next() {
  24         Some(x) => {
  25             println!("{}", x);
  26         },
  27         None => { break }
  28     }
  29 }
  30 ```
  31
  32 We make a mutable binding to the range, which is our iterator. We then `loop`,
  33 with an inner `match`. This `match` is used on the result of `range.next()`,
  34 which gives us a reference to the next value of the iterator. `next` returns an
  35 `Option<i32>`, in this case, which will be `Some(i32)` when we have a value and
  36 `None` once we run out. If we get `Some(i32)`, we print it out, and if we get
  37 `None`, we `break` out of the loop.
  38
  39 This code sample is basically the same as our `for` loop version. The `for`
  40 loop is just a handy way to write this `loop`/`match`/`break` construct.
  41
  42 `for` loops aren't the only thing that uses iterators, however. Writing your
  43 own iterator involves implementing the `Iterator` trait. While doing that is
  44 outside of the scope of this guide, Rust provides a number of useful iterators
  45 to accomplish various tasks. Before we talk about those, we should talk about a
  46 Rust anti-pattern. And that's using ranges like this.
  47
  48 Yes, we just talked about how ranges are cool. But ranges are also very
  49 primitive. For example, if you needed to iterate over the contents of a vector,
  50 you may be tempted to write this:
  51
  52 ```rust
  53 let nums = vec![1, 2, 3];
  54
  55 for i in 0..nums.len() {
  56     println!("{}", nums[i]);
  57 }
  58 ```
  59
  60 This is strictly worse than using an actual iterator. You can iterate over vectors
  61 directly, so write this:
  62
  63 ```rust
  64 let nums = vec![1, 2, 3];
  65
  66 for num in &nums {
  67     println!("{}", num);
  68 }
  69 ```
  70
  71 There are two reasons for this. First, this more directly expresses what we
  72 mean. We iterate through the entire vector, rather than iterating through
  73 indexes, and then indexing the vector. Second, this version is more efficient:
  74 the first version will have extra bounds checking because it used indexing,
  75 `nums[i]`. But since we yield a reference to each element of the vector in turn
  76 with the iterator, there's no bounds checking in the second example. This is
  77 very common with iterators: we can ignore unnecessary bounds checks, but still
  78 know that we're safe.
  79
  80 There's another detail here that's not 100% clear because of how `println!`
  81 works. `num` is actually of type `&i32`. That is, it's a reference to an `i32`,
  82 not an `i32` itself. `println!` handles the dereferencing for us, so we don't
  83 see it. This code works fine too:
  84
  85 ```rust
  86 let nums = vec![1, 2, 3];
  87
  88 for num in &nums {
  89     println!("{}", *num);
  90 }
  91 ```
  92
  93 Now we're explicitly dereferencing `num`. Why does `&nums` give us
  94 references?  Firstly, because we explicitly asked it to with
  95 `&`. Secondly, if it gave us the data itself, we would have to be its
  96 owner, which would involve making a copy of the data and giving us the
  97 copy. With references, we're just borrowing a reference to the data,
  98 and so it's just passing a reference, without needing to do the move.
  99
 100 So, now that we've established that ranges are often not what you want, let's
 101 talk about what you do want instead.
 102
 103 There are three broad classes of things that are relevant here: iterators,
 104 *iterator adapters*, and *consumers*. Here's some definitions:
 105
 106 * *iterators* give you a sequence of values.
 107 * *iterator adapters* operate on an iterator, producing a new iterator with a
 108   different output sequence.
 109 * *consumers* operate on an iterator, producing some final set of values.
 110
 111 Let's talk about consumers first, since you've already seen an iterator, ranges.
 112
 113 ## Consumers
 114
 115 A *consumer* operates on an iterator, returning some kind of value or values.
 116 The most common consumer is `collect()`. This code doesn't quite compile,
 117 but it shows the intention:
 118
 119 ```rust,ignore
 120 let one_to_one_hundred = (1..101).collect();
 121 ```
 122
 123 As you can see, we call `collect()` on our iterator. `collect()` takes
 124 as many values as the iterator will give it, and returns a collection
 125 of the results. So why won't this compile? Rust can't determine what
 126 type of things you want to collect, and so you need to let it know.
 127 Here's the version that does compile:
 128
 129 ```rust
 130 let one_to_one_hundred = (1..101).collect::<Vec<i32>>();
 131 ```
 132
 133 If you remember, the `::<>` syntax allows us to give a type hint,
 134 and so we tell it that we want a vector of integers. You don't always
 135 need to use the whole type, though. Using a `_` will let you provide
 136 a partial hint:
 137
 138 ```rust
 139 let one_to_one_hundred = (1..101).collect::<Vec<_>>();
 140 ```
 141
 142 This says "Collect into a `Vec<T>`, please, but infer what the `T` is for me."
 143 `_` is sometimes called a "type placeholder" for this reason.
 144
 145 `collect()` is the most common consumer, but there are others too. `find()`
 146 is one:
 147
 148 ```rust
 149 let greater_than_forty_two = (0..100)
 150                              .find(|x| *x > 42);
 151
 152 match greater_than_forty_two {
 153     Some(_) => println!("We got some numbers!"),
 154     None => println!("No numbers found :("),
 155 }
 156 ```
 157
 158 `find` takes a closure, and works on a reference to each element of an
 159 iterator. This closure returns `true` if the element is the element we're
 160 looking for, and `false` otherwise. Because we might not find a matching
 161 element, `find` returns an `Option` rather than the element itself.
 162
 163 Another important consumer is `fold`. Here's what it looks like:
 164
 165 ```rust
 166 let sum = (1..4).fold(0, |sum, x| sum + x);
 167 ```
 168
 169 `fold()` is a consumer that looks like this:
 170 `fold(base, |accumulator, element| ...)`. It takes two arguments: the first
 171 is an element called the *base*. The second is a closure that itself takes two
 172 arguments: the first is called the *accumulator*, and the second is an
 173 *element*. Upon each iteration, the closure is called, and the result is the
 174 value of the accumulator on the next iteration. On the first iteration, the
 175 base is the value of the accumulator.
 176
 177 Okay, that's a bit confusing. Let's examine the values of all of these things
 178 in this iterator:
 179
 180 | base | accumulator | element | closure result |
 181 |------|-------------|---------|----------------|
 182 | 0    | 0           | 1       | 1              |
 183 | 0    | 1           | 2       | 3              |
 184 | 0    | 3           | 3       | 6              |
 185
 186 We called `fold()` with these arguments:
 187
 188 ```rust
 189 # (1..4)
 190 .fold(0, |sum, x| sum + x);
 191 ```
 192
 193 So, `0` is our base, `sum` is our accumulator, and `x` is our element.  On the
 194 first iteration, we set `sum` to `0`, and `x` is the first element of `nums`,
 195 `1`. We then add `sum` and `x`, which gives us `0 + 1 = 1`. On the second
 196 iteration, that value becomes our accumulator, `sum`, and the element is
 197 the second element of the array, `2`. `1 + 2 = 3`, and so that becomes
 198 the value of the accumulator for the last iteration. On that iteration,
 199 `x` is the last element, `3`, and `3 + 3 = 6`, which is our final
 200 result for our sum. `1 + 2 + 3 = 6`, and that's the result we got.
 201
 202 Whew. `fold` can be a bit strange the first few times you see it, but once it
 203 clicks, you can use it all over the place. Any time you have a list of things,
 204 and you want a single result, `fold` is appropriate.
 205
 206 Consumers are important due to one additional property of iterators we haven't
 207 talked about yet: laziness. Let's talk some more about iterators, and you'll
 208 see why consumers matter.
 209
 210 ## Iterators
 211
 212 As we've said before, an iterator is something that we can call the
 213 `.next()` method on repeatedly, and it gives us a sequence of things.
 214 Because you need to call the method, this means that iterators
 215 can be *lazy* and not generate all of the values upfront. This code,
 216 for example, does not actually generate the numbers `1-100`, instead
 217 creating a value that merely represents the sequence:
 218
 219 ```rust
 220 let nums = 1..100;
 221 ```
 222
 223 Since we didn't do anything with the range, it didn't generate the sequence.
 224 Let's add the consumer:
 225
 226 ```rust
 227 let nums = (1..100).collect::<Vec<i32>>();
 228 ```
 229
 230 Now, `collect()` will require that the range gives it some numbers, and so
 231 it will do the work of generating the sequence.
 232
 233 Ranges are one of two basic iterators that you'll see. The other is `iter()`.
 234 `iter()` can turn a vector into a simple iterator that gives you each element
 235 in turn:
 236
 237 ```rust
 238 let nums = vec![1, 2, 3];
 239
 240 for num in nums.iter() {
 241    println!("{}", num);
 242 }
 243 ```
 244
 245 These two basic iterators should serve you well. There are some more
 246 advanced iterators, including ones that are infinite.
 247
 248 That's enough about iterators. Iterator adapters are the last concept
 249 we need to talk about with regards to iterators. Let's get to it!
 250
 251 ## Iterator adapters
 252
 253 *Iterator adapters* take an iterator and modify it somehow, producing
 254 a new iterator. The simplest one is called `map`:
 255
 256 ```rust,ignore
 257 (1..100).map(|x| x + 1);
 258 ```
 259
 260 `map` is called upon another iterator, and produces a new iterator where each
 261 element reference has the closure it's been given as an argument called on it.
 262 So this would give us the numbers from `2-100`. Well, almost! If you
 263 compile the example, you'll get a warning:
 264
 265 ```text
 266 warning: unused result which must be used: iterator adaptors are lazy and
 267          do nothing unless consumed, #[warn(unused_must_use)] on by default
 268 (1..100).map(|x| x + 1);
 269  ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 270 ```
 271
 272 Laziness strikes again! That closure will never execute. This example
 273 doesn't print any numbers:
 274
 275 ```rust,ignore
 276 (1..100).map(|x| println!("{}", x));
 277 ```
 278
 279 If you are trying to execute a closure on an iterator for its side effects,
 280 just use `for` instead.
 281
 282 There are tons of interesting iterator adapters. `take(n)` will return an
 283 iterator over the next `n` elements of the original iterator. Note that this
 284 has no side effect on the original iterator. Let's try it out with our infinite
 285 iterator from before:
 286
 287 ```rust
 288 # #![feature(step_by)]
 289 for i in (1..).step_by(5).take(5) {
 290     println!("{}", i);
 291 }
 292 ```
 293
 294 This will print
 295
 296 ```text
 297 1
 298 6
 299 11
 300 16
 301 21
 302 ```
 303
 304 `filter()` is an adapter that takes a closure as an argument. This closure
 305 returns `true` or `false`. The new iterator `filter()` produces
 306 only the elements that that closure returns `true` for:
 307
 308 ```rust
 309 for i in (1..100).filter(|&x| x % 2 == 0) {
 310     println!("{}", i);
 311 }
 312 ```
 313
 314 This will print all of the even numbers between one and a hundred.
 315 (Note that because `filter` doesn't consume the elements that are
 316 being iterated over, it is passed a reference to each element, and
 317 thus the filter predicate uses the `&x` pattern to extract the integer
 318 itself.)
 319
 320 You can chain all three things together: start with an iterator, adapt it
 321 a few times, and then consume the result. Check it out:
 322
 323 ```rust
 324 (1..1000)
 325     .filter(|&x| x % 2 == 0)
 326     .filter(|&x| x % 3 == 0)
 327     .take(5)
 328     .collect::<Vec<i32>>();
 329 ```
 330
 331 This will give you a vector containing `6`, `12`, `18`, `24`, and `30`.
 332
 333 This is just a small taste of what iterators, iterator adapters, and consumers
 334 can help you with. There are a number of really useful iterators, and you can
 335 write your own as well. Iterators provide a safe, efficient way to manipulate
 336 all kinds of lists. They're a little unusual at first, but if you play with
 337 them, you'll get hooked. For a full list of the different iterators and
 338 consumers, check out the [iterator module documentation](../std/iter/index.html).