Runtime of List.length

[TysonMN]

Can the runtime of List.length be added to the Remarks section of its documentation?

The standard implementation for a linked list would have linear runtime, but maybe F#'s list caches the length in the "head node" so that a constant runtime is possible. Since F#'s list is immutable, this is a textbook example of a time-space tradeoff: either choice has advantages over the other.

I briefly looked at the F# code to see if I could determine for myself what the implementation (and thus runtime) is. If someone wants to "teach me how to fish" in addition to "giving me a fish", that too would be greatly appreciated.

[TysonMN]

Based on these runtime tests, it appears to be a linear-time computation.

Case 1 compuated in 00:00:00.0004770 has length 10
Case 2 compuated in 00:00:00.0000022 has length 100
Case 3 compuated in 00:00:00.0000286 has length 1000
Case 4 compuated in 00:00:00.0003881 has length 10000
Case 5 compuated in 00:00:00.0008908 has length 100000
Case 6 compuated in 00:00:00.0070297 has length 1000000
Case 7 compuated in 00:00:00.0586394 has length 10000000
Case 8 compuated in 00:00:00.4871563 has length 100000000

[abelbraaksma]

That is correct, lists are implemented as singly linked lists and determining the length requires iteration over it until the last item, performance is O(n). Conversely, arrays have a fixed length and getting this length is O(1). While at it, sequences need to be evaluated in full, which can have side effects, but apart from that, getting their length is O(n).

I agree that the docs should have info on performance characteristics, I think there's a more general item open somewhere.