Mutate vector in scheme by appending vectors

Question

I don't know the underlying implementation of vectors in Scheme, hence not sure how to write a vector-append!

Prototype:

(define (vector-append! vect . vects)
  ; definition here 
  )

P.S. Preferred to use vector over list since vector-ref is a constant time operation [src]

Answer 1

You can't resize a vector after its creation, so vector-append! can not be implemented as an in-place operation. What you can do, is create a new vector with size equal to the sum of all the subvectors' sizes, where the elements in all subvectors will be copied one after the other.

Use vector-grow as the starting procedure, and work from there. You'll have to play a bit with indexes to get a working solution.

Answer 2

Vectors are not resizeable. So a vector-append! that extends a vector's size is not possible.

Answer 3

Here's my implementation. Sorry comments are from now rather than when I wrote the function.

Also don't think you can mutate the vector directly as they are fixed-length.

(define (vector-append . rest)
 (letrec    
    ((all-vectors?
     (lambda (vector . rest)
          (and (vector? vector)
           (or (null? rest) 
           (apply all-vectors? rest))))) 
    (++ (lambda (x) (+ x 1)))
    (gobble-next
     (lambda (big-i small-i vec-big vec-small)
      (if (= small-i  
         (vector-length vec-small))
          'gobbled
          (begin 
        (vector-set! vec-big big-i (vector-ref vec-small small-i))
        (gobble-next (++ big-i) (++ small-i) vec-big vec-small)))))
    (helper 
     (lambda (i vector . rest) ;;the i here keeps track of the place in the new-vec 
          (if (null? rest)     ;;to start copying at
          (begin
        (gobble-next i 0 new-vec vector)
        new-vec)
          (begin
        (gobble-next i 0 new-vec vector)

        (apply helper (cons 
                (+ i (vector-length vector)) 
                rest))))))
    (new-vec (make-vector (apply length-of-vectors rest)))) ;;end of letrec
   (cond ((null? rest) 
      (error "error, no arguments to vector-append"))
     ((not (apply all-vectors? rest)) (error "arguments not all vectors"))
     ((null? (cdr rest))
      (car rest))
     (else (apply helper (cons 0 rest)))))) 

(define length-of-vectors 
  (lambda (vector . rest)
   (+ (vector-length vector)
      (if (null? rest)
      0
      (apply length-of-vectors rest)))))

Answer 4

Normally a '!' implies a destructive operation in Scheme. You've not stated clearly that you want a destructive implementation. I'll give you both, sort of. First the non-destructive version, simply:

(define (vector-append! vect . vects)
  (list->vector (apply append (map vector->list (cons vect vects)))))

Now for the mutable one, you'll need your own vector abstraction because Scheme vectors are immutable in length. Don't let this distract you; if you need it you need it.

(define (my-vector . values)
  (cons 'MY-VECTOR (list->vector values)))
(define my-vector-values cdr)  ; private

(define (my-vector-ref vect index)
  (vector-ref (my-vector-values vect) index))

(define (my-vector-append! vect . vects)
  (set-cdr! vect (apply vector-append! (map my-vector-values (cons vect vects)))))

and then some helpers for your new abstraction:

(define (list->my-vector list)
  (cons 'MY-VECTOR (list->vector list)))

(define (vector->my-vector vector)
  (cons 'MY-VECTOR vector) ; maybe

;; etc