lisp - 将 Lisp 代码形成任务——与展平列表方法相关

Question

我在尝试为要解决的问题编写代码时遇到问题。它是这样的:

~ 目标:将嵌套列表展平为一个数字

1. 如果对象是列表，则用其原子的总和替换列表。
2. 对于嵌套列表，首先将最里面的列表展平，然后从那里开始工作。

示例:

  (CONDENSE '(2 3 4 (3 1 1 1) (2 3 (1 2)) 5))

       (2 3 4 (6) (2 3 (3)) 5)

       (2 3 4 (6) (8) 5)

       (28) 

  => 28 

我已经尝试为这个问题实现扁平化列表功能，结果是这样的:

(defun condense (lst)
  (cond
    ((null lst) nil)
    ((atom lst) (list lst)))
    (t (append  (flatten (apply #'+ (cdr lst))))))

但它给了我错误:(

任何人都可以向我解释我的处理/代码有什么问题吗？我该如何改进它？

---

更新:2012 年 6 月 5 日

(defun condense(lxt)
  (typecase lxt
    (number (abs lxt))
    (list
        (if (all-atoms lxt)
           (calculate lxt)
           (condense (mapcar #'condense lxt))))))

所以在这里，在此代码中，显示了我的真实意图。我有一个函数 calculate，它根据列表中的值执行计算。不一定每次都是一样的操作。另外，我知道我正在返回数字的绝对值；我这样做是因为我找不到另一种方法来返回数字本身。如果 lxt 是一个数字，我需要找到一种返回数字的方法。我让它在底部递归两次，因为这是它无限循环直到它计算出一个数字的一​​种方式。注意:此函数不再实现展平函数，也不再使用其中的任何内容。

Answer 1

假设您已经有了自己的函数。它得到什么？它必须生产什么？

给定一个原子，它返回什么？给定一个简单的原子列表，它应该返回什么？

(defun condense (x)
  (typecase x
    (number  
       ; then what?
       (condense-number x))
    (list
       ; then what?
       (if (all-atoms x)
         (condense-list-of-atoms x) ; how to do that?
         (process-further-somehow
            (condense-lists-inside x))))
    ; what other clauses, if any, must be here?
    ))

condense-lists-inside 必须做什么？根据你的描述，就是把里面的嵌套列表压缩成一个数，原子完好无损。所以它会留下一个数字列表。为了以某种方式进一步处理，我们已经“拥有”一个函数，condense-list-of-atoms，对吧？

现在，如何实现condense-lists-inside？很简单，

(defun condense-lists-inside (xs)
  (mapcar #'dowhat xs))

做什么？为什么，condense，当然!请记住，我们想象我们已经拥有它。只要它得到了它想要得到的东西，它就应该生产它设计用来生产的东西。即，给定一个原子或一个列表(内部可能有嵌套列表)，它将产生一个数字。

现在，填空并简化。特别是，看看您是否真的需要 all-atoms 检查。

编辑:实际上，使用 typecase 是一个不幸的选择，因为它将 NIL 视为 LIST。我们需要区别对待 NIL，返回一个“零值”。所以最好使用通常的 (cond ((null x) ...) ((numberp x) ...) ((listp x) ...) ... ) 构造。

关于您的新代码:您犯了错误:要处理 (mapcar #'condense x) 之后返回的原子列表，我们有一个函数 calculate也就是说，无需回溯到 condense 本身。当您在此处替换 calculate 时，很明显根本不需要检查 all-atoms；它只是一种教学手段，可以简化代码的开发。 :) 在我们开发时做出多余的选择是可以的，如果我们随后将它们简化，在我们实现了正确性<的目标/em>!

但是，删除 all-atoms 检查将破坏您的要求 #2。然后计算将进行如下

(CONDENSE '(2 3 4 (3 1 1 1) (2 3 (1 2)) 5))
==
(calculate (mapcar #'condense '(2 3 4 (3 1 1 1) (2 3 (1 2)) 5)))
== 
(calculate (list 2 3 4 (condense '(3 1 1 1)) (condense '(2 3 (1 2))) 5))
== 
(calculate (list 2 3 4 (calculate '(3 1 1 1)) 
                         (calculate (list 2 3 (calculate '(1 2)))) 5))
== 
(calculate (list 2 3 4 6 (calculate '(2 3 3)) 5))
== 
(calculate (list 2 3 4 6 8 5))
==
28

即它将以从左到右的方式进行，而不是从最深的嵌套层开始。将嵌套列表想象成一棵树(它确实是)，这将从最深的左角向上和向右“咀嚼”树；具有all-atoms 检查的代码将严格按级别执行。

所以最后的简化代码是:

(defun condense (x)
  (if (listp x)
    (reduce #'+ (mapcar #'condense x))
    (abs x)))

备注:查看最后一个归约序列图，清晰的画面出现了——替换参数中的每个节点tree 与 calculate 应用程序。这是一个明显的例子 folding ，就像 reduce 那样在树上而不是普通列表上完成。

这可以直接用所谓的“car-cdr 递归”编码，将每个 cons 单元格替换为对递归的两个结果应用组合函数 f调用单元格的 car 和 cdr 组件:

(defun condense (x) (reduce-tree x #'+ 0))
(defun reduce-tree (x f z)
  (labels ((g (x)
            (cond
             ((consp x) (funcall f (g (car x)) (g (cdr x))))
             ((numberp x) x)
             ((null x) z)
             (T (error "not a number")))))
    (g x)))

如您所见，这个版本是高度递归的，这不是很好。