From Imperative to Functional – Transposing Maps

In my recent adventures around Collective Intelligence, I took many code samples that have been written in an imperative coding style and moved them to a more functional style.  With this move sometimes brings some leaps in thinking in which you have to step back and break down the problem into smaller parts and come at it from a different direction.  Today, I’ll go over two examples in which we’re going to transpose a map from an imperative style using mutable dictionaries to one that is written in a functional style with immutable maps.  There is a lot of focus on this blog around immutability and functional composition as they are key to functional programming.

Transposing a Map

This first example comes to us from the Programming Collective Intelligence book which I’ve been covering lately.  In this example, we need to transpose a list which is person centric to become item centric.  For example, let’s say we have the following list:

let critics = 
  Map.of_list [("Lisa Rose", 
                Map.of_list [("You, Me and Dupree", 2.5);("The Night Listener", 3.0)]);
               ("Gene Seymour", 
                Map.of_list [("You, Me and Dupree", 3.5);("The Night Listener", 3.0)])]

Now we want the ability to turn this collection around so that it is item centric, so the movies are the keys in the outer map, with the critics and the ratings in the inner map.  Such a transformation might look like the following:

let items =
  Map.of_list [("You, Me and Dupree",
                Map.of_list [("Lisa Rose", 2.5);("Gene Seymour", 3.5)]);
               ("The Night Listener", 
                Map.of_list [("Lisa Rose", 3.0);("Gene Seymour", 3.0)]);]

Now in order to do this in an imperative coding style should be rather easy.  First we must iterate through all the keys of the outer list, then must iterate through each item in the outer list key’s inner map.  Then we create inner dictionary if required and set the appropriate values given our inversion.  Below is how you would do it using an imperative coding style with F#.

open System.Collections.Generic

// Invert the preferences to be item or person centric
let transformPrefs'
  (prefs:Dictionary<string, Dictionary<string, float>>) =
  
  let result = new Dictionary<string, Dictionary<string, float>>()
  for person in prefs.Keys do
    for item in prefs.[person].Keys do
      if result.[item] = null then
        result.[item] <- new Dictionary<string, float>()
      result.[item].[person] <- prefs.[person].[item]
  result

But to me, this loses a lot of the power of functional programming and F# and using a more non-composable form of programming.  Instead, let’s think about what we’re really doing here.  Many times when we’re looping, we’re accumulating values to return, and this case is no different.  First, we’re going to fold over the outer map, and then fold over the inner map.  But, in order to maintain state, we must feed an accumulated value along to our fold function on both the outer and the inner folds.  Then we can add to our immutable map from the accumulator on both the inner and external maps.  With the internal map, we can add to the existing, if present, else an empty map.

In order to take the arguments with us, let’s introduce a new operator which takes an a tuple pair and a function and executes the function on the untupled arguments.  This will clean up the code significantly for the use of a fold which not only takes a function, but also takes an accumulator and a map to be folded.  Our implementation of our transformPrefs should work out to something like the following:

[<AutoOpen>]
module Operators =
  let (||>) (x, y) f = f x y

// Invert the preferences to be item or person centric
let transformPrefs
  (prefs:Map<string, Map<string, float>>) =
  // Flip item and person
  (Map.empty, prefs) ||> Map.fold_left (fun acc k1 m' -> 
    (acc, m') ||> Map.fold_left (fun acc' k2 v -> 
       acc' |> Map.add k2 (Map.add k1 v (defaultArg (acc' |> Map.tryfind k2) Map.empty))))

If we run this through our F# interactive, we’ll find accomplishes the transpose rather efficiently.  I’ll revisit this post in the next installment of Collective Intelligence and Functional Programming on how to calculate how similar items are to one another.

Transpose and Combine

But, what if we want to not only transpose, but combine in such a way that we build a complete matrix?  For example, Chris Smith of the F# team, recently wrote a post on his blog “F# and the PFX Round 1” in which he builds a matrix of cities and distances so that he can the use the Shortest Path Problem to then decide which path to take when traveling cross-country.

I won’t completely reproduce the code, instead, highlight some changes I made as part of this.  As we note, we have some cities and then come distances between them.  We want the ability to transpose and combine them together so we have a complete picture from both cities about the distance between them.  The code is remarkably similar to the above solution, with changing just the initial accumulator to be the existing first map and voila, we get instant code reuse from our above solution.  Below is the code to do that.

#light

[<AutoOpen>]
module Operators =
  let (||>) (x, y) f = f x y

module Map =
  let transposeCombine m =
    (m, m) ||> Map.fold_left (fun acc k1 m' ->
      (acc, m') ||> Map.fold_left (fun acc' k2 v ->
        acc'
        |> Map.add k2 (Map.add k1 v (defaultArg (acc' |> Map.tryfind k2) Map.empty))
    ))

type City = 
    | Boise     | LosAngeles    | NewYork   | Seattle
    | StLouis   | Phoenix       | Boston    | Chicago   
    | Denver
    
let distTweenCities = 
  Map.of_list
    [
        (Boise, Map.of_list [(Seattle, 496);(Denver,  830);(Chicago, 1702)]);    
        (Seattle, Map.of_list [(LosAngeles, 1141);(Denver,  1321)]);     
        (LosAngeles, Map.of_list [(Denver,  1022);(Phoenix, 371)]);  
        (Phoenix, Map.of_list [(Denver,  809);(StLouis, 1504)]);      
        (Denver,  Map.of_list [(StLouis, 588);(Chicago, 1009)]);     
        (Chicago, Map.of_list [(NewYork, 811);(Boston,  986)]);      
        (StLouis, Map.of_list [(Chicago, 300)]);
        (Boston, Map.of_list [(StLouis,  986)]);      
        (NewYork, Map.of_list [(Boston,  211)])
    ]
    |> Map.transposeCombine

Alternatively, we could have kept the code the same with the empty accumulator and added an additional add statement to our inner left fold.  I’ll revisit this topic later as I get into other parts of this great post which fascinate me such as the Shortest Path Problem, which such algorithms as Dijkstra’s Algorithm, A* and so on.

Conclusion

Going from an imperative mindset to a more functional mindset is not always easy for some people.  Instead, thinking functionally while using immutable data structures gets us to break down our problems into the smallest composable parts.  In these examples, we saw realizing that our loops were nothing more than accumulators, we can then utilize folds to accomplish that very same task.  What this also allows us to do with folds is use immutable data structures which allows for better composition, because we’re not worried on whether the original value changed or not.  Instead, we focus on the evolution of the data as it passes through our functions.

No Comments