# Basics 15 - Collections (Basics)

%[https://youtu.be/e65YTC2Hbp8] 

Collections in F# are vastly different from collections available in `System.Collections` or `System.Collections.Generic` namespaces. While you are free to use `System.Collections` or `System.Collections.Generic` collections in F# (just like one does in C#), you will often find yourself moving against functional ideas.

There are five collection types in F#:

1. `array`
    
2. `list`
    
3. `seq`
    
4. `map`
    
5. `set`
    

# Sequences and Sequence Expressions

Sequences in F#, represented by `seq` is `IEnumerable` only. Essentially, anything which is enumerable. `IEnumerable` is often a source of confusion. `IEnumerable` is not a collection, it is an abstraction.

Iterating over an array, a list, a linked list, a dictionary, a hashtable or a binary tree can't be the same. `IEnumerable` provides an abstract way to iterate over various collection types. As a matter of fact, `IEnumerable` is not limited to collections.

## Using Sequence Expressions to Create Sequences

Here are a few examples of how to use sequence expressions to create sequences.

```plaintext
// Sequence 1 to 3
seq { 1..3 } |> printfn "%A" // seq [1; 2; 3]

// Sequence 1 to 7, skip 2
seq { 1..2..7 } |> printfn "%A" // seq [1; 3; 5; 7]

// Loop 1 to 4, i * i for each value of i
seq { for i in 1..4 -> i * i } |> printfn "%A" // seq [1; 4; 9; 16]

// Loop 1 to 7, skip 2, i * i for each value of i
seq { for i in 1..2..7 -> i * i } |> printfn "%A" // seq [1; 9; 25; 49]

// Same as above, alternate mechanism
seq {
    for i in 1..4 do
        yield i * i
}
|> printfn "%A" // seq [1; 4; 9; 16]

// Same as above, alternate mechanism
seq {
    for i in 1..4 do
        i * i
}
|> printfn "%A" // seq [1; 4; 9; 16]

// Nested loop, creating tuple
seq {
    for x in 1..3 do
        for y in 1..3 -> (x, y)
}
|> printfn "%A" // seq [(1, 1); (1, 2); (1, 3); (2, 1); ...]

// Loop and condition
seq {
    for n in 1..10 do
        if n % 2 = 0 then
            n
}
|> printfn "%A" // seq [2; 4; 6; 8; ...]
```

## Iterating over Sequences

Here are a few examples of how to iterate over sequences.

```plaintext
// Sequence of int
let s =   seq { 1..3 }

// Iterate over int values
for i in s do
    printfn "%d" i

// Sequence of tuple
let sTup =
    seq {
        for x in 1..3 do
            for y in 1..3 -> (x, y)
    }

// Patern matching, deconstruction and iteration
for (x, y) in sTup do
    printfn "x: %d, y: %d" x y
```

## Using Sequences as the Abstract Data Type

Sequences are best used as abstract data types.

Here's an example:

```plaintext
type Student =
    { Name: string
      Age: int
      Marks: int array }

let s =
    { Name = "Whatever"
      Age = 10
      Marks = [| 1; 2; 3 |] }
```

The `Student` record type has `Marks` of the type `int array`. This means an instance of `Student` can only be created with an `int array`. What if you have an `int list`?

Now consider this:

```plaintext
type Student =
    { Name: string
      Age: int
      Marks: int seq }

// using int array
let s1 =
    { Name = "Whatever"
      Age = 10
      Marks = [| 1; 2; 3 |] }

// using int list
let s2 =
    { Name = "Whatever"
      Age = 10
      Marks = [ 1; 2; 3 ] }

// using int seq
let s1 =
    { Name = "Whatever"
      Age = 10
      Marks = seq { 1..3 } }
```

With the updated definition of `Student`, `int array`, `int list` and `int seq`, all are allowed.

Similarly, when creating functions, make them generalized. For instance:

`let findMax (numbers: int list) = ...` vs.

`let findMax (numbers: int seq) = ...`

# Arrays

Arrays are fixed-size collections. Indexing is zero-based and arrays allow mutations.

Here are various ways in which arrays can be created:

```plaintext
// Fixed values
let arr1 = [| 1; 2; 3 |]

// expression
let arr2 = [| 1..3 |]

// expression
let arr3 = [| for i in 1..3 -> i |]

// Creates an array with 3 elements, all set to 0
let arr4 = Array.create 3 0

// Value mutation
arr4[0] <- 1
arr4[1] <- 2
arr4[2] <- 3

// Creates an array with 3 elements, all set to 0
let arr5 = Array.zeroCreate 3

// Value mutation
arr5[0] <- 1
arr5[1] <- 2
arr5[2] <- 3

printfn "%A" arr1 // [|1; 2; 3|]
printfn "%A" arr2 // [|1; 2; 3|]
printfn "%A" arr3 // [|1; 2; 3|]
printfn "%A" arr4 // [|1; 2; 3|]
printfn "%A" arr5 // [|1; 2; 3|]
```

How to access array items and iterate over an array:

```plaintext
let arr = [| 1; 2; 3 |]

// access array items
let a = arr[0]
let b = arr[1]
let c = arr[2]

// access array items
let a1 = arr.GetValue 0
let b1 = arr.GetValue 1
let c1 = arr.GetValue 2

// set values
arr[0] <- 5
arr[1] <- 6
arr[2] <- 7

// set values
arr.SetValue(5, 0)
arr.SetValue(6, 1)
arr.SetValue(7, 2)

// prints all array items
for i in arr do
    printfn "%d" i

// iter function invoke function for each item
Array.iter (fun x -> printfn "%d" x) arr // prints all array items
```

# Lists

Lists in F# are immutable collections. Indexing is zero-based.

Here are various ways in which lists can be created:

```plaintext
// Empty list
let list0 = []

// Fixed values
let list1 = [ 1; 2; 3 ]

// expression
let list2 = [ 1..3 ]

// expression
let list3 = [ for i in 1..3 -> i ]

// Add an item in the beginning
// :: aka cons operators
let list4 = 1 :: [ 2; 3 ]

// Contact 2 lists
let list5 = [ 1 ] @ [ 2; 3 ]

// Contact or add at the end
let list6 = [ 1; 2 ] @ [ 3 ]

printfn "%A" list0 // [0]
printfn "%A" list1 // [1; 2; 3]
printfn "%A" list2 // [1; 2; 3]
printfn "%A" list3 // [1; 2; 3]
printfn "%A" list4 // [1; 2; 3]
printfn "%A" list5 // [1; 2; 3]
printfn "%A" list6 // [1; 2; 3]
```

How to access list items and iterate over a list:

```plaintext
let list1 = [ 1; 2; 3 ]

// access list items
let a = list1[0]
let b = list1[1]
let c = list1[2]

// access list items
let a1 = list1.Item 0
let b1 = list1.Item 1
let c1 = list1.Item 2

// prints all list items
for i in list1 do
    printfn "%d" i

// iter function invoke function for each item
List.iter (fun x -> printfn "%d" x) list1 // prints all list items
```

## Pattern Matching, Head and Tail

`Head` refers to the first element of the list, while `Tail` refers to the list after the first element. A list can be pattern matched using `::` (cons operator) into head/tail.

Here is an example:

```plaintext
let l = [ 1; 2; 3 ]

let head = l.Head
let tail = l.Tail

printfn "%A" head // 1
printfn "%A" tail // [2; 3]

// recursive function for finding sum
// may cause stack overflow for a large list
let rec sum list =
    match list with
    | head :: tail -> head + sum tail
    | [] -> 0

// recursive function for finding sum
// no stack overflow, tail recursion
let sumFixed list =
    let rec loop list acc =
        match list with
        | head :: tail -> loop tail (acc + head)
        | [] -> acc
    loop list 0

// recursive function for finding min
// no stack overflow, tail recursion
let min list =
    if List.length list = 0 then
        raise (System.ArgumentException("Empt list provided!"))
    else
        let rec loop list acc =
            match list with
            | head :: tail -> loop tail (if head < acc then head else acc)
            | [] -> acc
        loop list Int32.MaxValue

// recursive function for finding max
// no stack overflow, tail recursion
let max list =
    if List.length list = 0 then
        raise (System.ArgumentException("Empt list provided!"))
    else
        let rec loop list acc =
            match list with
            | head :: tail -> loop tail (if head > acc then head else acc)
            | [] -> acc
        loop list Int32.MinValue

sum l |> printfn "%A" // 6
min l |> printfn "%A" // 1
max l |> printfn "%A" // 3
```

# Sets

Sets in F# are immutable collections. Sets are ordered which are based on binary trees.

Here are various ways in which sets can be created:

```plaintext
// An empty set
let s = Set.empty

printfn "%A" s // set []

// Add 1 to the empty set
let s = s.Add 1

printfn "%A" s // set [1]

// Can't add duplicate value
// Adding 1 again will have no effect
let s = s.Add 1

printfn "%A" s // set [1]

// Adding 2 and 3
let s = s.Add(2).Add(3)

printfn "%A" s // set [1; 2; 3]

// Array to Set
let s = Set.ofArray [| 1; 2; 3 |]

printfn "%A" s // set [1; 2; 3]

// Can't add duplicate value
// Array to Set
let s = Set.ofArray [| 1; 1; 2; 3 |]

printfn "%A" s // set [1; 2; 3]

// List to Set
let s = Set.ofList [ 1; 2; 3 ]

printfn "%A" s // set [1; 2; 3]

// Sequence to Set
let s = Set.ofSeq { 1..3 }

printfn "%A" s // set [1; 2; 3]
```

How to iterate over a set:

```plaintext
let s = Set.ofArray [| 1; 1; 2; 3 |]

// prints all set items
for i in s do
    printfn "%d" i

// iter function invoke function for each item
Set.iter (fun x -> printfn "%d" x) s // prints all set items
```

# Maps

Maps in F# are immutable collections. Maps represent key/value pairs aka dictionaries.

Here are various ways in which maps can be created:

```plaintext
// An empty map
let m = Map.empty

printfn "%A" m // map []

// Add an item (Key, Value)
let m = m.Add(1, "One")

printfn "%A" m // map [(1, "One")]

// Adding with the same key results in value update
let m = m.Add(1, "OneOne")

printfn "%A" m // map [(1, "OneOne")]

// Adding many values
let m = m.Add(1, "One")
let m = m.Add(2, "Two")
let m = m.Add(3, "Three")

printfn "%A" m // map [(1, "One"); (2, "Two"); (3, "Three")]

// Array to Map
let m = Map.ofArray [| (1, "One"); (2, "Two"); (3, "Three") |]

printfn "%A" m // map [(1, "One"); (2, "Two"); (3, "Three")]

// List to Map
let m = Map.ofList [ (1, "One"); (2, "Two"); (3, "Three") ]

// Sequence to Map
printfn "%A" m // map [(1, "One"); (2, "Two"); (3, "Three")]

let m =
    Map.ofSeq (
        seq {
            yield (1, "One")
            yield (2, "Two")
            yield (3, "Three")
        }
    )

printfn "%A" m // map [(1, "One"); (2, "Two"); (3, "Three")]
```

How to access map items and iterate over a map:

```plaintext
let m = Map.ofList [ (1, "One"); (2, "Two"); (3, "Three") ]

let x1 = m[1] // x1 is "One"
let y1 = m[100] // exception... key not found

let x2 = m.TryFind(1) // x2 is Some("One")
let y2 = m.TryFind(100) // y2 is None

let x3 = m.TryGetValue 1 // x3 is (true, "One")
let xy = m.TryGetValue 100 // y3 is (false, )

// prints all map items
// i = KeyValuePair<TypeKey, TypeValue?
for kv in m do
    printfn "Key: %A, Value: %A" kv.Key kv.Value

Map.iter (fun k v -> printfn "Key: %A, Value: %A" k v) m
```

If you have reached so far, congratulations.

Keep reading!