Every n-th element in a sequence

[countvajhula]

Some of the built-in Racket sequences provide start, end and step args, like (in-vector) and (in-string) (link). There doesn't seem to be an out-of-the-box way to do this with data/collection sequences, or is there?

How about a new interface every that looks something like this:

(define (every cnt seq)
  (if (empty? seq)
      empty-stream
      (let ([head (first seq)]
            [tail (with-handlers
                    ([exn:fail?
                      (λ (exn)
                        empty-stream)])
                    (drop cnt seq))])
        (stream-cons head (every cnt tail)))))

which could be used like:

(take 10 (every 5 (naturals)))
;; evens
(take 10 (every 2 (naturals)))
;; odds
(take 10 (every 2 (naturals 1)))
;; with an offset
(take 10 (every 7 (drop 100 (naturals))))
;; together with subsequence for start, stop, step
(every 3 (subsequence (naturals) 10 20))
;; in vector
(every 3 #(1 2 3 4 5 6 7 8 9 10))

which yield the outputs (converted to list):

'(0 5 10 15 20 25 30 35 40 45)
> 
'(0 2 4 6 8 10 12 14 16 18)
> 
'(1 3 5 7 9 11 13 15 17 19)
> 
'(100 107 114 121 128 135 142 149 156 163)
>
'(10 13 16 19)
>
'(1 4 7 10)

Do you think this would be a worthwhile addition to data/collection? If so, I could put something like it in a PR.

[countvajhula]

Hi @lexi-lambda !

Thanks for making this great library (which I know you've said you aren't actively maintaining). Since I first discovered it -- I assume about the time I opened this issue -- I took to implementing generic versions of common sequence operations whenever I had the need for one. Over time this grew into a sizable collection of general-purpose APIs. I've finally put this up, and I thought I'd mention it to you to see if you might have any thoughts on it:

https://docs.racket-lang.org/seq/index.html

The seq/base module essentially just extends data/collection, building on top of it to provide a number of generic and lazy sequence utilities that are implemented using streams. I also added two additional "layers" -- one called seq/api and the next one above that called seq/iso (for "isomorphic"). The idea is just to provide isomorphic (not in the usual algebraic sense but in the sense of "same form") versions of the APIs, so that the outputs have the same type as the inputs.

In order to do this, it was first necessary to know whether the output was finite to begin with, and that's where the seq/api layer comes in -- this layer simply annotates outputs from the core (seq/base) APIs with finiteness information, for cases where, given the nature of what we know the specific API does, the finiteness of the output is implied by the finiteness of the input. E.g.: (by 3 (range 10)) would be known-finite if (range 10) is known-finite.

Then, at the 'iso' level, if the output is finite, it is coerced back into the input type to provide the isomorphic behavior.

Now, do I like this approach? No, I'm not sure that I do. It feels overly complicated and has involved more manual work to accomplish than I'd like to admit, and I suspect it probably loses some of the benefits that you pointed out in your original talk about this library. It's very likely that having isomorphic behavior means that we lose the performance benefits of using different data structures to begin with (due at least to conversion to streams and back again), and I haven't really given a lot of thought to this. The main (and perhaps only) benefit that the isomorphic interfaces provide is convenience. At worst, these interfaces would be useful in testing scenarios or prototyping, where the behavior of the interfaces is more important than their performance. But another thing to be said for it is perhaps that it reifies a particular design goal -- for generic APIs to also be isomorphic in this manner.

Anyway, just thought I'd run all this by you. Is this all just a senseless waste of time? Is there a much better way? Could we perhaps have a DSL, maybe something like Common Lisp's iterate, that could be both generic as well as isomorphic and even performant?

Btw I think there are discussions going on around generic collections for Rhombus, but I haven't had a chance to keep track of them. It's possible these topics are already being discussed somewhere.

[countvajhula]

@lexi-lambda FYI Introducing Seq: A generic, isomorphic sequence library. Some of the code in seq probably belongs in data/collection (e.g. the changes in set-nth and range and the other overridden interfaces, mostly just finiteness annotation), and I'd love to merge those upstream in some form if you feel that makes sense.