StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POHow is memory-efficient non-destructive manipulation of collections achieved in functional programming?
text
Body
copied!<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 | [] -> [] | x::xs -> 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 | [] -> [] | x::xs -> 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) |> 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>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload