Blog: Mr. Mathiesen

F# - List prepend (::) vs. concatenate (@)

March 12, 2014.

Code Snippet:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

let foo xs =
  let rec foo' acc = function
    | [] -> List.rev acc
    | x::xs -> foo' (x::acc) xs
  xs |> foo' [] 

let bar xs =
  let rec bar' acc = function
    | [] -> acc
    | x::xs -> bar' (acc@[x]) xs
  xs |> bar' []

[1 .. 10000] |> foo

[1 .. 10000] |> bar

Code output:

> val foo : xs:'a list -> 'a list
> val bar : xs:'a list -> 'a list

> #time;;

--> Timing now on

> Real: 00:00:00.001, CPU: 00:00:00.001, GC gen0: 0, gen1: 0
val it : int list =
  [1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11; 12; 13; 14; 15; 16; 17; 18; 19; 20; 21;
   22; 23; 24; 25; 26; 27; 28; 29; 30; 31; 32; 33; 34; 35; 36; 37; 38; 39; 40;
   41; 42; 43; 44; 45; 46; 47; 48; 49; 50; 51; 52; 53; 54; 55; 56; 57; 58; 59;
   60; 61; 62; 63; 64; 65; 66; 67; 68; 69; 70; 71; 72; 73; 74; 75; 76; 77; 78;
   79; 80; 81; 82; 83; 84; 85; 86; 87; 88; 89; 90; 91; 92; 93; 94; 95; 96; 97;
   98; 99; 100; ...]

> Real: 00:00:01.308, CPU: 00:00:01.265, GC gen0: 190, gen1: 2
val it : int list =
  [1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11; 12; 13; 14; 15; 16; 17; 18; 19; 20; 21;
   22; 23; 24; 25; 26; 27; 28; 29; 30; 31; 32; 33; 34; 35; 36; 37; 38; 39; 40;
   41; 42; 43; 44; 45; 46; 47; 48; 49; 50; 51; 52; 53; 54; 55; 56; 57; 58; 59;
   60; 61; 62; 63; 64; 65; 66; 67; 68; 69; 70; 71; 72; 73; 74; 75; 76; 77; 78;
   79; 80; 81; 82; 83; 84; 85; 86; 87; 88; 89; 90; 91; 92; 93; 94; 95; 96; 97;
   98; 99; 100; ...]

References:

  • MSDN: 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).
  • Wikipedia: In Standard ML, lists are represented as imbalanced binary trees, and thus it is efficient to prepend an element to a list, but inefficient to append an element to a list. The extra pass over the list is a linear time operation, so while this technique requires more wall clock time, the asymptotics are not any worse.