(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