XO0909: a list update that copies the whole list every iteration

Reported by xo vet --cost, which builds the program and reads what the compiler did. A list update (push, set, pop, take) copies the list unless its count is 1. When the loop keeps the list as well as updating it (snaps.push(xs), or a name bound to it and used after the update), the count is 2 at every update, so each iteration copies the whole list: O(n squared). A holder made before the loop costs one copy, after which the loop’s list is its own again; a loop that updates the list on every iteration has that one copy moved to its entry. Update a copy you own, or keep the other holder out of the loop.

Example

fn history(n: Int) -> Int {
  var xs: List[Int] = []
  var snaps: List[List[Int]] = []
  for i in 0..n {
    snaps.push(xs)
    xs.push(i)
  }
  snaps.len() + xs.len()
}

Fix

fn history(n: Int) -> Int {
  var xs: List[Int] = []
  var lens: List[Int] = []
  for i in 0..n {
    lens.push(xs.len())
    xs.push(i)
  }
  lens.len() + xs.len()
}

Run xo explain XO0909 for this text in a terminal, or see section 10.6 of the specification.