Why does F# prefer lists over arrays?

Question

I'm trying to learn F# and was watching a video when something odd (at least, to me) came up. The video in question is here and the relevant part starts at 2:30 for those interested. But basically, the guy says that F# makes it awkward to work with arrays and that the designers did so on purpose because lists are easier to "prepend and append".

The question that immediately sprang to mind: isn't easy prepending and appending something that should be frowned upon in an immutable language? Specifically, I'm thinking of C#'s Lists where you can do something like List.Add(obj); and mutate the list. With an array you'd have to create an entirely new array, but that's also what would need to happen in an immutable language.

So why do the designers of F# prefer lists? What is the fundamental difference in an immutable environment between a list and an array? What am I missing? Are lists in F# really linked lists?

Answer 1

I would disagree that "F# makes it awkward to work with arrays". In fact, F# makes working with arrays quite nice compared to most languages.

For example, F# has literal array construction: let arr = [|1;2;3;4;|]. And perhaps even cooler, pattern matching on arrays:

match arr with | [|1;2;_;_|] -> printfn "Starts with 1;2" | [|_;_;3;4|] -> printfn "Ends with 3;4" | _ -> printfn "Array not recognized" 

As to why immutable singly linked lists are preferred in functional programming like F#, there's a lot to say, but the short answer is that it allows an O(1) prepend efficiency, and allows the implementation to share nodes, so it is easy on memory. For example,

let x = [2;3] let y = 1::x 

Here y is created by prepending 1 to x, but x is neither modified nor copied, so making y was very cheap. We can see a bit how this is possible, since x points to the head, 2, of the initially constructed list and can only move forward, and since the elements of the list it points to can't be mutated, it doesn't matter that y shares nodes with it.