Expanding a map into an infinite sequence

Question

I have a map that I want to 'expand' into an infinite sequence in the following manner:

{0 'zero 3 'three 10 'ten}
=>
('zero 'zero 'zero 'three 'three 'three 'three 'three 'three 'three 'ten 'ten 'ten ...)

The indexes of the map indicating the index of the sequence where the value should change.

The following code works, but it does not please me. Can this be written in a smarter way?

(defn expand-map
 [m]
 (letfn [(em
 [last-value indexes]
 (let [value (m (first indexes))]
 (if value
 (lazy-seq (cons value (em value (rest indexes))))
 (lazy-seq (cons last-value (em last-value (rest indexes)))))))]
 (em 'zero (iterate inc 0))))
(take 20 (expand-map {0 'zero 3 'three 10 'ten}))

• andrew cooke: oh, you want 'zero from 0th, then 'three from third, then 'ten from tenth?
• GHZ: yes, another example would be {0 0 1 1 3 3} => (0 1 1 3 3 3 ...)

Answer 1

It really depends on your specific goals. The code as it is is very lazy, but also recomputes quite a lot by accessing the map on every single step.

(iterate inc 0) can be more easily written as (range) as noted again below and the definition of expand-map is partially repetitive ((lazy-seq (cons ...)) comes up twice, as does (rest indexes) - generally it's better to keep the amount of duplicate code to a minimum.

The 'zero initial value is hardcoded, which is not that nice for a general solution, but apart from that it looks okay.

---

I have two other rewritten options below with different degrees of laziness and verboseness.

For both options I suggest a different way of iterating over the keys, that is, getting and sorting the keys of the input map once, then reusing it instead of looking up the current index that often.

Thus, option one, lazier then the other one, using repeat to create the sub-list with the indicated value, then concatenating it with the remainder.

Also, since it's not indicated what should happen on an empty map (except the presented code defaulting to 'zero); that could be indicated a bit nicer as well, by throwing a custom error perhaps.

(defn expand-map-2 [m]
 (letfn [(aux [indexes]
 (let [index (first indexes)
 rest (next indexes)
 value (m index)]
 (if rest
 (lazy-cat (repeat (- (first rest) index) value) (aux rest))
 (repeat value))))]
 (aux (sort (or (keys m) (throw (Exception. "No specification supplied.")))))))

The other way, less lazy, but IMO a bit nicer assuming your input map isn't huge, is to precompute all lazy lists and concatenate them. Also uses the mapcat over two shifted maps. The (concat (rest keys) [nil]) seems necessary since mapcat terminates early instead of till all the collections are exhausted.

(defn expand-map-3 [m]
 (let [keys (sort (or (keys m) (throw (Exception. "No specification supplied."))))]
 (mapcat (fn [first second]
 (let [value (m first)]
 (if second (repeat (- second first) value) (repeat value))))
 keys (concat (rest keys) [nil]))))

---

Since this post was migrated, there are actually a number of existing solutions here. I've already asked for one of them and got the go-ahead to incorporate it with an explanation of the solution.

Courtesy of @amalloy:

(defn expand-map-4 [m]
 (rest (reductions (fn [prev idx]
 (get m idx prev))
 'zero
 (range))))

Benchmarked this solution seems very similar to the above ones (and the initial code), but is much more concise. range will generate the the infinite list instead of (iterate inc 0), so that is already nice. reductions will return all intermediate results will reducing with the provided function; since we start from 'zero here, this works similarly to the code in the question (I'd rather replace this with similar behaviour to what I posted above, since it doesn't rely on the hard-coded 'zero though). get is used instead of using the map directly, but that's not actually necessary. The first rest is used to discard the spurious initial value (the supplied 'zero).

With those remarks in mind, I'd suggest this amended version:

(defn expand-map-5 [m]
 (let [keys (or (keys m)
 (throw (Exception. "No specification supplied.")))]
 (rest (reductions (fn [prev idx]
 (m idx prev))
 (m (first (sort keys)))
 (range)))))