================================================
(defun custom-reverse(list-to-reverse)
  (if (equal (cdr list-to-reverse) nil)
    (car list-to-reverse)
    (cons (custom-reverse (cdr list-to-reverse)) (cons (car list-to-reverse) nil))))
================================================

Now, it doesn't work.  At least not very well.  The problem is what should I return from the method?  Also, and I could be wrong, but is it possible to make a reverse method using car, cdr and cons?

- How do you reverse an empty list?

- How do you reverse a non-empty list?

- Fill in the missing parts:

  (DEFUN R (L)
    (IF (NULL L)
        reverse-empty-list
        reverse-non-empty-list))

- You will get extra points for not using APPEND.

BTW:

- (EQUAL X NIL)  equals  (NULL X)

- (CONS X NIL)   equals  (LIST X)

--
Nils M Holm  < n m h @ t 3 x . o r g >  www.t3x.org

 (if (null (cdr list-to-reverse))
   this
   that)

If you exchange the two cases, you can get rid of the null test:

 (if (cdr list-to-reverse)
   that
   this)

Anyway, list processing case like this must handle the special case
of the list being empty.

The reverse of a one element list is that list itself, not its first item.

   1. If the list is empty or length 1, return it.
   2. Otherwise, set the first item aside, reverse the rest of the
      list and then append the item to the resulting list.

(defun custom-reverse (list)
  (if (rest list) ;; let's use first and rest instead of car and cdr
    (append (custom-reverse (rest list)) (list (first list)))
    list))

The induction can only boostrap from a list of two or more items.

If you recognize only the empty list as a base case, and do not recognize
the length one list as a base case, then you have infinite recursion.  

That is because a list of length one can only be subdivided into a list of
length one and an empty list.  And if your divide-and-conquer function produces
a subdivision of the input which is equal to the entire input, it fails to
divide and conquer.

  (cond
    ((null l) reverse-empty-list)
    ((null (rest l)) reverse-length-one-list)
    (t reverse-longer-list))

But the first two cases can be merged since they return the
same thing and if (null l) is true then (null (rest l)) is also valid and true
true (since Lisp is not S**eme, dammit!)

  (if (not cond) then else)   <==>   (if cond else then)

(DEFUN R (L)
  (IF (NULL L)
      NIL
      (APPEND (R (CDR L)) (LIST (CAR L)))))

(R '(1 2 3)) ==> (3 2 1)
(R '(1))     ==> (1)
(R '())      ==> NIL

--
Nils M Holm  < n m h @ t 3 x . o r g >  www.t3x.org

Yes, there's something wrong.

     (defun custom-reverse (list-to-reverse)
       (if (equal (cdr list-to-reverse) nil)
         (car list-to-reverse)
         (cons (custom-reverse (cdr list-to-reverse))
               (cons (car list-to-reverse) nil))))

The problem you have here is that you don't know exactly how lists are
represented in Lisp.

There's no list data type in lisp; see
http://www.informatimago.com/articles/usenet.html#Lisp-Paradoxes

Lists are represented by chains of cons cells.

Proper lists are either the symbol CL:NIL representing the empty list,
CL:NIL can be read or printed as () too; or a CONS cell where the CAR
contains a first element, and the CDR contains a proper list that is the
rest of the list.

Notice the types:  proper list -->  ( element . rest-of-the-list )

The elements can be of any type, but the rest-of-the-list must be of
type proper list!  So it must be either CL:NIL (empty list = end of the
list), or another cons cell with an element and another proper list,
rest of the list.

The type signature of cons, when used to build a proper list would be:

   (cons t proper-list) --> proper-list

Now you have to be careful because CONS cells can be used to build other
kind of data structures.  For example, binary trees:

   (cons binary-tree binary-tree) --> binary-tree

Dotted lists:

   (cons t dotted-list) --> dotted-list

Circular lists:

   (cons t circular-list) --> circular-list

and more.

But we are considering here only proper lists.

   nil                  --> proper-list
   (cons t proper-list) --> proper-list

Ok, now so what's the problem with your function:

    (defun custom-reverse (list-to-reverse)
      (if (equal (cdr list-to-reverse) nil)
        (car list-to-reverse)
        (cons (custom-reverse (cdr list-to-reverse))
              (cons (car list-to-reverse) nil))))

The type signature of your function should be:

    (custom-reverse proper-list) --> proper-list

You give it a proper list, and it returns a proper list with the
elements in reverse order.

But let's see what it does.

If list-to-reverse is the empty list CL:NIL, also printed/read as (),
then the test is true and (car list-to-reverse) returns () which is a
proper list (right type) and the right result.  The reverse of the empty
list is the empty list.

If list-to-reverse is a list containing one element, eg. (a) then the
test is true too, and (car list-to-reverse) returns the first element of
that list, ie. the symbol A.  This is not a proper list.  Here you have
a first bug.

    cl-user> (custom-reverse '(a))
    a

Let's correct it:

    (defun custom-reverse (list-to-reverse)
      (if (null (cdr list-to-reverse))
         list-to-reverse
         (cons (custom-reverse (cdr list-to-reverse))
               (cons (car list-to-reverse) nil))))

    cl-user> (custom-reverse '(a))
    (a)
    cl-user> (custom-reverse '())
    nil ; = ()
    cl-user> (custom-reverse '(1 2 3 4 5))
    (((((5) 4) 3) 2) 1)

We still have the main bug, but now the result is more consistent.
Let's consider the other case, when the list-to-reverse contains more
than 1 element.

     (cons (custom-reverse (cdr list-to-reverse))
           (cons (car list-to-reverse) nil))

is called. custom-reverse returns a reversed proper list. (car list-to-reverse)
returns the first element.  So that expression is something like:

     (cons reversed/proper-list
           (cons first/element nil))

(cons first/element nil) conses an element to a proper-list therefore it
returns a proper-list all right.

But while the type analysis of:

   (cons reversed/proper-list head/proper-list)

doesn't reveal anything wrong: it takes an element which can be of any
type, reversed/proper-list is good, and a proper-list, and therefore
return a proper-list,  you may still notice that the element we're
putting in the list is not one element from the original list, but a
reversed rest of the list.  So here is the problem.  

You have (b) and (a) and you want to get (b a).  

    (cons '(b) '(a)) --> ((b) a)
    (cons '(e d c b) '(a)) --> ((e d c b) a)

so you can use cons directly to get (b a) or (e d c b a).

What you want indeed is to append the two lists:

   (append proper-list proper-list) --> proper-list

   (append (custom-reverse (cdr list-to-reverse))
           (cons (car list-to-reverse) nil))

    (defun custom-reverse (list-to-reverse)
      (if (null (cdr list-to-reverse))
         list-to-reverse
         (append (custom-reverse (cdr list-to-reverse))
               (cons (car list-to-reverse) nil))))

    cl-user> (mapcar 'custom-reverse '(() (1) (1 2) (1 2 3) (1 2 3 4 5 6 7)))
    (nil (1) (2 1) (3 2 1) (7 6 5 4 3 2 1))

Now using APPEND in reverse is a bad thing, since APPEND is O(n), and
CUSTOM-REVERSE iterates on LIST-TO-REVERSE too, therefore it is O(n²).
Furthermore, APPEND copies all its arguments (but the last), so it will
also cons O(n) cells, and therefore CUSTOM-REVERSE will also cons O(n²)
cells, when the result only has n cells.

You could use NCONC, which is the non-consing version of APPEND, it
modifies all its arguments to concatenate them.  So now you'd cons only
O(n) cells and being recursive, it also use O(n) stack space (so O(n)
space in total), but it is still be O(n²) in time complexity.  

One thing with the above solution is that it uses only one variable:
list-to-reverse.  If you try to imagine another algorithm to reverse a
list in O(n) time and O(n) space, it could be helpful to use more than
one variable.  (This could be an additionnal parameter to a recursive
function, or this could be a local variable to an iterative function).

For more solutions have a look at:

http://www.informatimago.com/develop/lisp/l99/index.html

http://www.informatimago.com/develop/lisp/l99/p05.lisp

--
__Pascal Bourguignon__                     http://www.informatimago.com/
A bad day in () is better than a good day in {}.

(defun my-reverse (list &optional reversed)
  (if (null list)
      reversed
      (my-reverse (cdr list)
                  (cons (car list) reversed))))

Nicolas

Otherwise, when processing lists, one may prefer to use list operators
instead of cons operators:

      list-level            cons-level
      ----------            ----------
      endp                  null
      first                 car
      rest                  cdr
      list*                 cons
      second                cadr
      third                 caddr
      fourth                cadddr
      ----------            ----------

(defun recursive-reverse (list)
  (labels ((rev (list acc)
     (if (endp list)
          acc
          (rev (rest list) (list* (first list) acc)))))
      (rev list '())))

(recursive-reverse '(1 2 3)) --> (3 2 1)

--
__Pascal Bourguignon__                     http://www.informatimago.com/
A bad day in () is better than a good day in {}.

Nicolas

[*] Well, maybe with the exception of ENDP which I don't use (probably
because I seldom recursively iterate over lists).

Long story short, this is my code and the error that I'm getting below when trying to load it in Common Lisp.

; this is the initial function that will set things up for the below method.
(defun custom-reverse2(list-to-reverse)
  ; set things up here so that we will pass in a list of two lists.  The first
  ;   list will store the reversed list -- after processing is done, but for
  ;   the moment is blank -- and the second list is the one that was passed in
  ;   in order to reverse.
  (reverse-rec((list '() list-to-reverse))))

; this method will do the iterating and reversing recursively.
(defun reverse-rec(grand-list)
  ; get the second list in the grand-list and see if it's nil.
  (if (null (car (cdr grand-list)))
    ; if the second list is a nil, then return the reversed list.
    (car grand-list)
    ; otherwise continue reversing the entire thing.
    ((setf new-list (cons (car (car (cdr grand-list))) (car grand-list)))
     (reverse-rec(list new-list (cdr (car (cdr grand-list))))))))

The error:

[110]> (load "test.lisp")
;; Loading file test.lisp ...
*** - SYSTEM::%EXPAND-FORM: (LIST 'NIL LIST-TO-REVERSE) should be a lambda expression
The following restarts are available:
SKIP           :R1      skip (DEFUN CUSTOM-REVERSE2 # ...)
STOP           :R2      stop loading file /home/ashvets/Documents/Development/Lisp/hello-world/test.lisp
ABORT          :R3      Abort main loop

So I can't pass in a nil into reverse-rec?

First of all, thank you very much into the effort that you put in writing this post.  I appreciate it.  I haven't understood everything and I will have to wait (try, fall on my face a couple of times) and learn more about how Lisp handles information.  I accepted the fact that I'll go through this n00bish uncomfortable phase if I would like to gain any sort of mastery of Lisp.

Second of all, I love your website.  I saw the 99 problems link and that's where I'll go to try stuff out and then see how you did things.

And everybody, thank you for your patience and input as I try to learn, quite possibly, the greatest programming language yet to be invented.

You are making thing less readable by not putting a space before (.
Lisp can become easy to read if you don't try to make it look like
some other language.

On 2012-09-26 10:09:44 EDT, Yves S. Garret wrote:

The double parens are usually wrong unless you are using some
macro like let.  (The lack of a space may be making it appear to be
a list inside a function call.)

Second, the '((setf ...', outside of a let, is another case of doubled
left parenthesis and a warning something may be wrong.  Here you are
grouping two statements by putting them in an outer parenthesis:

         ((setf newlist ...) (reverse-rec ...))

You would do that with:

         (progn (setf newlist ...) (reverse-rec ...))

Add considering that the setf is wrong:

         (let ((newlist ...)) (reverse-rec ...))

Also duplicate chains of '(cdr (car ...' are a hint that you need to
choose more meaningful local variable:

;; This method will do the iterating and reversing recursively.
(defun reverse-rec (grand-list)
  (let ((to-list (car grand-list))
        (from-list (car (cdr grand-list))))
    (if (null from-list)
        to-list
        (reverse-rec (list (cons (car from-list) to-list)
                           (cdr from-list))))))

The '(car (cdr grand-list))' could be expressed as (cadr grand-list) or
even (second grand-list).

But would be simpler to rather than create a new grand-list as an
argument to reverse-rec, just pass the lists as separate arguments.

(defun custom-reverse2 (list-to-reverse)
  (reverse-rec '() list-to-reverse))

Then:

(defun reverse-rec (to-list from-list)
    (if (null from-list)
        to-list
        (reverse-rec (cons (car from-list) to-list)
                     (cdr from-list))))

--
Barry Fishman

On 2012-09-26 12:51:39 EDT, Yves S. Garret wrote:

--
Barry Fishman

See:
http://groups.google.com/group/comp.lang.lisp/msg/6ec4dab4a8d57f6e
http://groups.google.com/group/comp.lang.lisp/msg/3050088218d355e5

But then, cons cells are interpreted in Common Lisp as operator
applications.  The car of a cons cell MUST be an operator, that is,
either a symbol, or a cons cell that's a lambda expression.  NO other
object is a valid operator in Common Lisp, and in particular, random
lists are NOT operators!  

      (sin 42)                    ; sin names a function
      (if (= a b) 3 4)            ; if names a special operator
      (dolist (x l) (print x))    ; dolist names a macro
      ((lambda (x) (* x x)) 42)   ; (lambda (x) (* x x)) "names" the
                                  ; function that squares its argument.

      ((list 'lambda '(x) 'x) 42) ; is NOT a valid CL form.

There's no operator named (list 'lambda '(x) 'x).
Even if (list 'lambda '(x) 'x) is a form that evaluates to a lambda
expression that "names" an operator,  (list 'lambda '(x) 'x) itself is
not an operator!  (+ 3 4) _is_ not 7.  (+ 3 4) _evaluates_ to 7.
(+ 3 4) _is_ a list.  (+ 3 4) _evaluates_ to an integer.

That's why you cannot add parentheses (that is, you cannot put conses in
car of conses) around forms.

Remember ( = operator call.

Now of course, there's the special case of special operators and of
macros, which can interpret their subforms differently than CL:EVAL.
For example, CL:LET interprets the second subform, not as a lisp form
(not as an operator call), but as a list of bindings, which can
themselves be lists (of a variable and an optional initial value
expression), and therefore, you can have two open parentheses
there, because they're not operator calls.

         +-- not lisp code, not an operator call!
         |
         v
    (let ((x 1)
          (y 2))
      (+ x y))

    (random-macro (x y z) (z a b))
                  ^       ^
                  |       |
                  +-------+--- we cannot know what those are
                               without knowing the random-macro.
                               data? code?  Only random-macro knows.

You can even write a macro that interprets the sexps as in scheme:

    (scheme ((list 'lambda '(x) '(* x x)) 42)) --> 1764

--
__Pascal Bourguignon__                     http://www.informatimago.com/
A bad day in () is better than a good day in {}.

$ mzscheme
Welcome to Racket v5.1.3.

Nicolas

    1:=>  ((eval (list 'lambda '(x) '(* x x)) '()) 42)
    1764

--
__Pascal Bourguignon__                     http://www.informatimago.com/
A bad day in () is better than a good day in {}.

;; myreverse - simply mimic the REVERSE command
(defun myreverse (mylist)
  (if (cdr (last mylist))  ; proper list criteria: (cdr (last mylist)) = NIL
    (error "~&~A is not of type SEQUENCE.~%" mylist)
    (let (rlist NIL)
      (dolist (i mylist rlist)
        (push i rlist)))))

I initially used FLET to define a SEQUENCE-P but the test is simple enough
to omit.  The ERROR message is same as retruned from REVERSE when fed an
improper list.

Have fun,

beaker

    last list &optional n => tail

    Arguments and Values:

    list---a list, which might be a dotted list but must not be a circular list.

--
__Pascal Bourguignon__                     http://www.informatimago.com/
A bad day in () is better than a good day in {}.

   (defun rev (xs &optional accum)
      (if (null xs)
             accum
          (rev (cdr xs) (cons (car xs) accum))))

The above simply builds up "accum" by peeling off elements of xs one by
one and consing them to the front of accum, so they end up in reversed
order.  When they are all peeled off, accum is the return value.  The
function is tail recursive and should avoid stack buildup with any
reasonable compiler.

(define (rev xs [accum '()])
  (if (null? xs)
    accum
    (rev (cdr xs) (cons (car xs) accum))))

Using pattern-matching:

(define (rev xs [accum '()])
  (match xs
    ['()  accum]
    [(list hd tl ...) (rev tl (cons hd accum))]))

(define (rev xs [accum '()])
  (if (empty? xs)
    accum
    (rev (rest xs) (list* (first xs) accum))))