Why is List.foldBack as fast as List.fold

Question

"Lists in F# are implemented as singly linked lists, which means that operations that access only the head of the list are O(1), and element access is O(n)." - http://msdn.microsoft.com/en-us/library/dd233224.aspx

Considering this, List.foldBack, which accesses elements from the last to the first element, should be notable slower than List.fold. However, I cannot confirm this by tests:

let f acc x = acc + x
List.fold f 100 [1 .. 5000000] ;;
List.foldBack f [1 .. 5000000] 100;;

#time

> List.fold f 100 [1 .. 5000000] ;;
Real: 00:00:01.379, CPU: 00:00:01.468, GC gen0: 29, gen1: 26, gen2: 2
val it : int = 1647668740
> List.foldBack f [1 .. 5000000] 100;;
Real: 00:00:01.417, CPU: 00:00:01.500, GC gen0: 28, gen1: 25, gen2: 2
val it : int = 1647668740
> 

Why does List.foldBack perform equally to List.fold?

Answer 1

If you look at the source for List.foldBack you can see that it converts the list into an array and then iterates over it from the end applying the accumulator function to get the result.