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