Most of Standard ML has immutability. Behind the scenes, references may be in use for optimization purposes, but the language guarantees that there is no program that will allow the user to determine if references are in use.
So as an example, tl is \(O(1)\) because it just returns a reference to the tail of the list.