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