Trying to make my own reverse function

[Yves S. Garret]

Hi, in my quest of becoming a better lisp programmer. I figured that I should try to make a reverse function. This is what I have now:

================================================
(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?

[Nils M Holm]

Yves S. Garret <yoursurr...@gmail.com> wrote:
> ================================================
> (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?

Okay, here are a few hints.

- 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

[Kaz Kylheku]

On 2012-09-25, Yves S. Garret <yoursurr...@gmail.com> wrote:
> Hi, in my quest of becoming a better lisp programmer. I figured that I should try to make a reverse function. This is what I have now:
>
>================================================
> (defun custom-reverse(list-to-reverse)
> (if (equal (cdr list-to-reverse) nil)

equal is a big gun for just testing for nil. eq will do. But more importantly,
we have two equivalent functions for testing for nil: the not function and the
null function.

(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.

> (car list-to-reverse)

If the list has length 1 (confirmed by (cdr list) being nil) then
you should return that list. Not its car!

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

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

The recursive rule for reversing a list is:

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

[Kaz Kylheku]

On 2012-09-25, Nils M Holm <news...@t3x.org> wrote:
> Yves S. Garret <yoursurr...@gmail.com> wrote:
>> ================================================
>> (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?
>
> Okay, here are a few hints.
>
> - How do you reverse an empty list?
>
> - How do you reverse a non-empty list?

I don't agree. He has the correct idea by treating the empty list and
the list of length one as the same base case.

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.

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

As you can see, the reverse-non-empty-list case has to test for a list of
length one and avoid recursion, otherwise it will cause infinite regress

(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!)

> BTW:
>
> - (EQUAL X NIL) equals (NULL X)
>
> - (CONS X NIL) equals (LIST X)

Back at you:

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

[Nils M Holm]

In article <201209251...@kylheku.com> you wrote:
> 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.

Well, I beg to differ:

(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

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

And it works fine in Scheme, too.

[Kaz Kylheku]

On 2012-09-25, Nils M Holm <news...@t3x.org> wrote:

> In article <201209251...@kylheku.com> you wrote:
>> 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.
>
> Well, I beg to differ:
>
> (DEFUN R (L)
> (IF (NULL L)
> NIL
> (APPEND (R (CDR L)) (LIST (CAR L)))))

You got me.

[Pascal J. Bourguignon]

cl-user> (custom-reverse '(1 2 3 4 5))
((((5 4) 3) 2) 1)


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 {}.

[Nicolas Neuss]

"Pascal J. Bourguignon" <p...@informatimago.com> writes:

> 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

Here is a nice Common Lisp one which is not yet in your list:

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

Nicolas

[Pascal J. Bourguignon]

It is actually, it's the function rev in recursive-reverse.

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)

[Nicolas Neuss]

"Pascal J. Bourguignon" <p...@informatimago.com> writes:

> Nicolas Neuss <last...@scipolis.de> writes:
>
>> "Pascal J. Bourguignon" <p...@informatimago.com> writes:
>>
>>> 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
>>
>> Here is a nice Common Lisp one which is not yet in your list:
>>
>> (defun my-reverse (list &optional reversed)
>> (if (null list)
>> reversed
>> (my-reverse (cdr list)
>> (cons (car list) reversed))))
>
> It is actually, it's the function rev in recursive-reverse.

Yes, but the "nice" was specifically meant to refer to the use of the
optional argument which is not in recursive-reverse:-)

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

I normally do that, too[*]. However, the OP asked specifically about
something using only CONS, CAR and CDR.

Nicolas

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

[Yves S. Garret]

Perhaps I'm needlessly torturing myself in my learning process, but I remember one of my professors teaching me Scheme (many moons ago) and the first homework assignment was the reverse method without using append as well. I was trying to replicate the same thing here as well.

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?

[Yves S. Garret]

Wow. Honestly, I haven't understood everything that you said, I'm on chapter 12 of PCL, so learning about lists as I go.

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.

[Barry Fishman]

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

(reverse-rec (list '() list-to-reverse)))

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

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

First setf is not the way to create a local variable, you need to use let
or let*.

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

[Yves S. Garret]

Yup, that did it. One question, does putting let at the bottom of the function a bad thing? In a sense that the Lisp compiler will reject that?

[Barry Fishman]

On 2012-09-26 12:51:39 EDT, Yves S. Garret wrote:
> Yup, that did it. One question, does putting let at the bottom of the
> function a bad thing? In a sense that the Lisp compiler will reject
> that?

I'm sure I know what you mean. The let does not need to be at the
beginning of a function. It can be use most places you can use an
expression.

--
Barry Fishman

[Yves S. Garret]

Thank you for your help.

[Pascal J. Bourguignon]

"Yves S. Garret" <yoursurr...@gmail.com> writes:

> Yup, that did it. One question, does putting let at the bottom of the
> function a bad thing? In a sense that the Lisp compiler will reject
> that?

Lisp is mostly an orthogonal language: you can combine any feature with
any feature as you want, it will always make something that's accepted
by a lisp compiler. It may not do anything meaningful or useful, but
there are not a lot of invalid forms in lisp. This is because lisp
sources are not sequences of characters, but lisp objects.

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

[Nicolas Neuss]

"Pascal J. Bourguignon" <p...@informatimago.com> writes:

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

However, real Scheme does something different:

$ mzscheme
Welcome to Racket v5.1.3.

> ((list 'lambda '(x) '(* x x)) 42)

procedure application: expected procedure, given: (lambda (x) (* x x)); arguments were: 42

Nicolas

[Pascal J. Bourguignon]

Right, you'd have to insert an eval call here:

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

[bea...@sdf.org]

>Yves S. Garret <yoursurr...@gmail.com> wrote:
>> ================================================
>> (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?

Thought this interesting enough to write something up:

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

[Pascal J. Bourguignon]

bea...@sdf.org writes:

>>Yves S. Garret <yoursurr...@gmail.com> wrote:
>>> ================================================
>>> (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?
>
>
> Thought this interesting enough to write something up:
>
> ;; 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)

Well, ok, but it'll fail on circular lists:


last list &optional n => tail

Arguments and Values:

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

> (let (rlist NIL)
> (dolist (i mylist rlist)
> (push i rlist)))))

Indeed.

> 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.

Check proper-list-p
https://gitorious.org/com-informatimago/com-informatimago/blobs/master/common-lisp/cesarum/list.lisp#line96

[Paul Rubin]

"Yves S. Garret" <yoursurr...@gmail.com> writes:

> Hi, in my quest of becoming a better lisp programmer. I figured that

> I should try to make a reverse function. This is what I have now...

The usual "functional programming" (Scheme) style is to use
a helper function with an accumulator variable. In Common Lisp
you can use a default or optional arg, defaulting to nil:

(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.

[Chris Riesbeck]

On 10/3/2012 10:53 PM, Paul Rubin wrote:
> "Yves S. Garret" <yoursurr...@gmail.com> writes:
>> Hi, in my quest of becoming a better lisp programmer. I figured that
>> I should try to make a reverse function. This is what I have now...
>
> The usual "functional programming" (Scheme) style is to use
> a helper function with an accumulator variable. In Common Lisp
> you can use a default or optional arg, defaulting to nil:
>
> (defun rev (xs &optional accum)
> (if (null xs)
> accum
> (rev (cdr xs) (cons (car xs) accum))))

This is CL's REVAPPEND, except accum is required.

[WJ]

Racket:

(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))]))

[WJ]

Pascal J. Bourguignon wrote:

> 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 '())))

Racket:

(define (rev xs [accum '()])

(if (empty? xs)
accum
(rev (rest xs) (list* (first xs) accum))))

[WJ]

Instead of DARPA CL, let's use a Lispy language.

Racket:

: (foldl cons '() '())
'()
: (foldl cons '() '(2))
'(2)
: (foldl cons '() '(2 3))
'(3 2)
: (foldl cons '() '(2 3 4))
'(4 3 2)