Deep inverse for trees in a circuit (Lisp)

Question

I have a deep reverse for the basic tree data structure in Schema

(define (deep-reverse t) (cond ((null? t) '()) ((not (pair? t)) t) (else (cons (deep-reverse (cdr t)) (deep-reverse (car t)))))) (define stree (cons (list 1 2) (list 3 4))) 1 ]=> (deep-reverse stree) ;Value: (((() . 4) . 3) (() . 2) . 1) 

I feel cleaner, the best result:

 (4 3 (2 1)) 

Can someone give some recommendations as to where I am mistaken in my deep inverse function? Thanks.

Answer 1

It’s better to break the task down into simple operations, rather than try to do it all at once. What you want to achieve can be described as follows: flip the current list, then flip all the signatures in it (or vice versa, the order of the two steps does not matter. I choose this order because it leads to a better formatting of the source code) .

Now the standard library already has a function for simply changing the list, reverse . So, all you have to do is combine this with recursion on those elements that are sublists:

 (define (deep-reverse t) (map (lambda (x) (if (list? x) (deep-reverse x) x)) (reverse t))) 

Answer 2

Try the following:

 (define (deep-reverse t) (let loop ((tt) (acc '())) (cond ((null? t) acc) ((not (pair? t)) t) (else (loop (cdr t) (cons (loop (car t) '()) acc)))))) 

Name it as follows:

 (define stree (cons (list 1 2) (list 3 4))) (deep-reverse stree) > (4 3 (2 1)) 

To create an inverted list, one method is to accumulate the response in the parameter (usually I call it acc ). Since we are working on a list of lists, recursion must be called on both the car part and the cdr in the list. Finally, I use named let as a shorthand to avoid creating an additional function, but the same result can be obtained by defining a helper function with two parameters: a tree and a battery:

 (define (deep-reverse t) (aux t '())) (define (aux t acc) (cond ((null? t) acc) ((not (pair? t)) t) (else (aux (cdr t) (cons (aux (car t) '()) acc))))) 

Answer 3

I think it’s better to cancel the list based on its number of elements: the reverse list is empty, one list of elements is also returned, more than 1 element is a concatenation of the reverse direction of the tail and head.

 (defun deep-reverse (tree) (cond ((zerop (length tree)) nil) ((and (= 1 (length tree)) (atom (car tree))) tree) ((consp (car tree)) (append (deep-reverse (cdr tree)) (list (deep-reverse (car tree))))) (t (append (deep-reverse (cdr tree)) (list (car tree))))))