F# program to generate a Map of substrings frequencies

Question

I wrote the following F# program that takes an input txt file and create a Map that contains all possible substrings of size N and their frequency in the file.

In other words if I call the program with a text file with the following content:

James John Max Gary Jess Gilles Mary

With a length of 2, the probabilityTable contains a value with a key of "ar" with a value of 0.054054.

Here is the program:

module NameGenerator

open System
open System.Collections.Generic

// Open a file and read all lines into IEnumerable<string>
let readInputFile (filePath:string) = 
    System.IO.File.ReadAllText(filePath)

// Parses a string and count the total number of occurrences of substrings of size length
let rec countOccurrences (input:string) (occurrenceTable:Map<string, float>) length = 
    let adjLen = length - 1

    match input |> Seq.toList with
    | head :: tail when tail.Length >= adjLen -> 
        let other = Seq.take adjLen tail |> Seq.toList
        let occurrence = (head :: other |> Array.ofList |> String)

        // add current occurrence to the occurrence table
        let updatedMap = match occurrenceTable.ContainsKey (occurrence) with
                         | true -> occurrenceTable.Add(occurrence, occurrenceTable.[occurrence] + 1.0)
                         | false -> occurrenceTable.Add(occurrence, 1.0)

        // call the function recursively with the rest of the string
        countOccurrences (tail |> Array.ofList |> String) updatedMap length
    | _ -> occurrenceTable

// Given a map that contains the a collection of string and their respective counts, return a
// frequency map that is obtained by count / total count
let buildFrenquencyTable (occurrenceTable:Map<string, float>) =
    // fold occurence dict, count total
    let total = Map.fold (fun acc key value -> acc + value) 0.0 occurrenceTable

    // map over previous map and replace values with count / total count
    Map.map (fun key value -> Math.Round(value / total, 6)) occurrenceTable

// Given an input file create a probability table for the different letters in the file
let buildProbabilityTable (filePath:string) length =
    let input = readInputFile filePath
    let initialDictionary = Map.empty

    countOccurrences input initialDictionary length 
    |> buildFrenquencyTable

I would like a review on how I could do things better and use a more functional style.

Answer 1

Let me also leave some comments.

1.You do not needed to use function readInputFile, because it performs the same thing as System.IO.File.ReadAllText.

2.As you already wrote @Henrik Hansen - better to remove the explicit dependency on file and use the string and further use formula for calculating the total :

let buildProbabilityTable (input : string) length =
    let initialDictionary = Map.empty
    let total = input.Length - length + 1 |> float 
    countOccurrences input initialDictionary length 
    |> Map.map (fun _ value -> Math.Round(value / total, 6)) 

3.In updatedMap you use the occurrenceTable.ContainsKey and then get item by key. Better use Map.tryFind (this will allow you not to specify the type for occurrenceTable):

    let updatedMap = 
        occurrenceTable
        |> Map.tryFind occurrence 
        |> defaultArg <| 0.0
        |> fun x -> occurrenceTable.Add(occurrence, x + 1.0)

If you don't like the defaultArg, you can use the usual pattern matching:

    let updatedMap = 
        occurrenceTable
        |> Map.tryFind occurrence 
        |> function
        | Some x -> occurrenceTable.Add(occurrence, x + 1.0)
        | None -> occurrenceTable.Add(occurrence, 1.0)

Answer 2

Fortunately you're already following the functional idioms entirely. So that's a very good thing.

The only things I would comment on are a few minor details:

---

let occurrence = (head :: other |> Array.ofList |> String)

Those parenthesis are superfluous.

---

let updatedMap = match occurrenceTable.ContainsKey (occurrence) with
                 | true -> occurrenceTable.Add(occurrence, occurrenceTable.[occurrence] + 1.0)
                 | false -> occurrenceTable.Add(occurrence, 1.0)

In this case, you have a lot of whitespace to the left of the match conditions, usually in this case I just break the match to a new line and then work from there.

let updatedMap =
    match occurrenceTable.ContainsKey (occurrence) with
    | true -> occurrenceTable.Add(occurrence, occurrenceTable.[occurrence] + 1.0)
    | false -> occurrenceTable.Add(occurrence, 1.0)

It's generally easier to read.

---

let total = Map.fold (fun acc key value -> acc + value) 0.0 occurrenceTable

I absolutely love to see fold used! I think it's far overlooked and definitely has many use cases.

---

In regards to this method:

let rec countOccurrences (input:string) (occurrenceTable:Map<string, float>) length = 

You nailed tail-call recursion. I would be willing to bet that if you looked at the IL for this code you would see a beautiful tail. call in there. Excellent work!

---

Overall, beautiful work. I think you did a phenomenal job with this code. :)

Answer 3

Nice and clear code - a couple of things though:

The total number of occurences (the sample size) is constant per input string:

(float (input.Length - length + 1))

because you do not filter anything out, so the let total = Map.fold... isn't necessary.

I wouldn't feed buildProbabilityTable with a file path but with the actual input data and load the file elsewhere, making it more flexible.

Because you know the total number in advance you could actually do everything in one single Seq.fold call on the input string without recursion - but maybe your focus was on recursion rather than anything else?

A detail: when I run your code on the names string I get ar: 0.057143?