3

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

~ 目标：将嵌套列表扁平化为一个数字

  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数字。我让它在底部递归两次，因为这是它无限循环直到计算一个数字的一​​种方式。注意：此函数不再实现 flatten 函数，也不再使用其中的任何内容。

4

5 回答 5

2

这是作业吗？如果是这样，请将其标记为这样。一些提示：

  1. 你确定空列表的“浓缩”nil吗？（也许你应该返回一个数字？）
  2. 你确定condensation一个元素是一个列表吗？（也许你应该返回一个数字？）
  3. 你确定condensation最后一个案例是一个列表吗？（你不应该返回一个数字）？

简而言之，如果您所有的返回值都是列表，您condense将如何返回？28

于 2012-06-05T07:51:41.227 回答
2

想象一下你已经有了你的功能。它得到什么？它必须产生什么？

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

(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当然！请记住，我们想象我们已经拥有它。只要它得到了它想要得到的东西，它就会生产出它设计生产的东西。也就是说，给定一个原子或一个列表（内部可能有嵌套列表），它将产生一个 number。

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

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

关于您的新代码：您犯了错误：要处理 之后返回的原子列表(mapcar #'condense x)，我们有一个函数calculate可以做到这一点，无需回溯到condense自身。当您在那里替换calculate时，很明显all-atoms根本不需要检查；它只是一种教学设备，用于简化代码的开发。:) 在我们开发的时候做多余的选择是可以的，如果我们在达到正确的目标之后再把它们简化掉！

但是，删除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)))

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

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

(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)))

正如你所看到的，这个版本是高度递归的，这不是很好。

于 2012-06-05T08:12:22.693 回答
0

任务：使用嵌套列表，首先展平最里面的列表并从那里开始工作

sum
   flatten lists

对于sum使用REDUCE，不是APPLY。

对于展平列表，您需要一个循环。Lisp 已经提供了专门的映射函数。

稍微高级一点：求和和展平都可以通过调用REDUCE.

您也可以在不使用 APPLY、REDUCE 等高阶函数的情况下写下递归......这需要更多的工作。

于 2012-06-05T08:28:10.010 回答
0

这里添加了对您遇到的错误的解释，实际上您已经接近解决您的问题，只需付出更多的努力，您就会得到正确的。

; compiling (DEFUN CONDENSE ...)

; file: /tmp/file8dCll3
; in: DEFUN CONDENSE
;     (T (APPEND (FLATTEN (APPLY #'+ (CDR LST)))))
; 
; caught WARNING:
;   The function T is undefined, and its name is reserved 
;   by ANSI CL so that even
;   if it were defined later, the code doing so would not be portable.
; 
; compilation unit finished
;   Undefined function:
;     T
;   caught 1 WARNING condition
;STYLE-WARNING: redefining CONDENSE in DEFUN

(defun condense (lst)
  (cond
    ((null lst) nil)
    ((atom lst) (list lst)))
  ;.------- this is a function call, not a condition
  ;|         (you closed the parens too early)
  (t (append  (flatten (apply #'+ (cdr lst))))))

;; Argument Y is not a NUMBER: (3 1 1 1)
;;    [Condition of type SIMPLE-TYPE-ERROR]

(defun condense (lst)
  (cond
    ((null lst) nil)
    ((atom lst) (list lst));             .-- not a number!
    ;You are calling #'+ -------.        |
    ;on something, which        |  '(3 4 (3 1 1 1) (2 3 (1 2)) 5)
    ; is not a number.          |   |
    (t (append  (flatten (apply #'+ (cdr lst)))))))

;; You probably wanted to flatten first, and then sum

(defun condense (lst)
  (cond
    ((null lst) nil);          .--- returns just the 
    ((atom lst) (list lst));  /     atom 28, you can
    ;  .---------------------/      just remove it.
    (t (append (apply #'+ (flatten lst))))))

;; Now, you are lucky that append would just return the 
;; atom if it's not a list

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

;; Again, you are lucky because (apply can take enough arguments
;; while your list is reasonably small - this will not always be
;; the case, that is why you need to use something more durable,
;; for example, reduce.

(defun condense (lst)
  (cond
    ((null lst) nil)
    ((atom lst) (list lst))
    (t (reduce #'+ (flatten lst)))))

;; Whoa!

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

这一切都是因为该flatten功能确实有效。

于 2012-06-05T12:07:03.207 回答
0

如果您的 lisp 已经实现flatten和reduce功能（例如 Clojure，我将在这里使用），您可以执行以下操作：

user=> (defn condense [l] (reduce + 0 (flatten l)))
#'user/condense
user=> (condense [1 [2 [[3 4] 5]]])
15
user=>

如果做不到这一点，这些功能的幼稚实现可能是：

(defn flatten [l]
  (cond (nil?  l) l
        (coll? l) (let [[h & t] l]
                    (concat (flatten h) (flatten t)))
        true      [l]))

和：

(defn reduce [op initial-value [h & t]]
  (if (nil? t)
    (op initial-value h)
    (op initial-value (reduce op h t))))

但请务必检查您正在使用的特定 Lisp 的语义。此外，如果您正在实施reduceand flatten，您可能希望使它们尾递归，我没有这样做以保持清晰。

在 Common Lisp 中，您可以执行以下操作：

(defun flatten (l)
    (cond ((null l) l)
          ((atom l) (list l))
          (t        (append (flatten (car l))
                            (flatten (cdr l))))))

并使用 apply 而不是 reduce：

(defun condense (l) (apply #'+ (flatten l)))
于 2012-06-05T13:30:04.227 回答