Expanding a map into an infinite sequence

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}))

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)))))


StackExchange Code Review Q#13982, answer score: 3