0

我是 Lisp 的新手，想length用递归来实现这个功能。我编写了以下代码只是发现它只能用于列表而不能用于字符串。

(defun mylen (l)
  (if (eq (cdr l) nil)
    1
    (+ 1 (mylen (cdr l)))))

我想知道我是否可以只编写一个既适用于列表又适用于字符串的函数？

4

4 回答 4

4

对任意序列使用序列函数

首先，请注意，Common Lisplength可以处理任何序列，而不仅仅是列表（不仅仅是字符串等）。所以你实际上根本不需要写这个。通常还有一些其他函数可以对序列进行操作，例如map. 一般来说，如果在列表和向量上都有效的话，编写通用代码并不是那么容易。实现通常通过检查首先提供了哪种序列，然后使用专门的版本来实现采用任意序列的函数。在可用时使用这些功能对您有利。您可以查看 HyperSpec 中的17.3 序列字典，了解更多对任意序列进行操作的函数。

您可以使用map和实现sequence-length这样的：

(defun sequence-length (sequence &aux (length 0))
  (map nil (lambda (x)
             (declare (ignore x))
             (incf length))
       sequence)
  length)

以上sequence-length只是强调了map适用于每一个。reduce正如Rainer Joswig 指出的那样，一个更惯用的解决方案是使用另一个通常适用于序列的函数，（此代码基于他的答案中的代码，但用于constantly创建一个忽略其参数并返回的函数1）：

(defun sequence-length (sequence)
  (reduce '+ sequence :key (constantly 1)))

CL-USER> (sequence-length '(1 2 3))
3
CL-USER> (sequence-length "foobar")
6

另一种选择是使用count-ifAs in

(count-if (constantly t) sequence)

它计算(constantly t)返回 true 的项目数，即所有项目。

编写自己的序列函数

但是，您正在实现的递归类型确实取决于由cons单元构建的列表，您可以轻松处理列表的第一部分，然后处理列表的其余部分。一般来说，没有函数可以对序列执行此操作，因为获取向量的其余部分通常意味着获取它的副本。通常，如果需要这样的东西，该函数会采用开始和结束索引，并在这些索引上递归，而不是在序列上。例如，

(defun list-elements (sequence start end)
  (if (= start end)
      '()
      (cons (elt sequence start)
            (list-elements sequence (1+ start) end))))

CL-USER> (list-elements "abcdefghijklmnop" 3 7)
(#\d #\e #\f #\g)

的大多数实现reduce只是简单地检查序列是列表还是向量，然后分派到以最合适的方式处理这些的专用版本。例如，如果您查看SBCL 的实现reduce（从第 1242 行开始），您将看到四个宏的实现：

  1. 咕哝减少
  2. 从头开始咕哝减少
  3. 减少列表
  4. 从末端减少列表

和一个序列遍历器：

  • 减少

您需要更多地了解 SBCL 中的定义形式以了解它们是如何使用的，但它们确实表明实现通用序列函数是一项工作。

为了完整性，效率低下的第一个元素/序列的其余部分

说了这么多之后，我要指出，你可以使用subseq适用于任意序列的 ，对向量和列表进行这种递归，但它确实效率不高。例如，这是一个微不足道的reverse-into-list函数。

(defun reverse-into-list (sequence &optional (result '()))
  (if (eql 0 (length sequence))
      result
      (reverse-into-list (subseq sequence 1) 
                         (cons (elt sequence 0) result))))

CL-USER> (reverse-into-list "hello")
(#\o #\l #\l #\e #\h)
CL-USER> (reverse-into-list '(1 2 3))
(3 2 1)

这用于length确定何时停止，但您可以编写一个更有效的版本，首先检查它是否是一个列表，如果是，检查它是否为空（恒定时间），如果它不是一个列表，只需调用 length （这也应该是恒定的时间）。

于 2013-10-10T01:14:40.803 回答
3

只是为了补充约书亚的答案：不map，使用reduce：

(reduce #'+ sequence :key (constantly 1))

在 Lisp 中计算字符串的长度是没有用的，因为每个向量都将长度存储为一个属性——没有像 C 中那样的结束标记。因此，向量的长度——并且字符串是向量——不需要在 Lisp 中计算。

于 2013-10-10T07:28:58.137 回答
1

您的 Lisp 实现的标准库length函数可能通过访问一些内部属性来处理字符串和其他向量。但是如果你想递归地计算向量的长度，你最好的选择可能是将coerce它们列在列表中。向量只是不像列表那样本质上是递归数据结构。

顺便说一句，您当前的实现对于列表也是错误的。对于空列表，它将失败（即返回1而不是）。0您可以通过简化它使其适用于空列表。

于 2013-10-10T03:07:45.100 回答
1

可以从序列中提取“其余部分”，并且如果它是向量，则只有少量： 

(defun sequence-rest (seq)
  (if (listp seq)
      (rest seq)
      ;; A full version would also care about element-type etc.
      (make-array (1- (length seq)) :displaced-to seq
                  :displaced-index-offset 1)))

(defun mylen (seq)
  (if (zerop (length seq))
    1
    (+ 1 (mylen (sequence-rest seq)))))
于 2013-10-10T05:30:50.690 回答