What happens in memory when working with immutable lists?

Question

What happens in memory when working with immutable lists?

Is a Deep Copy performed when invoking List.Append?

What is the Big-O Notation to describe this operation for F# Lists?

Is it still O(1) when adding a node to the end of a list?

If not, then why would using an immutable list be useful if using an immutable list violates the intended performance of a linked list?

Consider the following statement:

_modules <- _modules |> List.append moduleItems

Source Code:

type CreationViewModel() =
    inherit ViewModelBase()

    let mutable (_modules:Module list) = []

    member this.Modules
        with get()      = _modules
        and set(value)  = _modules <- value

    member this.Add moduleItem = 
        _modules <- moduleItem :: _modules

    member this.AddList moduleItems = 
        _modules <- _modules |> List.append moduleItems

In your particular case, `[moduleItem]` is the first list so your code is equivalent to `_modules <- moduleItem :: _modules`, with an extra unnecessary allocation of a single-element list. — Tarmil, Jan 24 '16 at 11:16
@Tarmil Edited the code to address your concern and match the intent of the question. Consider removing your downvote. — James Hugard, Jan 26 '16 at 08:20
@JamesHugard I wouldn't downvote just because of this, it's still a useful question to answer. In fact that's why I posted this as a comment rather than an answer. — Tarmil, Jan 26 '16 at 08:54
@Tarmil Sorry... there was a downvote... presumed from you because yours was the only comment :-) — James Hugard, Jan 26 '16 at 16:30

score 3 · Accepted Answer · answered Jan 24 '16 at 10:44

When List.append is called, the items themselves aren't copied but the pointers is the first list need to be.

This is because the list structure looks like

a::b::c::.....

so when you join two lists you go from

a::b::c::d::[] and e::f::g::h::[]

to

a::b::c::d::e::f::g::h::[]

which requires rewriting the first list.

As a result it is O(n) where n is the size of the first list

James Hugard · Answer 2 · 2016-02-08T17:56:56.607

F# lists are singly-linked, much like the following definition.

type SList<'a> =
| Cons of 'a * SList<'a>
| Nil

So, adding a new element to the head of the list is done in O(1) time, by creating a new head element and having it reference the existing tail elements(s).

> Cons ( "something", Nil );;
val it : SList<string> = Cons ("something", Nil)

Which could be used to create a list as follows:

> let test = Cons (1, Cons (2, Cons (3, Nil)));;
val test : SList<int> = Cons (1,Cons (2,Cons (3,Nil)))

However, adding a new element to the end of the list requires traversing the entire list to find the end, which takes O(N) time, in order to have the last node reference a new last node.

A trivial implementation could be defined as follows. Even though it copies the list twice, it is still O(N) because the cost scales linearly with the size of the list.

let rec fold f state = function
    | Cons(v,xs) -> fold f (f state v) xs
    | Nil -> state

let reverse xs =
    fold (fun st v -> Cons (v, st)) Nil xs

let append x xs =
    reverse ( Cons (x, (reverse xs) ) )

Note that lists defined as above are immutable.

Adding a new element at the head references an existing tail which is never modified, so the tail can be safely shared amongst multiple lists (each with different head elements).

Appending an element to the end of a list results in a new list in order to preserve immutability of the original list: changing the last element to point to a new last element means updating the previous element to point to the updated element, and so on up for every element in the list.

So why aren't F# lists doubly-linked?

Aside from historical reasons (ML only provides singly-linked lists), I believe an immutable doubly-linked list implementation would require copying the entire list when adding elements at either end, due to the need to adjust the next and prev elements of every node for either operation, thus always costing O(N) time.

An immutable singly-linked list only pays O(N) when appending to the end, so is generally more efficient.

Because of that last point, code which works with immutable lists will generally avoid appending multiple elements sequentially, which is O(M*N). Instead, such code generally reverses the list for O(N) cost, adds several elements to the head (backwards end) for O(1) cost, then reverses the result to get back the original ordering, making for an overall O(N) operation.

Note that the F# cons operator (::) is just an inline version of the ``cons`` function above; e.g., ``1 :: 2 :: 3 :: []`` — James Hugard, Jan 26 '16 at 08:11
I am not even sure how to define a double-linked list that is immutable. Consider appending to a double-linked list. The new head "points" the old head but then old head has to be made to point to the new head (double-linked). That requires mutating the old head. Perhaps there's some way to do it using a slightly more refined data structure but it seems the trivial one won't work? — Just another metaprogrammer, Jan 26 '16 at 13:25
@FuleSnabel My point exactly. See this post for more detail: http://stackoverflow.com/questions/8374010/scala-circular-references-in-immutable-data-types — James Hugard, Jan 26 '16 at 16:37

What happens in memory when working with immutable lists?

2 Answers2