Lisp：将向量分块

Question

如这里所提到的，我试图通过实现lodash来自学口齿不清。

我基本上没有关于Lisp的经验，所以对js来说微不足道的工作对我来说是陌生的。

例如，我正在研究一种_.chunk方法的实现，该方法在js中采用一个数组和一个size变量，并按大小“分块”该数组：

_.chunk(['a', 'b', 'c', 'd'], 2);
// => [['a', 'b'], ['c', 'd']]

_.chunk(['a', 'b', 'c', 'd'], 3);
// => [['a', 'b', 'c'], ['d']] 

作为对通用Lisp数据类型完全陌生的人，我认为类似类型将是向量，而不是数组，对吗？

其次，我在算法上解决此问题的方法是保留一个length变量和一个pointer变量，并获取数组/向量的一个子集，[指针+大小的指针]，而指针+大小为<长度，然后返回[指向长度的指针]，当它不再为真时，否则增加指向指针+大小+ 1的指针。

不知道如何在Lisp中实现它，到目前为止，这是我的代码。

(defun _.chunk (vector &optional (size 1 size-p))
   (if (or (not size-p) (eq size 1)) 
        vector
        ((let   (                    
                    (array_length (array-total-size array))
                    (pointer)
                )
            ???
        ))      
    )  
)

Answer 1

对于此实现，我将首先编写一个惯用的Common Lisp版本的块，该版本可在CL程序中使用（高效等），然后编写一个薄薄的lodash层，仅将这些函数包装起来。

例如，我首先要编写一个辅助函数，以允许与分块向量共享存储。置换数组是指另一个数组，但具有偏移量和不同的大小。将块仅作为原始向量的视图可能会很有用，以便它们都共享相同的基础存储阵列。这不仅是内存优化：在对块或原始向量进行突变时，行为是不同的，因为一个中的任何更改在另一个中都是可见的。但是据我所知lodash是（是？）一种纯函数式语言，所以如果您不对它们进行突变，则共享一些数据是有意义的。一些语言将这种间接数组称为“切片”。

(defun slice (vector start end)
  (make-array (- end start)
              :element-type (array-element-type vector)
              :displaced-to vector
              :displaced-index-offset start))

因此，我还将像通常一样使chunk-vectoraccept :start和:endparameters一起sharedp指定是否应与原始向量共享存储：

(defun chunk-vector (size vector &key start end sharedp)
  (check-type size (integer 1))
  (loop
     with slicer = (if sharedp #'slice #'subseq)
     and low = (or start 0)
     and high = (or end (length vector))
     for s from low below high by size
     for e from (+ low size) by size
     collect (funcall slicer vector s (min e high))))

注意：我认为这nil是一个可能的值end，表示向量的结尾，以反映subseq工作原理。我对做了同样的事情start，因为对于这些变量，可以毫无疑问地使用nil值来表示“默认值”。我也可以像在tfb的答案中那样在lambda列表中定义默认值。

以下是一些测试：

(chunk-vector 3 #(0 1 2 3 4 5 6 7 8 9) :sharedp t)
(#(0 1 2) #(3 4 5) #(6 7 8) #(9))

(chunk-vector 2 #(0 1 2 3 4 5 6 7 8 9))
(#(0 1) #(2 3) #(4 5) #(6 7) #(8 9))

(chunk-vector 1 #(0 1 2 3 4 5 6 7 8 9))
(#(0) #(1) #(2) #(3) #(4) #(5) #(6) #(7) #(8) #(9))

同样，您还可以定义一个chunk-list函数，并根据序列类型将lodash chunck函数分配给每个专用版本。

这可以使用CLOS来完成，但是由于已经在另一个答案中得到了证明，因此我将定义各个专用功能。

下面是一个实现chunk-list了基于LDIFF。我首先尝试将所有情况混合在一个函数中，但这变得不必要地复杂。

这是第一个无限制的块函数：

(defun chunk-list/unbounded (size list)
  (loop
     for front = list then next
     for next = (nthcdr size front)
     collect (ldiff front next)
     while next))

• front定义为initial list，则next每个步骤的当前值
• next是下一个块，使用size；这对于没有足够元素的列表非常有用，因为在这种情况下，nthcdr只返回剩余的元素。

处理该end参数需要更复杂的情况，为此，我们定义了有界版本，其中还存在一个额外的upper-limit计数器，该计数器size在迭代的每个步骤中都会减少。它代表要添加的剩余元素数，并与size一起用于计算(min size upper-limit)下一块的大小：

(defun chunk-list/bounded (size list upper-limit)
  (loop
     for front = list then next
     for next = (nthcdr (min size upper-limit) front)
     collect (ldiff front next)
     do (decf upper-limit size)
     while (and next (plusp upper-limit))))

最后，chunk-list根据是否end为nil 调度两个版本。呼叫在此内联（因为我们可以）：

(defun chunk-list (size list &key (start 0) end)
  (declare (inline check-list/bounded check-list/simple))
  (check-type size (integer 1))
  (let ((list (nthcdr start list)))
    (when list
      (if end
          (chunk-list/bounded size list (- end start))
          (chunk-list/unbounded size list)))))

一些例子：

(chunk-list 3 '(1 2 3 4 5 6 7))
((1 2 3) (4 5 6) (7))

(chunk-list 29 '(1 2))
((1 2))

(chunk-list 2 (alexandria:iota 100 :start 0) :start 10 :end 20)
((10 11) (12 13) (14 15) (16 17) (18 19))