在 lisp 函数中使用带有缺点的嵌套汽车

Question

我正在制作一个递归 lisp 函数，它接受两个列表并创建一个索引对的子列表

例如：放入 (A B C D( 和 (1 2 3 4( 并得到 ((1 A( (2 B( (3 C( (4 D((

但是，我在使用汽车和缺点来制作上述子列表时遇到问题。这是我的代码：

(DEFUN zipper (a b)
    (if (= (OR (list-length a) (list-length b)) 0)
        (setq c NIL)
        (progn (zipper (cdr a) (cdr b))
        (cons '((car a) (car b)) c))
    )
)

我玩了一会儿，似乎使用汽车创建列表在大多数情况下都不起作用。此外，我正在使用 CLISP。有什么想法吗？

谢谢！

Answer 1

总体思路是正确的。不过，存在很多问题。一起来看看吧。

(DEFUN zipper (a b)
    (if (= (OR (list-length a) (list-length b)) 0)
        (setq c NIL)
        (progn (zipper (cdr a) (cdr b))
        (cons '((car a) (car b)) c))
    )
)

第一个缩进：

(DEFUN zipper (a b)
  (if (= (OR (list-length a) (list-length b)) 0)
      (setq c NIL)
      (progn (zipper (cdr a) (cdr b))
        (cons '((car a) (car b)) c))                 ; <--
    )
  )

下一个悬空括号：

(DEFUN zipper (a b)
  (if (= (OR (list-length a) (list-length b)) 0)
      (setq c NIL)
      (progn (zipper (cdr a) (cdr b))
        (cons '((car a) (car b)) c))))

返回 IF 中真实情况的空列表：

(defun zipper (a b)
  (if (= (OR (list-length a) (list-length b)) 0)
      nil
      (progn (zipper (cdr a) (cdr b))
        (cons '((car a) (car b)) c))))

现在缺点是错误情况下的结果：

(defun zipper (a b)
  (if (= (OR (list-length a) (list-length b)) 0)
      nil
      (cons '((car a) (car b))
            (zipper (cdr a) (cdr b)))))

还有什么工作要做？

• 请参阅"RSM"的评论：将引号替换为调用list。
• 不要使用list-length.请改用null。它检查列表是否为空。 list-length会在每次调用时遍历输入整个列表 ->效率低下。

Answer 2

如果你在递归的每一步都调用list-length，你每次都会完全遍历两个列表，这使得你的zipper函数相对于列表大小的总和具有二次时间复杂度：

(zipper '(1 2 3) '(4 5 6))
=> (list-length (1 2 3))
=> (list-length (2 3))
=> (list-length (3))
=> (list-length ())
=> (list-length (4 5 6))
=> (list-length (4 5))
=> (list-length (5))
=> (list-length ())
(zipper '(2 3) '(5 6))
=> (list-length (2 3))
   ...
=> (list-length (5 6))
   ...
...

这是低效的，在这里没有必要。由于您已经在访问这两个列表，因此您可以使用 null 或 endp 直接检查其中任何一个是否为空，这需要恒定的时间。一旦其中一个列表为空，您就会返回 NIL，顺便说一下，这是 mapcar 的默认行为。另请注意，mapcar可以同时处理多个列表，例如：

(mapcar #'+ '(1 2) '(5 8))
=> (6 10)

如果您知道一个函数接受(至少(两个参数并返回一个列表，那么您可以在列表上mapcar该函数并拥有一个列表列表。

Answer 3

来自其他语言(如 Python 和 Haskell(的 zip 函数是 mapcar 的一个特例。

传统的zip功能可以通过以下方式实现：

> (mapcar #'list list1 list2 ... listn)

在这种情况下：

> (mapcar #'list '(A B C D) '(1 2 3 4))
((A 1) (B 2) (C 3) (D 4))

要按照您的指示交换货币对的顺序，只需相应地更改传递给mapcar的函数：

> (mapcar #'(lambda (x y) (list y x)) '(A B C D) '(1 2 3 4))
((1 A) (2 B) (3 C) (4 D))

查看地图车的文档以获取更多详细信息。

Answer 4

zip具有

任意数量列表的函数

(defun zip (&rest lists)
  (apply #'mapcar #'list lists))

最短的列表决定了拉链的深度。

CL-USER> (zip '(1 2 3) '(a b c) '("a" "b" "c"))
((1 A "a") (2 B "b") (3 C "c"))
CL-USER> (zip '(1 2 3) '(a b c) '("a" "b" "c" "d"))
((1 A "a") (2 B "b") (3 C "c"))

Answer 5

你可以做这样的事情：

(defun zipper (a b)
   (if (or (null a) (null b))
       nil
       (cons (list (car b) (car a)) (our-combiner (cdr a) (cdr b)))))

我们可以检查其中一个列表是否为 null，以便我们可以在其中一个列表用完时停止(类似于 mapcar 在其中一个列表用完时停止对列表应用函数的方式(。然后，我们可以在每个递归调用中使用列表的汽车来修复嵌套列表。您的输出将是：

CL-USER> (zipper '(a b c d) '(1 2 3 4))
((1 A) (2 B) (3 C) (4 D))
CL-USER> 

我们也可以使用mapcar，因为它将迭代两个列表并返回将函数应用于两个列表的结果(与mapc不同(。这是更少的代码行，并且由于它会在某些列表用完时返回，因此不需要条件：

(defun zipper (a b)
  (mapcar #'list b a))