2
\$\begingroup\$

For a genetic algorithm I'm writing, I need to sub-sequence a list, but I need it to be lazy so I can compose it with other lazy functions. If I introduce strictness into the chain, I risk potentially massive slow-downs since each step in the chain requires a full traversal of the population.

Amazingly, such a function doesn't appear to built into the core, so I needed to write one:

(defn lsubseq
  "Lazily sub-sequences any iterable collection.
  The left-index is inclusive, while the right is exclusive."
  [coll left-index right-index]
  (map second
    (filter #(<= left-index (first %) (dec right-index))
      (map vector (range) coll))))

I find this to be simultaneously atrocious and beautiful. It works exactly as I expected, so I'm happy with it in that regard.

What I'm not really crazy about is the need to enumerate the collection, only to strip the enumerations before returning. I know it's lazy, so the overhead of this should be minimal, but it still seems like a roundabout of achieving this.

What I want reviews on:

  1. Is there really no built-in for this? This seems like something that I would expect in a standard library.

  2. Are there any improvements that could be made?

\$\endgroup\$
3
\$\begingroup\$

One way to improve:

(defn lsubseq
  [coll left-index right-index]
  (take (- right-index left-index) (drop left-index coll)))

There is also a built-in function - 'subvec' - which should meet your performance objective if your input 'coll' is a vector.

\$\endgroup\$
2
  • \$\begingroup\$ Oh, that is nice. And I was using subvec, but it's strict, so that would mess with the chain of lazy operations I'm using. Thanks. \$\endgroup\$ – Carcigenicate Oct 13 '16 at 17:57
  • \$\begingroup\$ Ha, your version is roughly 8.922x faster than mine. Thanks again! \$\endgroup\$ – Carcigenicate Oct 13 '16 at 18:13
0
\$\begingroup\$

If you're composing a series of transformations on lazy sequences, you might find that expressing them as transducers is faster. For example, we can express @rmcv's answer using the ->> threading macro as ...

(defn lsubseq [left-index right-index coll]
  (->> coll
      (drop left-index)
      (take (- right-index left-index))))

For example,

(lsubseq 3 5 (range 10 20))
;(13 14)

We can mechanically translate this into transducer form as follows:

(defn lsubseq [left-index right-index coll]
  (sequence
    (comp
      (drop left-index)
      (take (- right-index left-index)))
    coll))

This has the same effect, but avoids constructing the intermediate (lazy) sequence.

The transducers are combined using simple functional composition. The more layered your transformation, the more worthwhile the performance gains are likely to be.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.