title: How is memory-efficient non-destructive manipulation of collections achieved in functional programming?
body: <p>I'm trying to figure out how non-destructive manipulation of large collections is implemented in functional programming, ie. how it is possible to alter or remove single elements without having to create a completely new collection where all elements, even the unmodified ones, will be duplicated in memory. (Even if the original collection would be garbage-collected, I'd expect the memory footprint and general performance of such a collection to be awful.)</p>
  
  <h2>This is how far I've got until now:</h2>
  
  <p>Using F#, I came up with a function <code>insert</code> that splits a list into two pieces and introduces a new element in-between, seemingly without cloning all unchanged elements:</p>
  
  <pre><code>// return a list without its first n elements:
  // (helper function)
  let rec skip list n =
      if n = 0 then
          list
      else
          match list with
          | []    -&gt; []
          | x::xs -&gt; skip xs (n-1)
  
  // return only the first n elements of a list:
  // (helper function)
  let rec take list n =
      if n = 0 then
          []
      else
          match list with
          | []    -&gt; []
          | x::xs -&gt; x::(take xs (n-1))
  
  // insert a value into a list at the specified zero-based position:
  let insert list position value =
      (take list position) @ [value] @ (skip list position)
  </code></pre>
  
  <p>I then checked whether objects from an original list are "recycled" in new lists by using .NET's <code>Object.ReferenceEquals</code>:</p>
  
  <pre><code>open System
  
  let (===) x y =
      Object.ReferenceEquals(x, y)
  
  let x = Some(42)
  let L = [Some(0); x; Some(43)]
  let M = Some(1) |&gt; insert L 1
  </code></pre>
  
  <p>The following three expressions all evaluate to <code>true</code>, indicating that the value referred to by <code>x</code> is re-used both in lists <code>L</code> and <code>M</code>, ie. that there is only 1 copy of this value in memory:</p>
  
  <pre><code>L.[1] === x
  M.[2] === x
  L.[1] === M.[2]
  </code></pre>
  
  <h2>My question:</h2>
  
  <p>Do functional programming languages generally re-use values instead of cloning them to a new memory location, or was I just lucky with F#'s behaviour? Assuming the former, is this how reasonably memory-efficient editing of collections can be implemented in functional programming?</p>
  
  <p>(Btw.: I know about <a href="http://books.google.com/books?id=SxPzSTcTalAC" rel="noreferrer">Chris Okasaki's book <em>Purely functional data structures</em></a>, but haven't yet had the time to read it thoroughly.)</p>