vector - 通过附加向量来改变方案中的向量

Question

我不知道 Scheme 中向量的底层实现，因此不知道如何编写vector-append!

原型：

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

PS 首选使用向量而不是列表，因为vector-ref它是一个恒定时间操作[src]

Answer 1

您无法在创建矢量后调整其大小，因此vector-append!无法将其实现为就地操作。您可以做的是创建一个大小等于所有子向量大小之和的新向量，其中所有子向量中的元素将一个接一个地复制。

用作vector-grow起始程序，然后从那里开始工作。您必须对索引进行一些操作才能获得有效的解决方案。

Answer 2

向量不可调整大小。所以vector-append!扩展向量大小的 a 是不可能的。

Answer 3

这是我的实现。抱歉，评论是从现在开始的，而不是我编写函数时的评论。

也不要认为你可以直接改变向量，因为它们是固定长度的。

(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

通常是一个“！” 意味着 Scheme 中的破坏性操作。您没有明确说明您想要一个破坏性的实现。我会给你两个，有点。首先是无损版本，简单地说：

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

现在对于可变向量，您需要自己的向量抽象，因为 Scheme 向量的长度是不可变的。不要让这分散你的注意力；如果你需要它，你需要它。

(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)))))

然后是一些新抽象的助手：

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

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

;; etc