Generating Lisp code for a task associated with a smoothing list method

Question

I'm having trouble writing code for the problem I want to solve. This happens as follows:

~ Purpose: hide the nested list in one number

• If the object is a list, replace the list with the sum of its atoms.
• With nested lists, first smooth out the innermost lists and work there.

Example:

(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 tried to implement a smoothing 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 this gives me errors :(

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

---

UPDATE: JUNE 5, 2012

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

So, here, in this code, my true intention is shown. I have a calculate function that performs a calculation based on the values ​​in a list. This is not necessarily the same operation. In addition, I know that I am returning the absolute value of a number; I did this because I could not find another way to return the number myself. I need to find a way to return a number if lxt is a number. And I got it two times at the bottom, because this is one of the ways that it loops endlessly until it calculates one number. NOTE. This function no longer implements the smoothing function and does not use any of it.

Answer 1

Imagine that you already have your function. What does he get? What should he 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? )) 

What do condense-lists-inside need to do? According to your description, it should condense nested lists inside - each into a number, and leave the atoms intact. Therefore, he will leave a list of numbers. To somehow handle this, we already “have” a function, condense-list-of-atoms , right?

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

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

What? Why, condense , of course! Remember, we assume that we already have this. As long as he receives what he wants to receive, he must produce what he intended for production. Namely, given an atom or list (with possible nested lists inside), it will produce a number.

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

edit: using typecase was a bad choice as it treats NIL as a LIST. We need to look at NIL differently to return a "null value" instead. Therefore, it is better to use the usual construction (cond ((null x) ...) ((numberp x) ...) ((listp x) ...) ... ) .

About your new code: you were mistaken: to process the list of atoms returned after (mapcar #'condense x) , we have a calculate function that does this, we don’t need to go back so far to condense . When you replace calculate there, it will become obvious that checking for all-atoms is not needed at all-atoms ; it was just a pedagogical device to facilitate code development. :) It’s normal to make extra choices when we develop, if we then simplify them, then we have reached the goal of correctness !

But removing the all-atoms check will violate your # 2 requirement. Then the calculation will act 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 

those. he will act from left to right, and not from the deepest nested level. Representing the nested list as a tree (this is it), it “chews” on the tree from its deepest left corner up and to the right; code with the all-atoms tag will be executed strictly upward.

Thus, the final simplified code:

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

note:. Looking at the last illustration of the recovery sequence, a clear image appears - replacing each node in the argument tree with a calculation application. This is an obvious case of folding , just one that runs on the tree instead of a simple list, since reduce is.

This can be directly encoded using the so-called "car-cdr recursion", replacing each cons cell with an application of the union function f with two results of recursive calls to the car and cdr components of the cell:

 (defun condense (x) (reduce-tree x #'+ 0)) (defun reduce-tree (xfz) (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"))))) (gx))) 

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

Answer 2

Is this homework? If yes, check this as such. Some tips:

• Are you sure the "condensation" of the empty list is nil ? (maybe you should return the number?)
• Are you sure that condensation one element is a list? (maybe you should return the number?)
• Are you sure condensation latter case is a list? (you should not return the number)?

In short, how will your condense ever return 28 if all of your return values ​​are lists?

Answer 3

Task: with nested lists, first smooth out the innermost lists and work from there

 sum flatten lists 

To use the amount of REDUCE , not APPLY .

You need a loop to smooth lists. Lisp already provides specialized mapping functions.

A bit more advanced: both sum and smoothing can be done by calling REDUCE .

You can also write recursion without using a higher order function such as APPLY, REDUCE, ... This works a bit more.

Answer 4

This adds an explanation of the mistakes you had, in fact you were close to solving your problem, just a little more effort, and you would understand it correctly.

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

All this is specified for the flatten function.

Answer 5

If your lisp already implements flatten and reduce functions (such as Clojure, which I will use here), you can simply do something like:

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

Otherwise, the naive implementation of these functions may be:

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

and

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

But be sure to check the semantics of the specific lisp you are using. Also, if you are doing reduce and flatten , you can make them tail recursive, which I didn’t do to maintain clarity.

In Common lisp you will do something like:

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

and use the abbreviation instead:

 (defun condense (l) (apply #'+ (flatten l)))