为任务形成Lisp代码-与扁平化列表方法有关 [英] Forming Lisp code to task -- related to flatten list method

问题描述

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

I'm having issues trying to form code for a problem I want to resolve. It goes like this:

〜目标:将嵌套列表压成一个数字

~ Goal: flatten a nested list into one number

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 

我已经尝试实现此问题的拼合列表功能，但最终得到了这个结果:

I've tried to implement the flatten list function for this problem and I ended up with this:

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

但是它给了我错误:(

But it gives me errors :(

有人可以向我解释我的处理/代码出了什么问题吗?我该如何改善?

Could anyone explain to me what is wrong with my processing/code? How can I improve it?

更新:2012年6月5日

UPDATE: JUNE 5 2012

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

因此，在此代码中显示了我的真实意图.我有一个函数calculate，该函数根据列表中的值执行计算.不必每次都执行相同的操作.另外，我知道我返回的是数字的绝对值.我这样做是因为我找不到其他方法来返回数字本身.如果lxt是数字，我需要找到一种方法来返回数字.而且我在底部进行了两次递归，因为这是一种无限循环的方式，直到它计算出一个单数为止.注意:此函数不再实现flatten函数，也不使用其中的任何内容.

So here, in this code, my true intent is shown. I have a function calculate that performs a calculation based off the values in the list. It is not necessarily the same operation each time. Also, I am aware that I am returning the absolute value of the number; I did this because I couldn't find another way to return the number itself. I need to find a way to return the number if the lxt is a number. And I had it recurse two times at the bottom, because this is one way that it loops on itself infinitely until it computes a single number. NOTE: this function doesn't implement a flatten function anymore nor does it use anything from it.

推荐答案

想象一下您已经拥有了函数.它得到什么?它必须产生什么?

Imagine you have your function already. What does it get? What must it produce?

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

Given an atom, what does it return? Given a simple list of atoms, what should it return?

(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，对吧?

What must condense-lists-inside do? According to your description, it is to condense the nested lists inside - each into a number, and leave the atoms intact. So it will leave a list of numbers. To process that further somehow, we already "have" a function, condense-list-of-atoms, right?

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

Now, how to implement condense-lists-inside? That's easy,

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

做什么?为什么condense当然是！记住，我们想象我们已经拥有了它.只要得到了它想要得到的东西，它就会生产出它打算生产的东西.也就是说，给定一个原子或一个列表(其中可能有嵌套的列表)，它将产生一个数字.

Do what? Why, condense, of course! Remember, we imagine we have it already. As long as it gets what it's meant to get, it shall produce what it is designed to produce. Namely, given an atom or a list (with possibly nested lists inside), it will produce a number.

因此，现在填写空白并进行简化.尤其要检查您是否真的需要all-atoms检查.

So now, fill in the blanks, and simplify. In particular, see whether you really need the all-atoms check.

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

edit: actually, using typecase was an unfortunate choice, as it treats NIL as LIST. We need to treat NIL differently, to return a "zero value" instead. So it's better to use the usual (cond ((null x) ...) ((numberp x) ...) ((listp x) ...) ... ) construct.

关于您的新代码:您已经犯了错误:要处理(mapcar #'condense x)之后返回的原子列表，我们有一个函数calculate可以执行此操作，无需回溯至condense本身.当在那里替换calculate时，很明显，根本不需要检查all-atoms；它只是一种教学手段，可以简化代码的开发. :)可以在开发时做出多余的选择，如果我们随后简化它们， 之后 ，我们已经达到了 正确性 ！

About your new code: you've erred: to process the list of atoms returned after (mapcar #'condense x), we have a function calculate that does that, no need to go so far back as to condense itself. When you substitute calculate there, it will become evident that the check for all-atoms is not needed at all; it was only a pedagogical device, to ease the development of the code. :) It is OK to make superfluous choices when we develop, if we then simplify them away, after we've achieved the goal of correctness!

但是，取消all-atoms检查将破坏您的要求#2.计算将如下进行

But, removing the all-atoms check will break your requirement #2. The calculation will then proceed as follows

(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检查的代码将严格按级别进行.

I.e. it'll proceed in left-to-right fashion instead of the from the deepest-nested level out. Imagining the nested list as a tree (which it is), this would "munch" on the tree from its deepest left corner up and to the right; the code with all-atoms check would proceed strictly by the levels up.

所以最终的简化代码是:

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

备注: 查看最后的还原序列插图，出现了清晰的画面-用替换自变量 tree 和 calculate 应用程序.这是 折叠 ，就像在树上而不是在纯列表上一样，如reduce一样.

a remark: Looking at that last illustration of reduction sequence, a clear picture emerges - of replacing each node in the argument tree with a calculate application. That is a clear case of folding, just such that is done over a tree instead of a plain list, as reduce is.

这可以直接用所谓的"car-cdr递归"进行编码，在对car和cdr组件进行递归调用的两个结果上，使用组合函数f替换每个cons单元格的单元格:

This can be directly coded with what's known as "car-cdr recursion", replacing each cons cell with an application of a combining function f on two results of recursive calls into car and cdr components of the cell:

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

如您所见，此版本是高度递归的，并不是很好.

As you can see this version is highly recursive, which is not that good.

这篇关于为任务形成Lisp代码-与扁平化列表方法有关的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！