Typed Racket Errors with vector-set

Question

I'm trying to write a function called rotate-right

(: rotate-right : (All (A) (Vectorof A) Integer Integer -> Void))
(rotate right v lo hi)

Which modifies vector v, such that that the elements in the interval [lo..hi-1] are moved to the positions [lo+1..hi] and the element at index hi is moved to position lo. For example

(rotate-right (vector 0 1 2 3 4 5 6 7 8 9))

produces

#(0 1 5 2 3 4 6 7 8 9).

I've written this code

(: rotate-right : (All (a) (Vectorof a) Integer Integer -> Void))
(define (rotate-right v lo hi)
  (local
    {(define tmp v)
     (: vector-scan : (All (a) (Vectorof a) Integer Integer Integer -> Void))
     (define (vector-scan v lo hi c)
       (cond
         [(= c -1) (vector-set! v 0 (vector-ref v 0))]
         [(and (< lo c) (>= hi c))
          (vector-scan
           (vector-set! v c (vector-ref tmp (- c 1)))
           lo hi (- c 1))]
         [(= c lo)
          (vector-scan
           (vector-set! v lo (vector-ref tmp hi))
           lo hi (- c 1))]
         [else
          (vector-scan
           (vector-set! v c (vector-ref v c))
           lo hi (- c 1))]))}
    (vector-scan v lo hi (vector-length v))))

however, this gives me type errors with vector-set!. Can anyone tell me what I'm doing wrong? Thanks.

Answer 1

I cannot help you with the typed part, but your algorithm doesn't work in regular Racket either. A more concise way to write this (while keeping using indexes as you do) would be:

(define (rotate-right v lo hi)
  (for/vector ((i (in-range (vector-length v))))
    (vector-ref v
                (cond
                  ((< i lo) i)
                  ((= i lo) hi)
                  ((<= i hi) (sub1 i))
                  (else i)))))

then

> (rotate-right (vector 0 1 2 3 4 5 6 7 8 9) 2 5)
'#(0 1 5 2 3 4 6 7 8 9)

Answer 2

Here is a version with for.

#lang typed/racket

(: rotate-right : (All (A) (Vectorof A) Integer Integer -> Void))
(define (rotate-right v lo hi)
  (define hi-1 (- hi 1))
  (cond
    [(>= lo hi-1) (void)]
    [else         (define tmp (vector-ref v hi-1))
                  (for ([i (in-range hi-1 lo -1)])
                    (vector-set! v i (vector-ref v (- i 1))))
                  (vector-set! v lo tmp)]))

(define v (vector 0 1 2 3 4 5 6 7 8 9))
(rotate-right v 3 7)
v

The output is:

'#(0 1 2 6 3 4 5 7 8 9)

The question is how we can fix the original program. Since vector-set! returns void, we need to separate the calls to vector-set! and vector-scan.

Furthermore the type of vector-scan should reuse the type variable a from rotate a.

That gives the following program which has correct types. (I haven't tested whether it rotates correctly though).

(: rotate-right : (All (a) (Vectorof a) Integer Integer -> Void))
(define (rotate-right v lo hi)
  (local
    {(define tmp v)
     (: vector-scan : (Vectorof a) Integer Integer Integer -> Void)
     (define (vector-scan v lo hi c)
       (cond
         [(= c -1) (vector-set! v 0 (vector-ref v 0))]
         [(and (< lo c) (>= hi c))
          (vector-set! v c (vector-ref tmp (- c 1)))
          (vector-scan v lo hi (- c 1))]
         [(= c lo)
          (vector-set! v lo (vector-ref tmp hi))
          (vector-scan v lo hi (- c 1))]
         [else
          (vector-set! v c (vector-ref v c))
          (vector-scan v lo hi (- c 1))]))}
    (vector-scan v lo hi (vector-length v))))