用common lisp编写一个返回列表求反的函数

Question

我在当前代码中得到以下错误：

 LET: illegal variable specification
   (COND (LISTP A (IF (NEGATE A) (NEGATE (REST L)) NIL))
    (T (SETF A (-A) (APPEND (LIST A) (REST L)) (NEGATE (REST L)) NIL)))

我当前的代码：

(defun negate(L)
 (setq x -1)

 (if (not (null L))

  (let ((a (fitst L))
        (cond (listp a
              (if (negate a)
                  (negate (rest L))
                nil))
        (t
         (setf a (-a) (append (list a)(rest L))
               (negate (rest L))
               nil))))
)
))

以及它需要通过的测试用例

o List is  (1 2 3 4)  
o Output should be: (-1 -2 -3 -4)

o List is  (1 -2 (3 4))  
o Output should be: (-1 2 (-3 -4) )

Answer 1

在最礼貌的意义上，你的代码有点离谱。你这周在学Lisp，是不是？没关系!它是一门有趣的语言，可以做一些很棒的事情。

你的基本情况是-

(defun negate (n) 
  (if (> n 0) (- 0 n)))

(map #'negate '(1 2 3 4))

遍历这棵树要复杂得多，但让我们来遍历一下这些想法。

(if (not (car seq)) 
  (if (listp (car seq))
    ;;Recurse
    ;;Otherwise negate the current element and append it to the recursed.

让我们在这里尝试第一次剪切：

(defun negate-seq (seq)
  (if (not seq)
      (return-from negate-seq))

  (if (listp (car seq))
      (negate-seq seq)
    (list (negate (car seq)) (negate-seq (cdr seq)))))

太好了!除了..。

(negate-seq '(1 2)) ==> (-1 (-2 NIL))

还有..。

 (negate-seq '(1 (1 2 -3))) ==> STACK OVERFLOW!

哦，天哪。我们现在有麻烦了。

首先，让我们尝试使用cons而不是list。这就解决了奇怪的嵌套列表问题。

很明显，我们进入了一个无限递归的循环。那是不可能的因为我们有not seq守卫。好的，让我们试一试调试。我正在使用CLISP，并且我可以使用以下命令跟踪参数：

(trace 'negate-seq) 

然后,

(negate-seq '(1 (1 2 -3)))

突然我看到了一个爆炸的

1621. Trace: (NEGATE-SEQ '((1 2 -3)))
1622. Trace: (NEGATE-SEQ '((1 2 -3)))
1623. Trace: (NEGATE-SEQ '((1 2 -3)))
1624. Trace: (NEGATE-SEQ '((1 2 -3)))

天哪，我忘带我的cdr了，我得把单子上的东西拿出来！嗯。

让我们试试这个：

(defun negate-seq (seq)
  (if (not seq)
      (return-from negate-seq))

  (if (listp (car seq))
      (cons (negate-seq (car seq))
        (negate-seq (cdr seq)))
    (cons (negate (car seq)) (negate-seq (cdr seq)))))

为车递归，在车上回避，把他们放在一起，我们可能有点头绪。

 (negate-seq '(1 (1 2 -3))) =>  (-1 (-1 -2 NIL)

嗯。让我们来看看它的轨迹。

1. 跟踪：(NEGATE-SEQ '(1 (1 2-3)
2. 跟踪：(NEGATE-SEQ '((1 2-3)
3. 跟踪：(NEGATE-SEQ '(1 2-3))
4. 跟踪：(NEGATE-SEQ '(2 -3))

H124跟踪：(NEGATE-SEQ '(-3))

1. Trace：(NEGATE-SEQ‘NIL)
2. 跟踪: NEGATE-SEQ==> NIL
3. 跟踪: NEGATE-SEQ ==> (NIL)
4. 跟踪: NEGATE-SEQ ==> (-2 NIL)
5. 跟踪: NEGATE-SEQ ==> (-1 -2 NIL)
6. 跟踪：(NEGATE-SEQ‘NIL)
7. 跟踪: NEGATE-SEQ ==> NIL
8. 跟踪: NEGATE-SEQ ==> (-1 -2 NIL)
9. 跟踪: NEGATE-SEQ ==> (-1 (-1 -2 NIL))

G244

所以我递归到-3，然后....它掉下来了？很奇怪。阿!我一直在抓取事物的CDR。CDR始终是一个列表。(cdr '(-3))为零！

让我们看看这里……

(翻找了很久)

如果为正，则Negate返回nil。哦。

(defun negate (n) 
  (if ( > n 0) 
      (- 0 n)
    n))


(defun negate-seq (seq)
  "Written by Paul Nathan"
  (if (not seq)
      (return-from negate-seq))

  (if (listp (car seq))
      (cons (negate-seq (car seq))
        (negate-seq (cdr seq)))
    (cons (negate (car seq)) 
      (negate-seq (cdr seq)))))

Answer 2

我不确定您是否在寻找一种温和的方式来纠正所显示的代码，或者您是否在寻求其他方法来完成此操作。我的第一个想法是使用mapcar

(defun negate-tree (tree)
  (mapcar (lambda (e)
            (cond 
              ((null e) nil)
              ((listp e) (negate-tree e))
              (t (- e))))
          tree))

然后，您可以概括出否定方面，并编写map-tree，接受一个应用于树中原子的函数：

(defun map-tree (f tree)
  (mapcar (lambda (e)
            (cond 
              ((null e) nil)
              ((listp e) (map-tree f e))
              (t (funcall f e))))
          tree))

比方说，你可以用一元否定函数调用它：

(map-tree #'- '(1 -2 (3 4)))

这样的调用假设树中的所有叶子要么是nil，要么是一元求反函数。

接受nil作为树中可能的叶会使访问算法变得有点混乱，而且不清楚所提供的函数f是否应该应用于所有叶-甚至是那些nil-so的叶，因为函数本身可以决定是否以及如何处理nil。

这个版本的另一个缺陷是它如何处理非的cons细胞。请注意，对于所有cons单元格，函数listp都返回true -即使是那些不构成正确列表的单元格-但mapcar确实要求其输入是正确的列表。我们可以沿着我们的"listp true“路径结束，递归地调用mapcar，并让mapcar因为接收到不正确的列表而失败。这意味着上面的算法要么需要测试cons单元格，看看它们是否是正确的列表，然后再将它们传递给mapcar，可能会将那些不是正确列表的元素视为叶子(这里我不愿说“原子”)，或者需要说明预期的树结构是由正确列表的正确列表组成的。

如果您需要接受不一定是列表本身的顶级“树”，这意味着一个单独的原子是一个有效的树，或者nil是一个有效的树，您可以拆分上述函数的组成部分，并在确定被检查的树是一个列表之后编写一个只使用mapcar的函数。

Answer 3

如果你这样写：

 (defun negate (n)
   (if ( > n 0)
     (- 0 n)
     n))

那么你就把你的代码限制为实数了。

如果您使用Common Lisp提供的原始negate函数，它将对任何数字起作用：

(mapcar (function -) '(1 2/3 #C(4 5)))     
--> (-1 -2/3 #C(-4 -5))