The modules Map, List and Set are examples of immutable data structures. When you add something to a list (e.g. using the :: 'cons' operator, as in 1 :: oldList) you get back a new object, which will contain an interior pointer to the old object.
The great thing about immutable data structures is that once you've got them they don't change! This gives your program very strong Invariants. That means you can use the data structures in backtracking algorithms, save them in error reports, pass them between threads and serialize them to/frm disk without really having to think about the object-identity semantics of the data structure - a map is a map, and with no hidden "gotchas" caused by other code mutating the map under your feet.
F# supports MutableDataStructures as well. Immutable data structures can contain mutable members. For example, you can have an immutable list whose members are mutable records, or a Map whose range includes mutable records. The elements of a set and the domain of a map should not be mutable. When using the [Set.Make] and [Map.Make] functors the comparison functions should be invariant.
