Nested List Issue in Lisp

Question

So I have to write a method that takes in a list like (nested '(4 5 2 8)) and returns (4 (5 () 2) 8).

I figured I needed to write 3 supporting methods to accomplish this. The first gets the size of the list:

(define (sizeList L)
   (if (null? L) 0
      (+ 1 (sizeList (cdr L)))))

 input : (sizeList '(1 2 3 4 5 6 7))
 output: 7

The second drops elements from the list:

 (define (drop n L)
   (if (= (- n 1) 0) L
      (drop (- n 1) (cdr L))))

 input : (drop 5 '(1 2 3 4 5 6 7))
 output: (5 6 7)

The third removes the last element of a list:

 (define (remLast E)
     (if (null? (cdr E)) '()
        (cons (car E) (remLast (cdr E)))))

 input : (remLast '(1 2 3 4 5 6 7))
 output: (1 2 3 4 5 6)

For the nested method I think I need to do the car of the first element, then recurse with the drop, and then remove the last element but for the life of me I can't figure out how to do it or maybe Im just continually messing up the parenthesis? Any ideas?

if (= (- n 1) 0) can be written more simply as if (= n 1) — Barmar
I don't see how any of these functions for dropping elements from the list are relevant. You just need to step through the list, adding the elements to a result list in the proper fashion. For the first half of the input list you should be creating new lists that are nested inside the previous list. For the second half you append to the end of the list at that level. — Barmar
When you're designing a recursive procedure, start with the base case, in this case an empty list. Then figure out how the next larger case is related to that. — Barmar

Renzo Renzo · Accepted Answer · 2016-10-30T14:13:04

Various recursive solutions are possible, but the problem is that the more intuitive ones have a very bad performance, since they have a cost that depends on the square of the size of the input list.

Consider for instance this simple solution:

; return a copy of list l without the last element
(define (butlast l)
  (cond ((null? l) '())
        ((null? (cdr l)) '())
        (else (cons (car l) (butlast (cdr l))))))

; return the last element of list l
(define (last l)
  (cond ((null? l) '())
        ((null? (cdr l)) (car l))
        (else (last (cdr l)))))

; nest a linear list
(define (nested l)
  (cond ((null? l) '())
        ((null? (cdr l)) l)
        (else (list (car l) (nested (butlast (cdr l))) (last l)))))

At each recursive call of nested, there is a call to butlast and a call to last: this means that for each element in the first half of the list we must scan twice the list, and this requires a number of operations of order O(n²).

Is it possible to find a recursive solution with a number of operations that grows only linearly with the size of the list? The answer is yes, and the key to this solution is to reverse the list, and work in parallel on both the list and its reverse, through an auxiliary function that gets one element from both the lists and recurs on their cdr, and using at the same time a counter to stop the processing when the first halves of both lists have been considered. Here is a possible implementation of this algorithm:

(define (nested l)
  (define (aux l lr n)
    (cond ((= n 0) '())
          ((= n 1) (list (car l)))
          (else (list (car l) (aux (cdr l) (cdr lr) (- n 2)) (car lr)))))
  (aux l (reverse l) (length l)))

Note that the parameter n starts from (length l) and is decreased by 2 at each recursion: this allows to manage both the cases of a list with an even or odd number of elements. reverse is the primitive function that reverses a list, but if you cannot use this primitive function you can implement it with a recursive algorithm in the following way:

(define (reverse l)
  (define (aux first-list second-list)
    (if (null? first-list)
        second-list
        (aux (cdr first-list) (cons (car first-list) second-list))))
  (aux l '()))

Nested List Issue in Lisp

1 Answers