How to solve the ransom note problem functionally

Question

Write a function that given a list of letters what and a word, returns true if the word can be spelt using the letters from the list and false if not. For example a list like

['a';'b';'d';'e';'a']

and the word

bed

the function should return true. If the word was bbed it should also return false because there is only one b in the list.

This is easy enough to do imperatively by mutating the state of the dictionary in a for loop but how can one do it in a more functional style without mutation?

Here's the imperative version I did:

open System.Collections.Generic

let letters = new Dictionary<char,int>()
[ ('a', 2); ('b', 1); ('c', 1); ('e', 1) ] |> Seq.iter letters.Add

let can_spell (word : string) =
    let mutable result = true
    for x in word do
        if letters.ContainsKey x && letters.[x] > 0 then
            let old = letters.[x]
            letters.[x] <- old - 1
        else
            result <- false
    done
    result

Answer 1

You can use 2 dictionaries to keep track of the counts by letter of the word and the existing letters and then check that the letter count is greater than the word letter count:

let contains (word:string)(letters:IDictionary<char,int>) = 
    let w = word
            |>Seq.countBy id
            |>dict

    w.Keys
    |>Seq.map(fun k-> letters.ContainsKey k && letters.[k] >= w.[k])
    |>Seq.reduce(&&)

and you can use it like this

let letters = 
    [ ('a', 2); ('b', 1); ('c', 1); ('e', 1); ('d', 1)] 
    |> dict

contains "bed" letters // True