You are previewing Programming F#.

Programming F#

Cover of Programming F# by Chris Smith Published by O'Reilly Media, Inc.
O'Reilly logo

Arrays

Until now, when you’ve needed to join multiple pieces of data together, you’ve used lists. Lists are extremely efficient at adding and removing elements from the beginning of a list, but they aren’t ideal for every situation. For example, random access of list elements is very slow. In addition, if you needed to change the last element of a list, you would need to clone the entire list. (The performance characteristics of lists will be covered more in-depth in Chapter 7.)

When you know ahead of time how many items you will need in your collection and would like to be able to update any given item, arrays are the ideal type to use.

Arrays in .NET are a contiguous block of memory containing zero or more elements, each of which can be modified individually (unlike lists, which are immutable).

Arrays can be constructed using array comprehensions, which are identical to list comprehensions (discussed in Chapter 2), or manually via a list of values separated by semicolons and enclosed between [| |]:

> // Using the array comprehension syntax
let perfectSquares = [| for i in 1 .. 7 -> i * i |];;

val perfectSquares : int array

> perfectSquares;;
val it : int array = [|1; 4; 9; 16; 25; 36; 49|]

> // Manually declared
let perfectSquares2 = [| 1; 4; 9; 16; 25; 36; 49; 64; 81 |];;

val perfectSquares2 : int array

Indexing an Array

To retrieve an element from the array, you can use an indexer, .[], which is a zero-based index into the array:

> // Indexing an array
printfn
    "The first three perfect squares are %d, %d, and %d"
    perfectSquares.[0]
    perfectSquares.[1]
    perfectSquares.[2];;
The first three perfect squares are 1, 4, and 9
val it : unit = ()

Example 4-5 uses array indexers to change individual characters of a character array to implement a primitive form of encryption known as ROT13. ROT13 works by simply taking each letter and rotating it 13 places forward in the alphabet. This is achieved in the example by converting each letter to an integer, adding 13, and then converting it back to a character.

Example 4-5. ROT13 encryption in F#

open System

// Encrypt a letter using ROT13
let rot13Encrypt (letter : char) =

    // Move the letter forward 13 places in the alphabet (looping around)
    // Otherwise ignore.
    if Char.IsLetter(letter) then
        let newLetter =
            (int letter)
            |> (fun letterIdx -> letterIdx - (int 'A'))
            |> (fun letterIdx -> (letterIdx + 13) % 26)
            |> (fun letterIdx -> letterIdx + (int 'A'))
            |> char
        newLetter
    else
        letter

// Loop through each array element, encrypting each letter
let encryptText (text  : char[]) =

    for idx = 0 to text.Length - 1 do
        let letter = text.[idx]
        text.[idx] <- rot13Encrypt letter

let text =
    Array.ofSeq "THE QUICK BROWN FOX JUMPED OVER THE LAZY DOG"

printfn "Origional = %s" <| new String(text)
encryptText(text)
printfn "Encrypted = %s" <| new String(text)

// A unique trait of ROT13 is that to decrypt, simply encrypt again
encryptText(text)
printfn "Decrypted = %s" <| new String(text)

The output of our simple program is:

Origional = THE QUICK FOX JUMPED OVER THE LAZY DOG
Encrypted = GUR DHVPX SBK WHZCRQ BIRE GUR YNML QBT
Decrypted = THE QUICK FOX JUMPED OVER THE LAZY DOG

Warning

Unlike C# and VB.NET, indexers in F# require using the dot notation. You can think of an indexer, then, as just another method or property:

// Incorrect
x[0]
// Correct
x.[0]

Attempting to access an element in the array with an index either less than zero or greater than or equal to the number of elements in the array will raise an IndexOutOfRangeException exception. (Exceptions will be covered later in this chapter.) Fortunately, arrays have a Length property, which will return the number of items in the array. Because array indexes are zero-based, you need to subtract 1 from Length to get the index of the last element in the array:

> let alphabet = [| 'a' .. 'z' |];;

val alphabet : char array

> // First letter
alphabet.[0];;

val it : char = 'a'
> // Last leter
alphabet.[alphabet.Length - 1];;

val it : char = 'z'
> // Some non-existant letter
alphabet.[10000];;

System.IndexOutOfRangeException: Index was outside the bounds of the array.
   at <StartupCode$FSI_0012>.$FSI_0012._main()
stopped due to error

Array Slices

When you’re analyzing data stored in arrays, it is sometimes convenient to just work with a subset of the data. In F#, there is a special syntax for taking a slice of an array, where you specify optional lower and upper bounds for the subset of data. The syntax for taking a slice is:

array.[lowerBound..upperBound]

If no lower bound is specified, 0 is used. If no upper bound is specified, the length of the array -1 is used. If neither a lower nor upper bound is specified, you can us an * to copy the entire array.

Example 4-6 shows the various ways for taking a slice of an array, but we will break it down line by line shortly.

Example 4-6. Using array slices

open System
let daysOfWeek = Enum.GetNames( typeof<DayOfWeek> )

// Standard array slice, elements 2 through 4
daysOfWeek.[2..4]

// Just specify lower bound, elements 4 to the end
daysOfWeek.[4..]

// Just specify an upper bound, elements 0 to 2
daysOfWeek.[..2]

// Specify no bounds, get all elements (copies the array)
daysOfWeek.[*]

The first way we sliced an array was specifying both an upper and lower bound; this returned all array elements within that range:

> // Standard array slice, elements 2 through 4
daysOfWeek.[2..4];;
val it : string [] = [|"Tuesday"; "Wednesday"; "Thursday"|]

Next we specified just a lower or just an upper bound. This returns each element from the lower bound to the end of the array, or from the beginning of the array to the upper bound:

> // Just specify lower bound, elements 4 to the end
daysOfWeek.[4..];;
val it : string [] = [|"Thursday"; "Friday"; "Saturday"|]

> // Just specify an upper bound, elements 0 to 2
daysOfWeek.[..2];;
val it : string [] = [|"Sunday"; "Monday"; "Tuesday"|]

And finally we just copied the entire array using *. Note that for every slice operation a new array is returned, so there will never be problems with aliasing:

> // Specify no bounds, get all elements (copies the array)
daysOfWeek.[*];;

Creating Arrays

Array comprehensions and manually specifying each element aren’t the only ways to construct arrays. You can also use the Array.init function; Array.init takes a function used to generate each array element based on its index. To create an uninitialized array, use the Array.zeroCreate function. With that function, each element is initialized to its default value: zero or null.

Example 4-7 shows how to use Array.init and Array.zeroCreate to construct arrays.

Example 4-7. Initializing arrays using Array.init

> // Initialize an array of sin-wave elements
let divisions = 4.0
let twoPi = 2.0 * Math.PI;;

val divisions : float = 4.0
val twoPi : float = 6.283185307

> Array.init (int divisions) (fun i -> float i * twoPi / divisions);;
val it : float array = [|0.0; 1.570796327; 3.141592654; 4.71238898|]
> // Construct empty arrays
let emptyIntArray    : int array    = Array.zeroCreate 3
let emptyStringArray : string array = Array.zeroCreate 3;;

val emptyIntArray : int array = [|0; 0; 0|]
val emptyStringArray : string array = [|null; null; null|]

Note

The CLR limits arrays to take up no more than 2GB of memory, even on 64-bit machines. If you need to allocate an array to store a massive amount of data, use a custom data structure instead.

Pattern Matching

Pattern matching against arrays is just as easy as using lists. And just like pattern matching against lists, when matching against arrays, you can capture element values, as well as match against the structure of the array. Example 4-8 shows matching an array value against null or an array with 0, 1, or 2 elements.

Example 4-8. Pattern matching against arrays

> // Describe an array
let describeArray arr =
    match arr with
    | null       -> "The array is null"
    | [| |]      -> "The array is empty"
    | [| x |]    -> sprintf "The array has one element, %A" x
    | [| x; y |] -> sprintf "The array has two elements, %A and %A" x y
    | a -> sprintf "The array had %d elements, %A" a.Length a;;

val describeArray : 'a array -> string

> describeArray [| 1 .. 4 |];;
val it : string = "The array had 4 elements, [|1; 2; 3; 4|]"
> describeArray [| ("tuple", 1, 2, 3) |];;
val it : string = "The array has one element, ("tuple", 1, 2, 3)"

Array Equality

Arrays in F# are compared using structural equality. Two arrays are considered equal if they have the same rank, length, and elements. (Rank is the dimensionality of the array, something we will cover in the next section.)

> [| 1 .. 5 |] = [| 1; 2; 3; 4; 5 |];;
val it : bool = true
> [| 1 .. 3 |] = [| |];;
val it : bool = false

Note

This is different from the behavior of equality on arrays in C#. In F#, the = operator contains special logic for comparing arrays so the default referential equality is not used. For more information on object equality in .NET, refer to Chapter 5.

Array Module Functions

Just like the List and Seq modules, there is an Array module detailed in Table 4-1 that contains nearly identical functions for manipulating arrays.

Table 4-1. Common methods in the Array module

Function

Description

Array.length

'a[] -> int

Returns the length of an array. Arrays already have a Length property as well, but this function is useful for function composition.

Array.init

int -> (int -> 'a) -> 'a[]

Creates a new array with the given number of elements; each element is initialized by the result of the provided function.

Array.zeroCreate

int -> 'a[]

Creates an array with the given length where each entry is the type’s default value.

Array.exists

('a -> bool) -> 'a[] -> bool

Tests if any element in the array satisfies the given function.

partition

Array.partition divides the given array into two new arrays. The first array contains only elements where the provided function returns true; the second array contains elements where the provided function returns false:

> // Simple Boolean function
let isGreaterThanTen x =
    if x > 10
    then true
    else false;;

val isGreaterThanTen : int -> bool

> // Partitioning arrays
[| 5; 5; 6; 20; 1; 3; 7; 11 |]
|> Array.partition isGreaterThanTen;;
val it : int array * int array = ([|20; 11|], [|5; 5; 6; 1; 3; 7|])

tryFind and tryFindIndex

Array.tryFind returns Some of the first element for which the given function returns true. Otherwise, it returns None. Array.tryFindIndex works just like Array.tryFind, except rather than returning the element, it returns its index in the array:

> // Simple Boolean function
let rec isPowerOfTwo x =
    if x = 2 then
        true
    elif x % 2 = 1  (* is odd *) then
        false
    else isPowerOfTwo (x / 2);;

val isPowerOfTwo : int -> bool

> [| 1; 7; 13; 64; 32 |]
|> Array.tryFind isPowerOfTwo;;
val it : int option = Some 64
> [| 1; 7; 13; 64; 32 |]
|> Array.tryFindIndex isPowerOfTwo;;
val it : int option = Some 3

Note

Array.tryFind and Array.tryFindIndex illustrate why the Option type is so powerful. In C#, functions similar to tryFindIndex will return −1 to indicate failure (opposed to None). However, if you are trying to implement tryFind, −1 could indicate either a failure to find an array element or finding an element with value −1.

Aggregate operators

The Array module also contains the aggregate operators of the List module, namely: fold, foldBack, map, and iter. In addition, there are also index-aware versions of these methods. Example 4-9 demonstrates the iteri function, which behaves just like iter except that in addition to the array element, the element’s index is provided as well.

Example 4-9. Using the iteri array aggregate function

> let vowels = [| 'a'; 'e'; 'i'; 'o'; 'u' |];;

val vowels : char array = [|'a'; 'e'; 'i'; 'o'; 'u'|]

> Array.iteri (fun idx chr -> printfn "vowel.[%d] = %c" idx chr) vowels
vowel.[0] = a
vowel.[1] = e
vowel.[2] = i
vowel.[3] = o
vowel.[4] = u
val it : unit = ()

Multidimensional Arrays

Arrays are helpful for storing data in a linear fashion, but what if you need to represent data as a two-, three-, or higher-dimensional grid? You can create multidimensional arrays, which enable you to treat data as a block indexed by several values.

Multidimensional arrays come in two flavors: rectangular and jagged; the difference is illustrated in Figure 4-2. Rectangular arrays are in a solid block, while jagged arrays are essentially arrays of arrays.

Rectangular and jagged arrays

Figure 4-2. Rectangular and jagged arrays

Which type of multidimensional array to use depends on the situation. Using jagged arrays allows you to save memory if each row doesn’t need to be the same length; however, rectangular arrays are more efficient for random access because the elements are stored in a contiguous block of memory. (And therefore can benefit from your processor’s cache.)

Rectangular arrays

Rectangular arrays are rectangular blocks of n by m elements in memory. Rectangular arrays are indicated by rectangular brackets with a comma separating them for each new dimension. Also, just like single-dimensional arrays, there are the Array2D and Array3D modules for creating and initializing rectangular arrays:

> // Creating a 3x3 array
let identityMatrix : float[,] = Array2D.zeroCreate 3 3
identityMatrix.[0,0] <- 1.0
identityMatrix.[1,1] <- 1.0
identityMatrix.[2,2] <- 1.0;;


val identityMatrix : float [,] = <1.0; 0.0; 0.0]
                                  [0.0; 1.0; 0.0]
                                  [0.0; 0.0; 1.0>

2D rectangular arrays can also take slices, using the same syntax but providing a slice for each dimension:

> // All rows for columns with index 1 through 2
identityMatrix.[*, 1..2];;
val it : float [,] = <0.0; 0.0]
                      [1.0; 0.0]
                      [0.0; 1.0>

Jagged arrays

Jagged arrays are simply single-dimensional arrays of single-dimensional arrays. Each row in the main array is a different array, each needing to be initialized separately:

> // Create a jagged array
let jaggedArray : int[][]  = Array.zeroCreate 3
jaggedArray.[0] <- Array.init 1 (fun x -> x)
jaggedArray.[1] <- Array.init 2 (fun x -> x)
jaggedArray.[2] <- Array.init 3 (fun x -> x);;


val jaggedArray : int [] [] = [|[|0|]; [|0; 1|]; [|0; 1; 2|]|]

The best content for your career. Discover unlimited learning on demand for around $1/day.