#-(and)" P05 (*) Reverse a list. " ;; The naive recursive solution, O(n²): (defun naive-recursive-reverse (list) (if (endp list) '() (append (naive-recursive-reverse (rest list)) (cons (first list) '())))) ;; A tail-recursive solution (with accumulator): (defun recursive-reverse (list) (labels ((rev (list acc) (if (endp list) acc (rev (rest list) (cons (first list) acc))))) (rev list '()))) ;; An iterative solution: (defun iterative-reverse-do (list) (let ((acc '())) (do ((current list (rest current))) ((endp current) acc) (setf acc (cons (first current) acc))))) (defun iterative-reverse-loop (list) (loop :with result = '() :for item :in list :do (push item result) :finally (return result))) ;; The smartass, Common Lisp solution: (defun my-reverse (list) (reverse list)) ;; (mapcar (lambda (fun) (mapcar fun '(() (a) (a b) (a b c)))) ;; (list (function iterative-reverse-do) ;; (function iterative-reverse-loop) ;; (function naive-recursive-reverse) ;; (function recursive-reverse) ;; (function my-reverse))) ;; --> ((NIL (A) (B A) (C B A)) ;; (NIL (A) (B A) (C B A)) ;; (NIL (A) (B A) (C B A)) ;; (NIL (A) (B A) (C B A)) ;; (NIL (A) (B A) (C B A))) ;; A tail-recursive solution for the reversing of the list in place. ;; Notice that cl:nreverse may be implemented without reusing the ;; input list, cl:nreverse may just call cl:reverse. (defun my-nreverse (list) (labels ((list-reverse (reverse list) (if (null list) reverse (let ((rest (cdr list))) (setf (cdr list) reverse) (list-reverse list rest))))) (list-reverse nil list))) ;; (let* ((list (list 1 2 3 4)) ;; (reversed (my-nreverse list))) ;; (values list reversed)) ;; --> (1) ;; (4 3 2 1) ;;;; THE END ;;;;