I was reading this and was wondering if :: is always more efficient than @ or if only in that particular implementation of rev
let rec rev = function
| [] -> []
| h::t -> rev t @ [h]
let rev l =
let aux accu = function
| [] -> accu
| h::t -> aux (h :: accu) t
For example, if I wanted to append an element on a queue, would there be a difference in these two methods:
let append x q = q @ [x]
and
type 'a queue = {front:'a list; back:'a list}
let norm = function
| {front=[]; back} -> {front=List.rev back; back=[]}
| q -> q
let append x q = norm {q with back=x::q.back}
@ is O(n) in the size of its left operand. :: is O(1) and List.rev (as defined in the standard library) is O(n).
So if you apply @ n times, you get an O(n^2) algorithm. But if you apply :: n times, that's only O(n) and if you then reverse the result once at the end, it's still O(n). This is true in general and for that reason any algorithm that appends to the end of a list multiple times, should instead prepend to the beginning of the list multiple times and then reverse the result.
However your example is different. Here you're replacing one single use of @ with one possible use of rev. Since both are O(n), you end up with the same complexity in the case where you use rev.
However the case where you use rev won't happen a lot, so the complexity of enqueuing n should end up amortized O(n) (and if you don't dequeue anything in between, it's just plain O(n)). Whereas your version using @ would lead to O(n^2).