The other day, I stumbled on Ivan Towlson's A Practical Developer’s Introduction to F#. It’s one of the best introductions I’ve seen in a long time, simply because it’s so practically oriented. I learned a couple of things about F# from the video, which I'll summarize in a couple of posts.
The first thing I learned is how the F# list type, which is a linked list and not List<T>, is immutable for reasons of safety and efficiency. Once you create a list, you can never again modify this exact instance. If you do, what you’ll get back is a new list. Think of the safety in terms of threads: if one thread, inadvertently or not, modifies the list, it'll just get back a new list, shielding any other thread from the change.
This copy-on-modification behavior may seem inefficient at first. And it would be if it weren't for F#'s ability to share part of a list:
let smallOddPrimes = [3; 5; 7] let smallPrimes = 2 :: smallOddPrimes // [2; 3; 5; 7]
When you create the smallPrimes list, F# need only create one additional cell containing the even prime. The next pointer of this cell will be a reference to the smallOddPrimes list:
Object.ReferenceEquals(smallPrimes.Tail, smallOddPrimes) // true
The tail of the smallPrimes list — the possibly empty list comprised of everything but the first element — points back to smallOddPrimes list, saving both processing time and memory while retaining thread-safety.