CODEWITHSUNDEEP
f#performanceimmutabilitypersistent
Mehran
Mehran

Reputation: 2027

Are F# lists persistent?

I'm a C# developer new to F#,I understand that in .net the strings are immutable. In other words every time you modify a string you get a new string instance.

For a non functional mind like mine the first question would be efficiency and I understand that C# mutable objects are not persistent. since string manipulation is normally trivial in most of applications.

My question is, Is this the case for F# lists too?, Do F# clones every list on change? Like for example, when filtering a list do I create a new list with fewer Items?

Update: I'm not comparing .net string and lists. I named string as an example of an immutable object and want to know if F# provides any special treatment for it's List.

This is what I mean by "persistent".

Upvotes: 5

Views: 948

Answers (5)

Tomas Petricek
Tomas Petricek

Reputation: 243051

I think that the references from Dan and Brian should directly answer your question. If you want to find out more, you can also look at the following materials (published just this week at MSDN) that were written to explain F# and functional concepts to .NET developers:

Upvotes: 1

Adam Gent
Adam Gent

Reputation: 49085

The best way to understand lists in functional languages to understand Cons Cells

Upvotes: 0

Dan Abramov
Dan Abramov

Reputation: 268255

I think Dustin Campbell's introduction does an amazing job of explaining list immutability.

In the functional world, lists are immutable. This means that node sharing is possible because the original lists will never change. Because the first list ends with the empty list, its nodes must be copied in order to point its last node to the second list. After the append operation, our lists look like so:

enter image description here

At this point, the more skeptical among you might be saying, "Well, that's a pretty interesting theory, but can you prove it?"

No problem.

Using the knowledge that F# lists are recursive, we can retrieve the last half of combined (the inner list starting at 4) by taking the tail, of its tail, of its tail. List.tl is the function that F# provides for extracting a list's tail.

> let lastHalf = List.tl (List.tl (List.tl combined));;

val lastHalf : int list

> lastHalf;;

val it : int list = [4; 5; 6]

Finally, because F# is first-class citizen of the .NET Framework, we have full access to all of the base class libraries. So, we can use the Object.ReferenceEquals method to test whether or not lastHalf and second are indeed the same instance.

> System.Object.ReferenceEquals(lastHalf, second);;

val it : bool = true

And there you have it. Believe it or not, appending two immutable lists can actually be faster and more memory efficient than appending mutable lists because fewer nodes have to be copied.

Upvotes: 7

Brian
Brian

Reputation: 118865

F# lists are immutable. There are no APIs to 'modify' an F# list, so there is no cloning involved. Operations like List.filter do create a new list (which might share some structure with the original, if possible).

(This is how all immutable objects in any language work, I think.)

See e.g.

http://en.wikipedia.org/wiki/Persistent_data_structure

for a nice description along with pictures that suggest how sharing works.

Upvotes: 1

Charles Lambert
Charles Lambert

Reputation: 5132

F# lists are linked lists. So when you create a new list it simply adds the item to the existing list and points to the head, which contains the new item. The original list still points to the item that was the head at the time that list was created. So in other words, they all point to the same list at different spots within the list.

Upvotes: 0

Related Questions