# F Sharp Programming/Arrays

Arrays are a ubiquitous, familiar data structure used to represent a group of related, ordered values. Unlike F# data structures, arrays are mutable, meaning the values in an array can be changed after the array has been created.

## Creating Arrays

Arrays are conceptually similar to lists. Naturally, arrays can be created using many of the same techniques as lists:

### Array comprehensions

F# supports array comprehensions using ranges and generators in the same style and format as list comprehensions:

### System.Array Methods

There are several methods in the System.Array module for creating arrays:
val zeroCreate : int arraySize -> 'T
    Creates an array with arraySize elements. Each element in the array holds the default value for the particular data type (0 for numbers, false for bools, null for reference types).
val create : int -> 'T value -> 'T
    Creates an array with arraySize elements. Initializes each element in the array with value.
val init : int arraySize -> (int index -> 'T) initializer -> 'T
    Creates an array with arraySize elements. Initializes each element in the array with the initializer function.

## Working With Arrays

Elements in an array are accessed by their index, or position in an array. Array indexes always start at 0 and end at array.length - 1. For example, lets take the following array:
This list contains 5 items. The first index is 0, and the last index is 4.
We can access items in the array using the .[index] operator, also called indexer notation. Here is the same array in fsi:
Instances of arrays have a Length property which returns the number of elements in the array:
Arrays are mutable data structures, meaning we can assign elements in an array new values at any point in our program:
If you try to access an element outside the range of an array, you'll get an exception:

### Array Slicing

F# supports a few useful operators which allow programmers to return "slices" or subarrays of an array using the .[start..finish] operator, where one of the start and finish arguments may be omitted.
Note that array slices generate a new array, rather than altering the existing array. This requires allocating new memory and copying elements from our source array into our target array. If performance is a high priority, it is generally more efficient to look at parts of an array using a few index adjustments.

### Multi-dimensional Arrays

A multi-dimensional array is literally an array of arrays. Conceptually, it's not any harder to work with these types of arrays than single-dimensional arrays (as shown above). Multi-dimensional arrays come in two forms: rectangular and jagged arrays.

#### Rectangular Arrays

A rectangular array, which may be called a grid or a matrix, is an array of arrays, where all of the inner arrays have the same length. Here is a simple 2x3 rectangular array in fsi:
This array has 2 rows, and each row has 3 columns. To access elements in this array, you use the .[row,col] operator:
Here's a simple program to demonstrate how to use and iterate through multidimensional arrays:
This program outputs the following:
In additional to the Array2D module, F# has an Array3D module to support 3-dimensional arrays as well.
    Note It's possible to create arrays with more than 3 dimensions using the System.Array.CreateInstance method, but it's generally recommended to avoid creating arrays with huge numbers of elements or dimensions, since it is very hard to manage, and also can quickly consume all of the available memory on a machine.

#### Jagged arrays

A jagged array is an array of arrays, except each row in the array does not necessarily need to have the same number of elements:
You use the .[index] operator to access items in the array. Since each element contains another array, it's common to see code that resembles .[row].[col]:
    Note: Notice that the data type of a rectangular array is 'a[,], but the data type of a jagged array is 'a array array. This results because a rectangular array stores data "flat", whereas a jagged array is literally an array of pointers to arrays. Since these two types of arrays are stored differently in memory, F# treats 'a[,] and 'a array array as two different, non-interchangeable data types. As a result, rectangular and jagged arrays have slightly different syntax for element access.
    Rectangular arrays are stored in a slightly more efficient manner and generally perform better than jagged arrays, although there may not be a perceptible difference in most applications. However, it's worth noting performance differences between the two in benchmark tests.

### Using the Array Module

There are two array modules, System.Array and Microsoft.FSharp.Collections.Array, developed by the .NET BCL designers and the creators of F# respectively. Many of the methods and functions in the F# Array module are similar to those in the List module.
val append : 'T first -> 'T second -> 'T
    Returns a new array with elements consisting of the first array followed by the second array.
val choose : ('T item -> 'U option) -> 'T input -> 'U
    Filters and maps an array, returning a new array consisting of all elements which returned Some.
val copy : 'T input -> 'T
    Returns a copy of the input array.
val fill : 'T input -> int start -> int end -> 'T value -> unit
    Assigns value to all the elements between the start and end indexes.
val filter : ('T -> bool) -> 'T -> 'T
    Returns a new array consisting of items filtered out of the input array.
val fold : ('State -> 'T -> 'State) -> 'State -> 'T input -> 'State
    Accumulates left to right over an array.
val foldBack : ('T -> 'State -> 'State) -> 'T input -> 'State -> 'State
    Accumulates right to left over an array.
val iter : ('T -> unit) -> 'T input -> unit
    Applies a function to all of the elements of the input array.
val length : 'T -> int
    Returns the number of items in an array.
val map : ('T -> 'U) -> 'T -> 'U
    Applies a mapping function to each element in the input array to return a new array.
val rev : 'T input -> 'T
    Returns a new array with the items in reverse order.
val sort : 'T -> 'T
    Sorts a copy of an array.
val sortInPlace : 'T -> unit
    Sorts an array in place. Note that the sortInPlace method returns unit, indicating the sortInPlace mutates the original array.
val sortBy : ('T -> 'T -> int) -> 'T -> 'T
    Sorts a copy of an array based on the sorting function.
val sub : 'T -> int start -> int end -> 'T
    Returns a sub array based on the given start and end indexes.

## Differences Between Arrays and Lists

* Lists
** Immutable, allows new lists to share nodes with other lists.
** List literals.
** Pattern matching.
** Supports mapping and folding.
** Linear lookup time.
** No random access to elements, just "forward-only" traversal.
* Arrays
** Array literals.
** Constant lookup time.
** Good spacial locality of reference ensures efficient lookup time.
** Indexes indicate the position of each element relative to others, making arrays ideal for random access.
** Supports mapping and folding.
** Mutability prevents arrays from sharing nodes with other elements in an array.
** Not resizable.

### Representation in Memory

Items in an array are represented in memory as adjacent values in memory. For example, lets say we create the following int array:
    [| 15; 5; 21; 0; 9 |]
Represented in memory, our array resembles something like this:
Each int occupies 4 bytes of memory. Since our array contains 5 elements, the operating systems allocate 20 bytes of memory to hold this array (4 bytes * 5 elements = 20 bytes). The first element in the array occupies memory 100-103, the second element occupies 104-107, and so on.
We know that each element in the array is identified by its index or position in the array. Literally, the index is an offset: since the array starts at memory location 100, and each element in the array occupies a fixed amount of memory, the operating system can know the exact address of each element in memory using the formula:
    Start memory address of element at index n = StartPosition of array + (n * length of data type)
    End memory address of element at index n = Start memory address + length of data type
In layman's terms, this means we can access the nth element of an array in constant time, or in O(1) operations. This is in contrast to lists, where accessing the nth element requires O(n) operations.
With the understanding that elements in an array occupy adjacent memory locations, we can deduce two properties of arrays:
* Creating arrays requires programmers to specify the size of the array up front, otherwise, the operating system won't know how many adjacent memory locations to allocate.
* Arrays are not resizable, because memory locations before the first element or beyond the last element may hold data used by other applications. An array is only "resized" by allocating a new block of memory and copying all of the elements from the old array into the new array.