Clojure lazy-sequence where sequence grows from both ends

1
votes

I have written a function (listed below) which returns a function that returns n items from an infiniate set as defined in the comments.

; Returns a function which in turn returns a vector of 'n' items, with init-val being the 'middle' value,
; Values to the 'right' of init-val being 'step' added to the (previously) last value, and items 'left' of
; 'init-val' being 'step' subtracted from the (previously) first value in the list. 
(defn range-right-left [init-val step] 
(fn [n] ; produce a vector containing 'n' items
    (loop [Vector (cond (zero? n) [] 
                (pos? n)  [init-val] 
                :else  nil)]
        (if (or (= (count Vector) n) (nil? Vector)) Vector ; base case(s)
            (recur
                (if (odd? (count Vector))
                    (conj Vector (+ (last Vector) step)) ; add 'step' to the last element of the vector and place it on the back of the vector 
                    (vec (cons (- (first Vector) step) Vector)))))))) ;else if Vector contains an even number of items, subtract step from the first item in the vector and place it on front of the resulting collection (converting to vector)

To clarify the behavior of the function, I am including the code for the tests (which all passed).

(deftest range-right-left-test
    (is (= nil ((range-right-left 7 3) -1)))
    (is (= [] ((range-right-left 7 3)  0)))
    (is (= [7] ((range-right-left 7 3)  1)))
    (is (= [7 10] ((range-right-left 7 3)  2)))
    (is (= [4 7 10] ((range-right-left 7 3)  3)))
    (is (= [4 7 10 13] ((range-right-left 7 3)  4)))
    (is (= [1 4 7 10 13] ((range-right-left 7 3)  5))))

What I would really like, though, is for 'range-right-left' to return a lazy sequence instead of a function. In other words, instead of doing this:

((range-right-left 7 3) 3)

I would like to be able to do:

(take 3 (range-right-left 7 3))

It seems to be the default behavior for lazy sequences to strictly grow from left to right. I have tried to develop a lazy seq that can grow in both directions, to no avail. I would very much appreciate suggestions to do such.

3
clojurelazy-sequences
Lazy sequences can only grow in one direction because they have a lazy tail. Once you have the head of a lazy sequence, you can't go back and "lazily" change it because it's already been evaluated. What are you trying to do here? It seems like you should be able to sove your range-right-left problem with 2 ranges instead of 1. If you provide more details about the use case we might be able to suggest an alternate solution. - DaoWen
One use case is to be able to get n items from the equivalence class defined by 'r (mod m)'. 'r' would be the starting middle value. The next item to the left would be obtained by subtracting m from the first of the list. Likewise, the next item to the right would be obtained by adding m to the last item in the list. I would like to have this behavior defined in a lazy-sequence so that I can be more idiomatic about using such a sequence (i.e. for n items being able to say (take 3 seq) and give me n items in the way I have specified. - satch5150
To clarify my above remarks, what I'm looking for is to be able to obtain n items from the equivalence class defined by 'r (mod m)' without having to specify a 'least' element, so that I am able to obtain items from both ends of the 'spectrum', as it were. - satch5150

3 Answers

3
votes

You could try using the approach of zippers.

(defn left [[left v right]]
  [(next left) (first left) (cons v right)])
(defn right [[left v right]]
  [(cons v left) (first right) (next right)])
(defn curr [[left v right]] v)

So now we can define your function as

(defn range-right-left [init-val step]
  [(next (iterate #(- % step) init-val))
   init-val
   (next (iterate #(+ % step) init-val))])

Then we can take any given element by using left and right to move our view of our collection and curr to extract the current element:

(def zipper (range-right-left 4 10))
(-> zipper left left left curr) ; => -26

We can also create two utility functions:

(defn left-seq [[left v right]]
  (cons v left))
(defn right-seq [[left v right]]
  (cons v right))

which gives us the ability to do something close to what you wanted

(take 3 (left-seq (range-right-left 7 3))) ; => (7 4 1)
(take 3 (right-seq (range-right-left 7 3))) ; => (7 10 13)

Note: zippers are far more general than what you're doing here, so this approach may be overkill for your particular use. If your ordering is unimportant to you then I would recommend just using DaoWen's approach of interleaving the two sides of the sequence.

1
votes

If all you want is to get n members of an equivalence class, then you could define your function like this instead:

(defn range-right-left [x step]
  (interleave (iterate #(- % step) x)
              (iterate #(+ % step) (+ x step))))

(take 5 (range-right-left 7 3))
; => (7 10 4 13 1)

(sort (take 5 (range-right-left 7 3)))
; => (1 4 7 10 13)

The results aren't in the same order that you had before, but as the example shows you can just use sort once you have your slice of the infinite stream if you really need it in sorted order.

0
votes

I'd recommend to do this:

(defn from-right-left-range
  "Take n items from a range expanding from init by step in both
  directions."
  [init step n]
  (cond
    (= 0 n) '()
    (= 1 n) (list init)
    :else (let [d (* step (dec n))]
            (concat [(- init d)]
                    (from-right-left-range init step (dec n))
                    [(+ init d)]))))

This recursive function can be memoized and will run faster. 

(dotimes [_ 5]
  (time (from-right-left-range 7 3 100)))
=> "Elapsed time: 0.129167 msecs"
   "Elapsed time: 0.065219 msecs"
   "Elapsed time: 0.061449 msecs"
   "Elapsed time: 0.069579 msecs"
   "Elapsed time: 0.060461 msecs"

Now memoized:

(def from-right-left-range (memoize from-right-left-range))
(dotimes [_ 5]
  (time (from-right-left-range 7 3 100)))
=> "Elapsed time: 0.297716 msecs"
   "Elapsed time: 0.038473 msecs"
   "Elapsed time: 0.013715 msecs"
   "Elapsed time: 0.010902 msecs"
   "Elapsed time: 0.010372 msecs"

Depending on what you originally wanted to achieve with the use of a lazy-seqs, if it was performance, this is your solution.

Now what you can do is create a lazy-seq of like

(defn right-left-ranges
  [init step]
  (map (partial from-right-left-range init step) (range)))

You can use (nth ls n) on that lazy-seq like you'd use (take n ls) on lazy-seqs to get your double-grown seq. Thanks to memoize, only the not yet calculated missing elements at the beginning and end will be added.