Functional Adventures in F# - Using Map Collections

Tweet

This time we will look at how we can manipulate Map collections to store data.

This post is part of a series:
Functional Adventures in F# - A simple planner
Functional Adventures in F# - Calling F# from C#
Functional Adventures in F# - Using Map Collections
Functional Adventures in F# - Application State
Functional Adventures in F# - Types with member functions
Functional Adventures in F# - Getting rid of loops
Functional Adventures in F# - Getting rid of temp variables
Functional Adventures in F# - The MailboxProcessor
Functional Adventures in F# - Persisting Application State
Functional Adventures in F# - Adding Snapshot Persisting
Functional Adventures in F# - Type-safe identifiers
Functional Adventures in F# - Event sourcing lessons learned

I am no expert in F#, writing these posts is a way for me to learn and hopefully they can help someone else as well.

Graph of symbols

OK, so I want to create a symbol graph (influenced by some ideas in the book 'Gödel, Escher, Bach: An Eternal Golden Braid', a book I really recommend everyone to read)
This is just a very naive implementation but it raised some issues when dealing with F# in general.
Basic concept is that you have a bunch of symbols and each time they are triggered together with another symbol you either add an edge or increase the edges weight. And when 2 symbols are totally interlinked, they may become a new symbol of their own. But in this example I will just focus on the graph bit.

Defining types with and keyword

For example: In F#, everything that you use need to be defined before you use them. Meaning that if you have type X that references type Y, and then type Y reference type X.. You have a problem.

type X = { name:string; hits:int; outgoingEdges:Y}
type Y = { target:X; hits:int;  }

This would result in a "The type 'Y' is not defined." error. To solve it, we can change the second type definition to use the keyword and instead of type.

type X = { name:string; hits:int; outgoingEdges:Y}
and Y = { target:X; hits:int;  }

Lets start with defining some types.

module Symbolism =
    type Edge = { targetName:string; hits:int;  }
    type Symbol = { name:string; hits:int; outgoingEdges:Edges}
    and Edges = Map<string, Edge>
    type Symbols = Map<string, Symbol>

So here we see the usage of the and keyword as Symbol forward references Edges.

Using Map Collections

As you can see above, we have defined Edges and Symbols to be of the type Map, basically Map works like a Dictionary in C#, there are probably differences (other then the immutability part), but for my purposes I like to think that they are about the same. They both store objects as Key/Value pairs.

So, our first function will be getSymbol that takes a Symbols collection and the name of the symbol to get. Here I want to return the symbol from the Map if it exists, otherwise return a new empty symbol that has never been seen before. For this we will use pattern matching mechanism of F#, the task is quite trivial and thus a straight forward place to figure out how pattern matching works.

let getSymbol (symbols:Symbols) (key:string) =
    match symbols.ContainsKey key with
    | true -> symbols.[key]
    | _ -> { name = key; hits = 0; outgoingEdges = Map.empty }

We start by checking if they Symbols Map contains the key with the match [expression] with part.
The next line we define what happens if the result is true. We return the object that is in the Map, notice the dot (.) before the indexer. In C# you would access a dictionary as 'symbols[key]' but in F# you need the extra dot.
The second pattern line means, anything else.... So in this case it would be if the result is false we return a brand new record. The outgoingEdges is of the type Edges that is a Map<string, Edge>. I spent some time trying to initialize it with Edges.empty until I figured out that it is the Map.empty that should be used to initialize an empty map of any type.

Next, we want to add or update a value in the Map.

let addEdgeToSymbol (symbol:Symbol) (target:Symbol) = 
    let edge = getEdge symbol target
    let weightedEdge = increaseEdgeWeigth edge
    let updatedSymbol:Symbol = { symbol with outgoingEdges = symbol.outgoingEdges.Add(target.name, weightedEdge) }
    updatedSymbol

This took me a while as well. Trying to google how to update a value in a Map collection. Evidently it is built into the Add function.
If the key does not exist in the Map: a new Map with the key/value pair added to it is returned
If the key exists already in the Map: a new Map with the value in the key location updated is returned.
Pretty neat to not have to bloat the code with all the checks just to add or update, just call the Add function.
Here also, we want to update one field in the symbol record. We could define a new record and manually copy all the fields but that is just code debt waiting to blow. Instead there is a nice way to do this with the following line.

{ symbol with outgoingEdges = symbol.outgoingEdges.Add(target.name, weightedEdge) }

Here we say, that we want a new record based on the values in the record 'symbol' but with the following things updated. In this case the outgoingEdges field.

Full source code

module Symbolism =
    type Edge = { targetName:string; hits:int;  }
    type Symbol = { name:string; hits:int; outgoingEdges:Edges}
    and Edges = Map<string, Edge>
    type Symbols = Map<string, Symbol>
        
    let getSymbol (symbols:Symbols) (key:string) =
        match symbols.ContainsKey key with
        | true -> symbols.[key]
        | _ -> { name = key; hits = 0; outgoingEdges = Map.empty }
    
    let getEdge (symbol:Symbol) (target:Symbol) = 
        match symbol.outgoingEdges.ContainsKey target.name with
        | true -> symbol.outgoingEdges.[target.name]
        | _ -> { targetName = target.name; hits = 0; }

    let increasSymboleWeigth symbol:Symbol =
        let updatedSymbol:Symbol = { symbol with hits = symbol.hits + 1 }
        updatedSymbol

    let increaseEdgeWeigth edge:Edge =
        let updatedEdge:Edge = { edge with hits = edge.hits + 1 }
        updatedEdge
        
    let addEdgeToSymbol (symbol:Symbol) (target:Symbol) = 
        let edge = getEdge symbol target
        let weightedEdge = increaseEdgeWeigth edge
        let updatedSymbol:Symbol = { symbol with outgoingEdges = symbol.outgoingEdges.Add(target.name, weightedEdge) }
        updatedSymbol

    let addEdge (symbols:Symbols) (from:string) (target:string) = 
        let symbol = getSymbol symbols from
        let targetSymbol = getSymbol symbols target
        let edgedSymbol = addEdgeToSymbol symbol targetSymbol
        let weightedSymbol = increasSymboleWeigth edgedSymbol
        let weightedTargetSymbol = increasSymboleWeigth targetSymbol
        symbols
            .Add(from, weightedSymbol)
            .Add(target, weightedTargetSymbol)

Unit tests

[<TestClass>]
type SymbolismTest () =

    [<TestMethod>]
    member this.Symbolism_getSymbol_NoExistingSymbols () =
        let target : Symbols = Map.empty
        let actual = getSymbol target "ewan mcgregor"
        Assert.AreEqual("ewan mcgregor", actual.name)
        Assert.AreEqual(0, actual.outgoingEdges.Count)
  
  
    [<TestMethod>]
    member this.Symbolism_getSymbol_ExistingSymbol () =
        let target : Symbols = Map.empty.Add("ewan mcgregor", { name = "test item"; hits = 0; outgoingEdges = Map.empty })
        let actual = getSymbol target "ewan mcgregor"
        Assert.AreEqual("test item", actual.name)
        Assert.AreEqual(0, actual.outgoingEdges.Count)
        
    [<TestMethod>]
    member this.Symbolism_addEdgeToSymbol () =
        let from = { name = "daisy ridley"; hits = 0; outgoingEdges = Map.empty }
        let target = { name = "star wars"; hits = 0; outgoingEdges = Map.empty }
        let actual = addEdgeToSymbol from target
        Assert.AreEqual("daisy ridley", actual.name)
        Assert.AreEqual(1, actual.outgoingEdges.Count)
        Assert.IsTrue(actual.outgoingEdges.ContainsKey("star wars"))
        Assert.AreEqual(1, actual.outgoingEdges.["star wars"].hits)
        
    [<TestMethod>]
    member this.Symbolism_addEdge_NoExistingSymbols () =
        let target : Symbols = Map.empty
        let symbols = addEdge target "ewan mcgregor" "star wars"
        let actualewan = getSymbol symbols "ewan mcgregor"
        let actualStarWars = getSymbol symbols "star wars"
        Assert.AreEqual("ewan mcgregor", actualewan.name)
        Assert.AreEqual(1, actualewan.hits)
        Assert.AreEqual(1, actualewan.outgoingEdges.Count)
        Assert.AreEqual("star wars", actualStarWars.name)
        Assert.AreEqual(1, actualStarWars.hits)
        Assert.AreEqual(0, actualStarWars.outgoingEdges.Count)
        Assert.AreEqual(2, symbols.Count)

Here in the Symbolism_getSymbol_ExistingSymbol test we can see how to initialize a Map with a starting key value. I.e. by adding an item to an empty Map.

Merging 2 Map collections

Added 2018-03-21, did not want to create a new post for this.
At some point you may come across a problem that needs to be solved by merging 2 different Map collections that have the same type if Key and Value. To use this, we will use Map.fold to create a new Map collection that has the contents of both input Maps

let newUnits = Map.fold (fun acc key value -> Map.add key value acc) state.Units builtUnits

So there it is. We have gone through how to

• Check if a key exists in a Map
• Retrieve the value stored in the Map for a particular key
• Add values to a Map
• Update values in a Map
• Initialize an empty Map
• Initialize a Map with key/value pairs from the start
• Merge 2 Map collections

All code provided as-is. This is copied from my own code-base, May need some additional programming to work. Use for whatever you want, how you want! If you find this helpful, please leave a comment or share a link, not required but appreciated! :)

Hope this helps someone out there!