Map Collections

If we're doing lookups, then a good data structure for that is a Map collection. A Map is an immutable dictionary of elements. Maps consist of key and value pairs. If you look up the key, you get the value.

If you need to do lookups on a key, maps are much more efficient than trying to do the same thing with a list or array.

Some references.

let exampleMap = Map [("a", "hey"); ("b","ho")]
let exampleMap2 = [(4,"apple"); (10,"pizza")] |> Map

Three equivalent ways to find a key given a value.async

Option 1:

exampleMap["a"]

Option 2:

Map.find "a" exampleMap

Option 3:

exampleMap2 |> Map.find 10

// Comparing performance of list vs. Map lookups.

#time "on"
let isOdd x = if x % 2 = 0 then false else true
let arr = [ for i = 1 to 100_000 do (i, isOdd i) ]
let arrMap = arr |> Map

arr |> List.find (fun (a,b) -> a = 100)

(100, false)

arrMap |> Map.find 101

true

Compare performance to find something at the beginning of an list.

for i = 1 to 100 do 
    arr |> List.find(fun (a,b) -> a = 1_000) |> ignore

for i = 1 to 100 do
    arrMap |> Map.find 1_000 |> ignore

Compare performance to find something that is towards the end of the list.

for i = 1 to 100 do 
    arr |> List.find(fun (a,b) -> a = 99_000) |> ignore

for i = 1 to 100 do
    arrMap |> Map.find 99_000 |> ignore

Question 1

Create a Map collection named mapA from the list [("a",1);("b",2)] where the first thing in the tuple is the key and the second thing is the value.

Use Map.tryFind to retrieve the value for key "a"
Use Map.tryFind to retrieve the value for key "c"

answer

Create Map Collection:

let mapA = Map [("a",1);("b",2)]

Real: 00:00:00.000, CPU: 00:00:00.000, GC gen0: 0, gen1: 0, gen2: 0
val mapA: Map<string,int> = map [("a", 1); ("b", 2)]

let mapA2 = [("a",1);("b",2)] |> Map

Real: 00:00:00.000, CPU: 00:00:00.000, GC gen0: 0, gen1: 0, gen2: 0
val mapA2: Map<string,int> = map [("a", 1); ("b", 2)]

let mapA3 = [("a",1);("b",2)] |> Map.ofList

Real: 00:00:00.000, CPU: 00:00:00.000, GC gen0: 0, gen1: 0, gen2: 0
val mapA3: Map<string,int> = map [("a", 1); ("b", 2)]

Use Map.tryFind to retrieve the value for key "a":

Map.tryFind "a" mapA    // evaluates to Some 1

Real: 00:00:00.000, CPU: 00:00:00.000, GC gen0: 0, gen1: 0, gen2: 0
val it: int option = Some 1

mapA |> Map.tryFind "a" // evaluates to Some 1

Real: 00:00:00.000, CPU: 00:00:00.000, GC gen0: 0, gen1: 0, gen2: 0
val it: int option = Some 1

Use Map.tryFind to retrieve the value for key "c":

Map.tryFind "c" mapA    // evaluates to None

Real: 00:00:00.000, CPU: 00:00:00.000, GC gen0: 0, gen1: 0, gen2: 0
val it: int option = None

mapA |> Map.tryFind "c" // evaluates to None

Real: 00:00:00.000, CPU: 00:00:00.000, GC gen0: 0, gen1: 0, gen2: 0
val it: int option = None

Question 2

Create a Map collection named mapB from the list [(1,"a");(2,"b")] where the first thing in the tuple is the key and the second thing is the value.

Use Map.tryFind to retrieve the value for key 1
Use Map.tryFind to retrieve the value for key 3

answer

let mapB = Map [(1,"a");(2,"b")]
let tryFindMapB1 = Map.tryFind 1 mapB
let tryFindMapB3 =Map.tryFind 3 mapB

Real: 00:00:00.000, CPU: 00:00:00.000, GC gen0: 0, gen1: 0, gen2: 0
val mapB: Map<int,string> = map [(1, "a"); (2, "b")]
val tryFindMapB1: string option = Some "a"
val tryFindMapB3: string option = None

Question 3

Use this list

type StockDays3 = 
    {
        Day: int
        Price: decimal
        Dividend: decimal Option 
    }
let stockDays3 = 
    [ for day = 0 to 5 do 
        let dividend = if day % 2 = 0 then None else Some 1m
        { Day = day
          Price = 100m + decimal day
          Dividend = dividend } ]

Create a Map collection named mapC. The key should be the day field, and the value should be the full StockDays3 record.
Create a Map collection named mapD. The key should be the full StockDay3 record. The value should be the day field.

answer

let mapC =
    stockDays3
    |> List.map(fun day ->
        // we just want to create a tuple of the (key,value).
        // The key and value can be anything.
        day.Day, day)
    |> Map

Real: 00:00:00.000, CPU: 00:00:00.000, GC gen0: 0, gen1: 0, gen2: 0
val mapC: Map<int,StockDays3> =
  map
    [(0, { Day = 0
           Price = 100M
           Dividend = None }); (1, { Day = 1
                                     Price = 101M
                                     Dividend = Some 1M });
     (2, { Day = 2
           Price = 102M
           Dividend = None }); (3, { Day = 3
                                     Price = 103M
                                     Dividend = Some 1M });
     (4, { Day = 4
           Price = 104M
           Dividend = None }); (5, { Day = 5
                                     Price = 105M
                                     Dividend = Some 1M })]

let mapD =
    stockDays3
    |> List.map(fun day ->
        // we just want to create a tuple of the (key,value).
        // The key and value can be anything.
        day, day.Day)
    |> Map

Real: 00:00:00.001, CPU: 00:00:00.000, GC gen0: 0, gen1: 0, gen2: 0
val mapD: Map<StockDays3,int> =
  map
    [({ Day = 0
        Price = 100M
        Dividend = None }, 0); ({ Day = 1
                                  Price = 101M
                                  Dividend = Some 1M }, 1);
     ({ Day = 2
        Price = 102M
        Dividend = None }, 2); ({ Day = 3
                                  Price = 103M
                                  Dividend = Some 1M }, 3);
     ({ Day = 4
        Price = 104M
        Dividend = None }, 4); ({ Day = 5
                                  Price = 105M
                                  Dividend = Some 1M }, 5)]

Question 4

Consider a the following Map collection:

let mapp = [("a", 1); ("d",7)] |> Map.ofList

Write a function named lookFor that takes x: string as an input and looks up the value in mapp. If it finds Some y, print "I found y" to standard output where y is the actual integer found. If it finds None, print "I did not find x" to standard output where x is the actual key that was looked up. Test it by looking up "a","b","c","d"

answer

let lookFor x =
    match Map.tryFind x mapp with
    | Some y -> printfn $"I found {y}"
    | None -> printfn $"I did not find {x}" 

lookFor "a" // I found 1
lookFor "b" // I did not find b
lookFor "c" // I did not find c
lookFor "d" // I found 7

I found 1
I did not find b
I did not find c
I found 7
Real: 00:00:00.000, CPU: 00:00:00.000, GC gen0: 0, gen1: 0, gen2: 0
val lookFor: x: string -> unit
val it: unit = ()

or iterate it we use iter instead of map because the result of iter has type unit, and iter is for when your function has type unit. Basically, unit type means the function did something (in this case, printed to standard output) but it doesn't actually return any output.
You could use map, but then we get unit list which isn't really what we want. We just want to iterate through the list and print to output.

["a"; "b"; "c"; "d"] |> List.iter lookFor

I found 1
I did not find b
I did not find c
I found 7
Real: 00:00:00.000, CPU: 00:00:00.000, GC gen0: 0, gen1: 0, gen2: 0
val it: unit = ()

or loop it

for letter in ["a"; "b"; "c"; "d"] do
    printfn $"{lookFor letter}"

I found 1

I did not find b

I did not find c

I found 7

Real: 00:00:00.000, CPU: 00:00:00.000, GC gen0: 0, gen1: 0, gen2: 0
val it: unit = ()

Joins

For the following questions use this data:

type StockPriceOb =
    { Stock : string 
      Time : int
      Price : int }
type TwoStocksPriceOb =
    { Time : int 
      PriceA : int option 
      PriceB : int option }
let stockA = 
    [{ Stock = "A"; Time = 1; Price = 5}
     { Stock = "A"; Time = 2; Price = 6}]
let stockB =     
    [{ Stock = "B"; Time = 2; Price = 5}
     { Stock = "B"; Time = 3; Price = 4}]

Hint: remember that Map collections are useful for lookups.

Question 1

Create a TwoStocksPriceOb list named tslA that has prices for every observation of stockA. If there is a price for stockB at the same time as stockA, then include the stockB price. Otherwise, the stockB price should be None.

answer

let stockbByTime = 
    stockB 
    |> List.map(fun day -> day.Time, day)
    |> Map
let tslA1 =
    stockA
    |> List.map(fun dayA ->
        let priceB = 
            if stockbByTime.ContainsKey dayA.Time then
                Some stockbByTime[dayA.Time].Price
            else 
                None
        { Time = dayA.Time
          PriceA = Some dayA.Price
          PriceB = priceB } )
// or, just a personal preference if you like the loop or List.map
let tslA2 =
    [ for dayA in stockA do 
        let priceB = 
            if stockbByTime.ContainsKey dayA.Time then
                Some stockbByTime[dayA.Time].Price
            else 
                None
        { Time = dayA.Time
          PriceA = Some dayA.Price
          PriceB = priceB } ]

// or, using Map.tryFind statement
let tslA4 =
    [ for dayA in stockA do
        let priceB =
            match Map.tryFind dayA.Time stockbByTime with
            | Some dayB -> Some dayB.Price
            | None -> None 
        { Time = dayA.Time
          PriceA = Some dayA.Price
          PriceB = priceB } ]

// or, this is the same as tslA4, but using Option.map
let tslA5 =
    [ for dayA in stockA do
        let priceB =
            stockbByTime
            |> Map.tryFind dayA.Time
            |> Option.map (fun x -> x.Price)
        { Time = dayA.Time
          PriceA = Some dayA.Price
          PriceB = priceB } ]



// or, define a function
let tryFindBforA (dayA: StockPriceOb) =
    let priceB =
        match Map.tryFind dayA.Time stockbByTime with
        | Some dayB -> Some dayB.Price
        | None -> None 
    { Time = dayA.Time
      PriceA = Some dayA.Price
      PriceB = priceB } 

// checkit
tryFindBforA stockA.[0]
// do it
let tslA3 = stockA |> List.map tryFindBforA

Real: 00:00:00.001, CPU: 00:00:00.000, GC gen0: 0, gen1: 0, gen2: 0
val stockbByTime: Map<int,StockPriceOb> =
  map [(2, { Stock = "B"
             Time = 2
             Price = 5 }); (3, { Stock = "B"
                                 Time = 3
                                 Price = 4 })]
val tslA1: TwoStocksPriceOb list = [{ Time = 1
                                      PriceA = Some 5
                                      PriceB = None }; { Time = 2
                                                         PriceA = Some 6
                                                         PriceB = Some 5 }]
val tslA2: TwoStocksPriceOb list = [{ Time = 1
                                      PriceA = Some 5
                                      PriceB = None }; { Time = 2
                                                         PriceA = Some 6
                                                         PriceB = Some 5 }]
val tslA4: TwoStocksPriceOb list = [{ Time = 1
                                      PriceA = Some 5
                                      PriceB = None }; { Time = 2
                                                         PriceA = Some 6
                                                         PriceB = Some 5 }]
val tslA5: TwoStocksPriceOb list = [{ Time = 1
                                      PriceA = Some 5
                                      PriceB = None }; { Time = 2
                                                         PriceA = Some 6
                                                         PriceB = Some 5 }]
val tryFindBforA: dayA: StockPriceOb -> TwoStocksPriceOb
val tslA3: TwoStocksPriceOb list = [{ Time = 1
                                      PriceA = Some 5
                                      PriceB = None }; { Time = 2
                                                         PriceA = Some 6
                                                         PriceB = Some 5 }]

Question 2

Create a TwoStocksPriceOb list named tslB that has prices for every observation of stockB. If there is a price for stockA at the same time as stockB, then include the stockA price. Otherwise, the stockA price should be None.

answer

let stockaByTime = 
    stockA 
    |> List.map(fun day -> day.Time, day)
    |> Map
let tslB =
    stockB
    |> List.map(fun dayB ->
        let dayA = Map.tryFind dayB.Time stockaByTime
        match dayA with
        | None -> 
            { Time = dayB.Time
              PriceA = None
              PriceB = Some dayB.Price }
        | Some da -> 
            { Time = dayB.Time
              PriceA = Some da.Price 
              PriceB = Some dayB.Price })

Real: 00:00:00.000, CPU: 00:00:00.000, GC gen0: 0, gen1: 0, gen2: 0
val stockaByTime: Map<int,StockPriceOb> =
  map [(1, { Stock = "A"
             Time = 1
             Price = 5 }); (2, { Stock = "A"
                                 Time = 2
                                 Price = 6 })]
val tslB: TwoStocksPriceOb list = [{ Time = 2
                                     PriceA = Some 6
                                     PriceB = Some 5 }; { Time = 3
                                                          PriceA = None
                                                          PriceB = Some 4 }]

Question 3

Create a TwoStocksPriceOb list named tslC that only includes times when there is a price for both stockA and stockB. The prices for stocks A and B should always be something.

answer

let stockaByTime2 = 
    stockA 
    |> List.map(fun day -> day.Time, day)
    |> Map
let tslC1 =
    stockB
    |> List.choose(fun dayB ->
        let dayA = Map.tryFind dayB.Time stockaByTime2
        match dayA with
        | None -> None
        | Some da -> 
            let output =
                { Time = dayB.Time
                  PriceA = Some da.Price 
                  PriceB = Some dayB.Price }
            Some output)
// or, using set which I know you do not know. But #yolo
let timesA = stockA |> List.map(fun x -> x.Time) |> set
let timesB = stockB |> List.map(fun x -> x.Time) |> set
let timesAandB = Set.intersect timesA timesB
let tslC2 =
    timesAandB
    |> Set.toList
    |> List.map(fun time -> 
        { Time = time 
          PriceA = Some stockaByTime.[time].Price
          PriceB = Some stockbByTime.[time].Price})

Real: 00:00:00.001, CPU: 00:00:00.000, GC gen0: 0, gen1: 0, gen2: 0
val stockaByTime2: Map<int,StockPriceOb> =
  map [(1, { Stock = "A"
             Time = 1
             Price = 5 }); (2, { Stock = "A"
                                 Time = 2
                                 Price = 6 })]
val tslC1: TwoStocksPriceOb list = [{ Time = 2
                                      PriceA = Some 6
                                      PriceB = Some 5 }]
val timesA: Set<int> = set [1; 2]
val timesB: Set<int> = set [2; 3]
val timesAandB: Set<int> = set [2]
val tslC2: TwoStocksPriceOb list = [{ Time = 2
                                      PriceA = Some 6
                                      PriceB = Some 5 }]

Question 4

Create a TwoStocksPriceOb list named tslD that includes available stock prices for stockA and stockB at all possible times. If a price for one of the stocks is missing for a given time, it should be None.

answer

let stockATimes = stockA |> List.map(fun x -> x.Time)
let stockBTimes = stockB |> List.map(fun x -> x.Time)
let allTimes = 
    List.append stockATimes stockBTimes
    |> List.distinct
let tslD =
    allTimes
    |> List.map(fun time ->
        let a = 
            match Map.tryFind time stockaByTime with
            | None -> None
            | Some a -> Some a.Price
            
        let b = 
            // same thing as what's done above with match expression,
            // but with Option.map. Personal preference depending
            // on what seems clearest. If you're mapping an option
            // and returning None for the None case,
            // a Option.map can be nice.
            Map.tryFind time stockbByTime
            |> Option.map (fun b -> b.Price)
        { Time = time; PriceA = a; PriceB = b }) 

// or, using a function. This is the same thing as in the above
// anonymous function that begins with `(fun time -> `, 
// but I'm going to use different 
// code to achieve the same goal just to show you different options.
// again, it's just personal preference.
// check how to write the function using time = 1 as a test
let testTime = 1
let time1A = Map.tryFind testTime stockaByTime
let time1B = Map.tryFind testTime stockbByTime
let time1Aprice = time1A |> Option.map(fun x -> x.Price )
let time1Bprice = time1B |> Option.map(fun x -> x.Price)
let testOutput = { Time = testTime; PriceA = time1Aprice; PriceB = time1Bprice }
// now turn above code into a function to do the same thing
let getTheMatch time =
    let a = Map.tryFind time stockaByTime
    let b = Map.tryFind time stockbByTime
    let aPrice = a |> Option.map(fun x -> x.Price)
    let bPrice = b |> Option.map(fun x -> x.Price)
    { Time = time; PriceA = aPrice; PriceB = bPrice }
// test it to see that it works
getTheMatch 1
getTheMatch 2
// now do it for the whole list
let tslD2 = allTimes |> List.map getTheMatch

Real: 00:00:00.000, CPU: 00:00:00.000, GC gen0: 0, gen1: 0, gen2: 0
val stockATimes: int list = [1; 2]
val stockBTimes: int list = [2; 3]
val allTimes: int list = [1; 2; 3]
val tslD: TwoStocksPriceOb list =
  [{ Time = 1
     PriceA = Some 5
     PriceB = None }; { Time = 2
                        PriceA = Some 6
                        PriceB = Some 5 }; { Time = 3
                                             PriceA = None
                                             PriceB = Some 4 }]
val testTime: int = 1
val time1A: StockPriceOb option = Some { Stock = "A"
                                         Time = 1
                                         Price = 5 }
val time1B: StockPriceOb option = None
val time1Aprice: int option = Some 5
val time1Bprice: int option = None
val testOutput: TwoStocksPriceOb = { Time = 1
                                     PriceA = Some 5
                                     PriceB = None }
val getTheMatch: time: int -> TwoStocksPriceOb
val tslD2: TwoStocksPriceOb list =
  [{ Time = 1
     PriceA = Some 5
     PriceB = None }; { Time = 2
                        PriceA = Some 6
                        PriceB = Some 5 }; { Time = 3
                                             PriceA = None
                                             PriceB = Some 4 }]

val exampleMap: Map<string,string>

Multiple items
module Map from Microsoft.FSharp.Collections

--------------------
type Map<'Key,'Value (requires comparison)> = interface IReadOnlyDictionary<'Key,'Value> interface IReadOnlyCollection<KeyValuePair<'Key,'Value>> interface IEnumerable interface IStructuralEquatable interface IComparable interface IEnumerable<KeyValuePair<'Key,'Value>> interface ICollection<KeyValuePair<'Key,'Value>> interface IDictionary<'Key,'Value> new: elements: ('Key * 'Value) seq -> Map<'Key,'Value> member Add: key: 'Key * value: 'Value -> Map<'Key,'Value> ...

--------------------
new: elements: ('Key * 'Value) seq -> Map<'Key,'Value>

val exampleMap2: Map<int,string>

val find: key: 'Key -> table: Map<'Key,'T> -> 'T (requires comparison)

val isOdd: x: int -> bool

val x: int

val arr: (int * bool) list

val i: int

val arrMap: Map<int,bool>

Multiple items
module List from Microsoft.FSharp.Collections

--------------------
type List<'T> = | op_Nil | op_ColonColon of Head: 'T * Tail: 'T list interface IReadOnlyList<'T> interface IReadOnlyCollection<'T> interface IEnumerable interface IEnumerable<'T> member GetReverseIndex: rank: int * offset: int -> int member GetSlice: startIndex: int option * endIndex: int option -> 'T list static member Cons: head: 'T * tail: 'T list -> 'T list member Head: 'T member IsEmpty: bool member Item: index: int -> 'T with get ...

val find: predicate: ('T -> bool) -> list: 'T list -> 'T

val a: int

val b: bool

val ignore: value: 'T -> unit

val mapA: Map<string,int>

val mapA2: Map<string,int>

val mapA3: Map<string,int>

val ofList: elements: ('Key * 'T) list -> Map<'Key,'T> (requires comparison)

val tryFind: key: 'Key -> table: Map<'Key,'T> -> 'T option (requires comparison)

val mapB: Map<int,string>

val tryFindMapB1: string option

val tryFindMapB3: string option

type StockDays3 = { Day: int Price: decimal Dividend: Option<decimal> }

Multiple items
val int: value: 'T -> int (requires member op_Explicit)

--------------------
type int = int32

--------------------
type int<'Measure> = int

Multiple items
val decimal: value: 'T -> decimal (requires member op_Explicit)

--------------------
type decimal = System.Decimal

--------------------
type decimal<'Measure> = decimal

module Option from Microsoft.FSharp.Core

val stockDays3: StockDays3 list

val day: int

val dividend: decimal option

union case Option.None: Option<'T>

union case Option.Some: Value: 'T -> Option<'T>

val mapC: Map<int,StockDays3>

val map: mapping: ('T -> 'U) -> list: 'T list -> 'U list

val day: StockDays3

StockDays3.Day: int

val mapD: Map<StockDays3,int>

val mapp: Map<string,int>

val lookFor: x: string -> unit

val x: string

val y: int

val printfn: format: Printf.TextWriterFormat<'T> -> 'T

val iter: action: ('T -> unit) -> list: 'T list -> unit

val letter: string

type StockPriceOb = { Stock: string Time: int Price: int }

Multiple items
val string: value: 'T -> string

--------------------
type string = System.String

type TwoStocksPriceOb = { Time: int PriceA: int option PriceB: int option }

type 'T option = Option<'T>

val stockA: StockPriceOb list

val stockB: StockPriceOb list

val stockbByTime: Map<int,StockPriceOb>

val day: StockPriceOb

StockPriceOb.Time: int

val tslA1: TwoStocksPriceOb list

val dayA: StockPriceOb

val priceB: int option

member Map.ContainsKey: key: 'Key -> bool

StockPriceOb.Price: int

val tslA2: TwoStocksPriceOb list

val tslA4: TwoStocksPriceOb list

val dayB: StockPriceOb

val tslA5: TwoStocksPriceOb list

val map: mapping: ('T -> 'U) -> option: 'T option -> 'U option

val x: StockPriceOb

val tryFindBforA: dayA: StockPriceOb -> TwoStocksPriceOb

val tslA3: TwoStocksPriceOb list

val stockaByTime: Map<int,StockPriceOb>

val tslB: TwoStocksPriceOb list

val dayA: StockPriceOb option

val da: StockPriceOb

val stockaByTime2: Map<int,StockPriceOb>

val tslC1: TwoStocksPriceOb list

val choose: chooser: ('T -> 'U option) -> list: 'T list -> 'U list

val output: TwoStocksPriceOb

val timesA: Set<int>

val set: elements: 'T seq -> Set<'T> (requires comparison)

val timesB: Set<int>

val timesAandB: Set<int>

Multiple items
module Set from Microsoft.FSharp.Collections

--------------------
type Set<'T (requires comparison)> = interface IReadOnlyCollection<'T> interface IStructuralEquatable interface IComparable interface IEnumerable interface IEnumerable<'T> interface ICollection<'T> new: elements: 'T seq -> Set<'T> member Add: value: 'T -> Set<'T> member Contains: value: 'T -> bool override Equals: obj -> bool ...

--------------------
new: elements: 'T seq -> Set<'T>

val intersect: set1: Set<'T> -> set2: Set<'T> -> Set<'T> (requires comparison)

val tslC2: TwoStocksPriceOb list

val toList: set: Set<'T> -> 'T list (requires comparison)

val time: int

val stockATimes: int list

val stockBTimes: int list

val allTimes: int list

val append: list1: 'T list -> list2: 'T list -> 'T list

val distinct: list: 'T list -> 'T list (requires equality)

val tslD: TwoStocksPriceOb list

val a: int option

val a: StockPriceOb

val b: int option

val b: StockPriceOb

val testTime: int

val time1A: StockPriceOb option

val time1B: StockPriceOb option

val time1Aprice: int option

val time1Bprice: int option

val testOutput: TwoStocksPriceOb

val getTheMatch: time: int -> TwoStocksPriceOb

val a: StockPriceOb option

val b: StockPriceOb option

val aPrice: int option

val bPrice: int option

val tslD2: TwoStocksPriceOb list