.

Summary

F# Lists, Arrays and Tuples

This page covers the basics of

• F# Lists
• F# Arrays
• F# 2-Dimensional Arrays
• F# Tuples

It does not cover

• System . Collections . Generic . List<_>
• System . Collections . ArrayList
• Programming with Vectors
• Programming with Matrices
• etc.

F# Lists

F# lists are immutable linked lists (types written as "list<int>" or "int list"). A useful structure for functional programming, but not the right data structure for matrices or high-efficiency programming with large data structures.

1. Literals and pattern matching
2. Immutable (never need to shallow copy)
3. Will often share internal nodes (like most immutable data structures)
4. Very fast to generate a new list with an element added to the front
5. Good for mapping and folding
6. Linear lookup time.

• Precisely the same as Microsoft . FSharp . Collections . List<_>.
• Precisely different to System . Collections. Generic . List<_>.

  Empty                     []  
  Example Literal           [1;2;3] 
  Example Pattern           [_;x;y] 
  Example Indexed Creation  List.init 10 (fun i -> i*3)
  Add to front (cons)       elem :: rest
  Head of list (car)        List.hd someList
  Tail of list (cdr)        List.tl someList
  Example Lookup            List.nth [1;2;3;4] 2
  Dimension                 List.length someList


  Map                       List.map (fun x -> x + 3) someList
                    or      someList |> List.map (fun x -> x + 3)


  Iterate                   List.iter (fun x -> Printf.printf "x = %d\n" x) someList
                    or      someList |> List.iter (fun x -> Printf.printf "x = %d\n" x)


  Fold                      List.fold_left  f state someList
                    or      List.fold_right f someList state


  Other operations          See Microsoft.FSharp.MLLib.List (i.e. the module List)

F# Arrays

F# arrays (as in "int[]" or "int array") are mutable "flat storage" arrays, coinciding with .NET arrays, and are an efficient building block for other data structures. These may not be resized (you have to allocate a new array and copy)

1. Literals
2. Very efficient storage (e.g. double[] is stored 'flat')
3. Constant lookup time
4. Can be enormous
5. Support mapping and folding
6. No sharing of immediate storage with other arrays
7. Beware of mutability

• Precisely the same as .NET arrays
• Related to System . Collections . Generic . List<_>, which uses an array underneath but is resizeable

  Empty                     [| |]  
  Example Literal           [| 1;2;3 |] 
  Example Indexed Creation  Array.init 10 (fun i -> i*3) 
  Example Lookup            arr.(2)
  Example Set               arr.(2) <- 4
  Subrange                  Array.sub arr start length
  Blit                      Array.blit src srcStart dest destStart length
  Dimension                 Array.length arr
                       or   arr.Length
  Shallow Copy              Array.copy arr


  Map                       Array.map (fun x -> x + 3) arr
                    or      arr |> Array.map (fun x -> x + 3)


  Iterate                   Array.iter (fun x -> Printf.printf "x = %d\n" x) arr
                    or      arr |> Array.iter (fun x -> Printf.printf "x = %d\n" x)


  Fold                      Array.fold_left  f state arr 
                            Array.fold_right f arr state


  Other operations          See Microsoft.FSharp.MLLib.Array (i.e. the module Array) and System.Array 

F# Two-Dimensional Arrays

F# 2-D arrays (as in "int[,]") are mutable "flat storage" non-jagged 2D arrays, coinciding with .NET 2D arrays, and are a very efficient building block for matrices. These may not be resized (you have to allocate a new array and copy). Not available in F# unless using .NET 2.0.

1. Very efficient storage (e.g. double[,] is stored 'flat')
2. Good for mapping and folding
3. Constant lookup time
4. No Literals (as of 1.1.3.2)
5. No sharing of immediate storage with other arrays
6. Beware of mutability

• Precisely the same as .NET 2D arrays

  Empty                     Array2.zero_create 0 0  
  Example Literal           PROPOSED: new int[,] { 1;2;3 }
  Example Indexed Creation  Array2.init 10 10 (fun i j -> i*3 + j)
  Example Lookup            arr.(2,3)
  Example Set               arr.(2,3) <- 4
  Dimension 1               Array2.length1 arr
                       or   Array2.GetLength(0)
  Dimension 2               Array2.length2 arr
                       or   arr.GetLength(1)
  Shallow Copy              Array2.copy arr
  Subrange                  Array2.sub arr start1 start2 length1 length2
  Subrange                  Array2.blit src srcStart1 srcStart2 dest destStart1 destStart2 length1 length2


  Map                       Array2.map f arr
                      or    arr |> Array2.map f


  Iterate                   Array2.iter f l
                      or    l |> Array2.iter f


  Other operations          See Microsoft.FSharp.MLLib.Array2 (i.e. the module Array2)

F# Tuples

F# tuples (as in "int * int" or "int * string * int") are different to both lists and arrays, because the F# type system tracks the exact type-shape of the individual elements of tuples explicitly.

1. Literals and Patterns
2. OK storage (each tuple is a new object)
3. Constant lookup time
4. No mutation

• Precisely the same as Microsoft . FSharp . Tuple<,...,>

  Empty                  ()
  Example Literal        (1,"2",3)
  Example Lookup         match p with (x,y,z) -> y
  Map                    match p with (x,y,z) -> (x,f y,z)
  Iterate                match p with (x,y,z) -> f y
  Fold                   match p with (x,y,z) -> f x (f y (f z acc))


  Other operations       Define as needed