CODEWITHSUNDEEP
clojure
Joe
Joe

Reputation: 47619

Map with an accumulator in Clojure?

I want to map over a sequence in order but want to carry an accumulator value forward, like in a reduce.

Example use case: Take a vector and return a running total, each value multiplied by two.

(defn map-with-accumulator
  "Map over input but with an accumulator. func accepts [value accumulator] and returns [new-value new-accumulator]."
  [func accumulator collection]
  (if (empty? collection)
    nil
    (let [[this-value new-accumulator] (func (first collection) accumulator)]
      (cons this-value (map-with-accumulator func new-accumulator (rest collection))))))

(defn double-running-sum
  [value accumulator]
  [(* 2 (+ value accumulator)) (+ value accumulator)])

Which gives

(prn (pr-str (map-with-accumulator double-running-sum 0 [1 2 3 4 5])))

>>> (2 6 12 20 30)

Another example to illustrate the generality, print running sum as stars and the original number. A slightly convoluted example, but demonstrates that I need to keep the running accumulator in the map function:

(defn stars [n] (apply str (take n (repeat \*))))

(defn stars-sum [value accumulator]
  [[(stars (+ value accumulator)) value] (+ value accumulator)])

(prn (pr-str (map-with-accumulator stars-sum 0 [1 2 3 4 5])))
>>> (["*" 1] ["***" 2] ["******" 3] ["**********" 4] ["***************" 5])

This works fine, but I would expect this to be a common pattern, and for some kind of map-with-accumulator to exist in core. Does it?

Upvotes: 3

Views: 1183

Answers (4)

Thumbnail
Thumbnail

Reputation: 13473

The general solution

The common pattern of a mapping that can depend on both an item and the accumulating sum of a sequence is captured by the function

(defn map-sigma [f s] (map f s (sigma s)))

where 

(def sigma (partial reductions +))

... returns the sequence of accumulating sums of a sequence: 

(sigma (repeat 12 1))
; (1 2 3 4 5 6 7 8 9 10 11 12)

(sigma [1 2 3 4 5])
; (1 3 6 10 15)

In the definition of map-sigma, f is a function of two arguments, the item followed by the accumulator.

The examples

In these terms, the first example can be expressed

(map-sigma (fn [_ x] (* 2 x)) [1 2 3 4 5])
; (2 6 12 20 30)

In this case, the mapping function ignores the item and depends only on the accumulator.

The second can be expressed

(map-sigma #(vector (stars %2) %1) [1 2 3 4 5])
; (["*" 1] ["***" 2] ["******" 3] ["**********" 4] ["***************" 5])

... where the mapping function depends on both the item and the accumulator.

There is no standard function like map-sigma.

General conclusions

  • Just because a pattern of computation is common does not imply that it merits or requires its own standard function.
  • Lazy sequences and the sequence library are powerful enough to tease apart many problems into clear function compositions.

Rewritten to be specific to the question posed.

Edited to accommodate the changed second example.

Upvotes: 3

mobyte
mobyte

Reputation: 3752

As mentioned you could use reductions: 

(defn map-with-accumulator [f init-value collection]
  (map first (reductions (fn [[_ accumulator] next-elem]
                           (f next-elem accumulator))
                         (f (first collection) init-value)
                         (rest collection))))

=> (map-with-accumulator double-running-sum 0 [1 2 3 4 5])
(2 6 12 20 30)

=> (map-with-accumulator stars-sum 0 [1 2 3 4 5])
("*" "***" "******" "**********" "***************")

It's only in case you want to keep the original requirements. Otherwise I'd prefer to decompose f into two separate functions and use Thumbnail's approach.

Upvotes: 0

KobbyPemson
KobbyPemson

Reputation: 2539

Reductions is the way to go as Diego mentioned however to your specific problem the following works

(map #(* % (inc %)) [1 2 3 4 5])

Upvotes: 0

Diego Basch
Diego Basch

Reputation: 13079

You should look into reductions. For this specific case:

(reductions #(+ % (* 2 %2)) 2 (range 2 6))

produces

(2 6 12 20 30)

Upvotes: 4

Related Questions