CODEWITHSUNDEEP
schemerangelispracket
artemonster
artemonster

Reputation: 763

Iterative range function in Scheme/Lisp

I wanted to implement range function (start, end, inc), that generates all natural numbers from start to end, with increment of inc. This is first version:

(define (gen start end step)
  (if (>= start end)
  '()
  (cons start (gen (+ step start) end step))))

The problem is, this is not tail-recursive. Another try:

(define (gen-iter start end step acc)
  (if (>= start end)
    acc
    (gen-iter (+ step start) end step (cons start acc))))

But this generates a list in reverse order :) So yeah, I can reverse it with O(n), and be happy, but I kind of stuck here, trying to make function that will construct a list with proper order from start to end, without appending on each iteration, as append is costly. There is also a list built-in, but I don't know how it operates.

Upvotes: 2

Views: 924

Answers (2)

Alex Knauth
Alex Knauth

Reputation: 8373

As uselpa already said in a comment, the solution would be to use reverse at the end. After expansion, the racket implementation of range is pretty similar to reverseing the result of your gen-iter function, except for some cases you probably weren't thinking about.

The actual implementation of range in racket uses (for/list ([i (in-range start end step)]) i), but what that expands to is actually equivalent to

(reverse
 (for/fold ([fold-var null])
           ([i (in-range start end step)])
   (cons i fold-var)))

Except that it uses an alt-reverse function instead of reverse, and it uses for/fold/derived for better error reporting. And if you expand that, it is equivalent to this after some simplification (deleting unnecessary let-values wrappers, error-checking, etc.)

(reverse
 (let ([start start] [end end] [inc step])
   (let for-loop ([fold-var null] [pos start])
     (if (if (>= step 0)
             (< pos end)
             (> pos end))
         (let ([i pos])
           (let ([fold-var (cons i fold-var)])
             (for-loop
              fold-var
              (+ pos inc))))
         fold-var))))

The named let there is equivalent to defining a helper function like this: (after substituting some lets and lifting the helper outside the range function)

(define (range start end step)
  (reverse
   (range-reversed null start end step)))
(define (range-reversed fold-var pos end step)
  (if (if (>= step 0)
          (< pos end)
          (> pos end))
      (range-reversed
       (cons pos fold-var)
       (+ pos step)
       end
       step)
      fold-var))

This is still different from your solution because your solution assumes that step is positive, while this one works even when step is negative. If step is positive, the if condition will be (< pos end) instead of the nested if.

It also uses (< pos end) where you used (>= pos end), but it also switches the if cases. That's equivalent to your solution if (< x y) is the same as (not (>= x y)), because (if (not a) b c) is equivalent to (if a c b). However, there's at least one case I can think of where that wouldn't be true, where either start or end is +nan.0. For that case, racket's range function would return an empty list, while your solution would go into an infinite loop.

Upvotes: 4

Sylwester
Sylwester

Reputation: 48745

It's not always so easy to see it but "reverse" is a keyword here. To make it iterative you need to do the actual job in reverse:

(define (my-range start end step)      
  (define (helper n acc)
    (if (= end n)
        (cons n acc)
        (helper (- n step) (cons n acc))))

  (define actual-end end) ; this needs improvement
  (helper actual-end '()))

Just as range in racket you should get these results:

(my-range 1 10 1)  ; ==> (1 2 3 4 5 6 7 8 9)
(my-range 10 1 -1) ; ==> (10 9 8 7 6 5 4 3 2)

To get this correct actual-end needs to do find the correct value based on math.

(my-range 1 10 2)  ; ==> (1 3 5 7 9)  (actual-end should be 9)
(my-range 10 1 -2) ; ==> (10 8 6 4 2) (actual-end should be 2)

I guess you can use the ceiling procedure along with the normal math procedures to get this correct.

Upvotes: 3

Related Questions