Interactive Session #10: List, Array, Sequence

F# supports three different list-like data structures to store values of the same type: List, Array and Sequence. In this session we want to explore the similarities and differences among these three types. First lets instantiate values of each of these types.

> [0; 1; 2];;
val it : int list = [0; 1; 2]
> [0..10];;
val it : int list = [0; 1; 2; 3; 4; 5; 6; 7; 8; 9; 10]
> [|3; 4; 5|];;
val it : int [] = [|3; 4; 5|]
> [|0..10|];;
val it : int [] = [|0; 1; 2; 3; 4; 5; 6; 7; 8; 9; 10|]
> seq { 6..8 };;   
val it : seq<int> = seq [6; 7; 8]

Now lets create large values to see how each type performs.

> [0..10000000];;
val it : int list =
 [0; 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; ...]
> [|0..10000000|];;
val it : int [] =
 [|0; 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; ...|]
> seq { 0..10000000 };;
val it : seq<int> = seq [0; 1; 2; 3; ...]

On my machine the creation of the list and array values needed a couple of seconds, however, the creation time of the sequence value was unnoticeable. This is due to the fact, that the sequence type does not compute its values immediately, but only on demand, this strategy is called lazy evaluation and is one of the primary computation strategies in functional programming languages.

Accessing and modifying individual elements is also different between lists, arrays and sequences. List elements may only be read, but not modified. Array elements can be read and modified. Sequences are not intended for reading and modifying individual elements (you could but it is rather tedious).

> let l = [0..10];;

val l : int list = [0; 1; 2; 3; 4; 5; 6; 7; 8; 9; 10]

> let a = [|1..10|];;

val a : int [] = [|1; 2; 3; 4; 5; 6; 7; 8; 9; 10|]

> let s = seq { 0..10 };;

val s : seq<int>

> l.Item(5);;
val it : int = 5
> a.[0];;
val it : int = 5
> l.[0] <- 5;;

 l.[0] <- 5;;
 ^^^^^^^^^^

~/stdin(29,1): error FS0810: Property 'Item' cannot be set
> a.[0] <- 5;;
val it : unit = ()
> a;;
val it : int [] = [|5; 2; 3; 4; 5; 6; 7; 8; 9; 10|]

Iter, map, fold and filter functions are available for all three types.

> List.map (fun i -> i*i) l;;
val it : int list = [0; 1; 4; 9; 16; 25; 36; 49; 64; 81; 100]
> Array.map (fun i -> i*i) a;;
val it : int [] = [|25; 4; 9; 16; 25; 36; 49; 64; 81; 100|]
> Seq.map (fun i -> i*i) s;;
val it : seq<int> = seq [0; 1; 4; 9; ...]

Out of the above simple exercises we can derive the following guidelines for the usage of list, array and sequence types:

  • use arrays when your algorithm needs in-place replacement
  • use sequences for processing and transforming large amounts of data (up to infinite sequences), also when each element is computed using a function
  • use lists for all other cases

Further reading:

Advertisements
This entry was posted in Getting Started, Language. Bookmark the permalink.

One Response to Interactive Session #10: List, Array, Sequence

  1. Pingback: Rick Minerich's Development Wonderland : F# Discoveries This Week 10/03/2010

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s