Clojure: Modifying a List of Vectors based on Previous Iteration Value

(EDIT: Looks like I muffed the title of this one but I'm going to leave it as is. Should read "Vector of Maps".)

Here's an interesting problem I've been pondering this morning. What is a good functional approach to solving a problem in which you have to iterate through a vector of maps and copy a value from a previous item if the value is nil in the current one?

Problem Statement

This is something that came up while trying to parse output from Cisco Nexus show ip bgp regex....

*|e172.16.1.1/32      192.168.1.1                                    0 65535 i
*>e                   192.168.255.255                                0 65535 i

And this results in a map that looks like the value of c here:

(def c [{:next-hop "192.168.1.1", :prefix "172.16.1.1/32", :route-status "*|e"}
        {:next-hop "192.168.255.255", :prefix nil, :route-status "*>e"}])

The goal of this code is to carry-over the value of the last seen prefix value to all subsequent values that have nil prefixes. In the nature of the output, the last-seen prefix value may not be from the iteration immediately before.

The return of our code is expected to look like this:

[{:next-hop "192.168.1.1", :prefix "172.16.1.1/32", :route-status "*|e"}
 {:next-hop "192.168.255.255", :prefix "172.16.1.1/32", :route-status "*>e"}]

Approaches

My initial approach was to initiate an atom in a let-binding for the carry-over value and to use map.

; map with atom
(let [prev (atom nil)]
  (map (fn [r]
         (if (and @prev (not (:prefix r)))
           (assoc r :prefix @prev)
           (do (reset! prev (:prefix r))
               r)))
       c))

Carrying over a value in a mutable atom isn't a very functional way of dealing with the problem so here are a couple more approaches I came up with.

The next approach uses reduce in which each iteration returns a compound accumulator as [<previous value> <accumulating vector>]:

; reduce with compound accumulator
(second
  (reduce
    (fn [[prev acc] v]
      (if (and prev (not (:prefix v)))
        [prev (conj acc (assoc v :prefix prev))]
        [(:prefix v) (conj acc v)]))
    [nil []]
    c))

What I like about this approach is it's very clear about what's going into the next iteration. There isn't any mutable state. What I don't like is having to deal with the compound accumulator and having to unpack the result of the reduce using second.

My final approach uses loop/recur:

; loop/recur
(loop [prev nil
       acc []
       coll c]
  (if-let [v (first coll)]
    (if (and prev (not (:prefix v)))
      (recur prev (conj acc (assoc v :prefix prev)) (rest coll))
      (recur (:prefix v) (conj acc v) (rest coll)))
    acc))

When I first looked at this I thought it was a bit awkward but it's growing on me. The loop's base case is when there are no more items in coll - return the accumulated result. And the recursing code will either update prev or append a modified value.

One might think that this approach may suffer from limits on stack depth but as I understand it, loop/recur has some special handling which makes it not a problem.

Github Gist

https://gist.github.com/francisluong/967b5528e4cd64e2d6a34553c677f5cd

Clojure and Values (vs. Places)

I let my workmate craigy talk me into checking out Clojure. This is also partly because of all of the love Paul Graham heaps on Lisp in his writing.

I have been kicking tires using vim and lein repl for the past couple days but this morning I decided to take it to the next level.

I finally watched Rich Hickey's Keynote: The Value of Values. This doesn't help with Clojure directly but it really helps to get clear on what a value is and what it isn't and why you want your software to work with values. Really worth a watch and it will challenge the way you look at code and data.

After watching this video, I set about trying to get a decent dev environment setup so that I can experiment with the code without having to repaste into a REPL. For me, the best way is to get a solid IDE setup and use unit tests for the tire kicking. RubyMine has been really good for me, and I decided to use IntelliJ CE with the Cursive plugin. There's still a good bit of configuring you need to do and it doesn't fully feel native but it was better than my feeble attempts at using Eclipse.

Thank you to JetBrains and Ideogram for making non-commercial versions available.

References