I'm trying to compare these two functions to see which has the best algorithm. I been looking at Order of n complexity, and although I don't know how to arrive at it mathematically (which is a shame) I can sometimes guess the order. I think to know if the algorithm is better than another I need to look at them in terms of asymptotic time, complexity and experimentally.
let flatten1 xs = List.fold (@) [] xs
let flatten2 xs = List.foldBack (@) xs []
I used the F# #time feature and this is what I got.
Real: 00:00:00.001, CPU: 00:00:00.000, GC gen0: 0, gen1: 0, gen2: 0
val it : int list =
[1; 2; 3; 5; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11; 12; 13; 14; 15; 16; 17; 18; 19;
20; 5; 4; 5; 6]
>
Real: 00:00:00.001, CPU: 00:00:00.000, GC gen0: 0, gen1: 0, gen2: 0
val it : int list =
[1; 2; 3; 5; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11; 12; 13; 14; 15; 16; 17; 18; 19;
20; 5; 4; 5; 6]
With xs of length n and each operation f is O(1), List.fold f xs and List.foldBack f xs have the same complexity O(n).
However, @ is more complex than that. Assume that you run flatten1 and flatten2 on xs of length n where each of elements is a list of length m. The resulting list is of length n*m
Since @ is O(k) where k is length of the first list, complexity of flatten1 is:
// After each `@` call, the first list (the accumulator) increases its length by `m`
O(m + 2*m + 3*m + ... + (n-1)*m)
= O(n*(n-1)*m/2)
In case of flatten2, the first list is always a list of length m:
O(m + m + ... + m) // n-1 steps
= O((n-1)*m)
You can easily see that flatten2 will be much more efficient than flatten1. Difference in time complexity will dominate the extra allocation of List.foldBack anyway. To illustrate, here is a quick test showing the difference
let flatten1 xs = List.fold (@) [] xs
let flatten2 xs = List.foldBack (@) xs []
let xs = [ for _ in 1..1000 -> [1..100] ]
#time "on";;
// Real: 00:00:01.456, CPU: 00:00:01.466, GC gen0: 256, gen1: 124, gen2: 1
let xs1 = flatten1 xs;;
// Real: 00:00:00.007, CPU: 00:00:00.000, GC gen0: 1, gen1: 0, gen2: 0
let xs2 = flatten2 xs;;
Note that you can just use List.concat, an efficient implementation of flatten function.