MHB Can anyone help me reverse a list in Lisp without using the reverse function?

[JamesBwoii]

Hi, I'm trying to reverse a list in Common Lisp without using the reverse function.

I've had a go but it's not working. Can anyone help?

(defun my-reverse(my-list)
  (cond
    ((null my-list) nil)
    (t (append (my-reverse(cdr my-list))
	       (list (car my-list))))))

Thanks.

 

[Evgeny.Makarov]

What exactly is not working? I don't have Common Lisp installed, but I tried your code in Emacs Lisp, and it seems to work.

 

[JamesBwoii]

What exactly is not working? I don't have Common Lisp installed, but I tried your code in Emacs Lisp, and it seems to work.

That's strange. I am using Emacs, SBLC and slime. I think it could be because I'm not running it right, I'm new to Lisp and not completely sure how it works.

I'm trying to run it:

(my-reverse (1 2 3))

Here's the error

; SLIME 2014-10-10; compiling (DEFUN MY-REVERSE ...)
CL-USER> (my-reverse (1 2 3))
; in: MY-REVERSE (1 2 3)
;     (1 2 3)
; 
; caught ERROR:
;   illegal function call
; 
; compilation unit finished
;   caught 1 ERROR condition

I assume the illegal function call means that I am calling it wrong but I've called other, simpler, functions I've made that way and they've worked.

Cheers.

 

[Evgeny.Makarov]

The notation [m](f a b c)[/m] in Lisp denotes function application. To interpret it as a list, you need to "deactivate" it, i.e., declare that it is a list constant rather than the result of a function call. This is done using the function [m]quote[/m]. For example, [m](quote (f a b c))[/m] is a list containing three symbols [m]f[/m], [m]a[/m], [m]b[/m] and [m]c[/m]. A shorthand for [m]quote[/m] is the prime [m]'[/m]. So you should invoke your function as [m](my-reverse '(1 2 3))[/m].

 

[JamesBwoii]

The notation [m](f a b c)[/m] in Lisp denotes function application. To interpret it as a list, you need to "deactivate" it, i.e., declare that it is a list constant rather than the result of a function call. This is done using the function [m]quote[/m]. For example, [m](quote (f a b c))[/m] is a list containing three symbols [m]f[/m], [m]a[/m], [m]b[/m] and [m]c[/m]. A shorthand for [m]quote[/m] is the prime [m]'[/m]. So you should invoke your function as [m](my-reverse '(1 2 3))[/m].

Thanks, slight annoyed with myself as I knew that, just had forgotten!

Despite having written it, I needed to look up most of it so am not sure I understand most of it. I think it works like this.

(defun my-reverse(my-list)                         ;define a function with parameter
  (cond                                                     ; essentially an 'if' statement
    ((null my-list) nil)                                  ;empty list is false
    (t (append (my-reverse(cdr my-list))         ;true 
	       (list (car my-list))))))

• Define a function with the paramter 'my-list'
• Essentially an if statement
• Empty list is false
• True. Append(Recursively go back to the function with cdr, so the list without the first element.
• This is what I'm not sure about. Car of the list is the first element so is 'list' being added to with the first element? What I'm not sure of is how it gets to that bit as won't the recursion keep happening before this part?

 

[Evgeny.Makarov]

[m]cond[/m] is like [m]switch[/m] in C-like languages, but with arbitrary conditions instead of just comparing with constants. The last branch that starts with [m]t[/m] is like the [m]default[/m] clause. It executes always unless some other branch executed before, because the condition of this default branch is always true.

Empty list is false

It is true that in CL the empty list [m]nil[/m] also fulfills the role of the Boolean constant False. (Such conflation is not necessarily a good thing for the clarity of the language semantics.) But here it does not behave as False; it behaves (is returned) as the empty list.

This is what I'm not sure about. Car of the list is the first element so is 'list' being added to with the first element?

Yes. This construction: [m](append ... (list (car my-list)))[/m] is necessary because, I think, there is no built-in function that adds an element to the end of a list (I may be wrong about CL in this), so we have to use [m]append[/m], and it requires both arguments to be lists.

What I'm not sure of is how it gets to that bit as won't the recursion keep happening before this part?

Yes, the recursive call happens before [m]append[/m]. This is a mind-twisting thing about recursion. First, note that the recursion eventually stops because the function is called with smaller and smaller lists. But yes, the complete recursive call (which gives rise to other recursive calls) has to finish before [m]append[/m] is executed.

The correctness of this program is easy to understand: if we denote concatenation by $\cdot$, then $\operatorname{reverse}(x\cdot l)=\operatorname{reverse}(l)\cdot x$. But to trace this program in one's head may be quite difficult. I call this the "magic" aspect of some well-designed programming languages: it is often easier to write a program than to understand how it works.

 

[JamesBwoii]

That makes sense, and you're right, getting my head around recursion is quite difficult.

I've found some code online which reverses a list that has lists in it but I don't quite get it and was hoping that you could explain a bit of it.

(defun my-reverse (l)
  (cond ((null l) nil)
        ((listp (car l)) 
	 (append (my-reverse (cdr l)) 
         (list (my-reverse (car l)))))
        (t
          (append (my-reverse (cdr l)) 
                  (list (car l))))))

What I don't get is this part.

  (cond ((null l) nil)
        ((listp (car l)) 
	 (append (my-reverse (cdr l)) 
         (list (my-reverse (car l)))))

I assume that is the bit which reverse a list inside another list. What I don't understand is that isn't it saying that if the list is empty then it executes the 3 lines of code after it?

Is it then creating a listp with the first element of list l?
Then appending by recursively go back to the function with cdr, so the list without the first element.
Then creating a list by recursively going back to the function with the first element of the list?

I really don't see how that is working.

 

[Evgeny.Makarov]

  (cond ((null l) nil)
        ((listp (car l)) 
	 (append (my-reverse (cdr l)) 
         (list (my-reverse (car l)))))

I assume that is the bit which reverse a list inside another list. What I don't understand is that isn't it saying that if the list is empty then it executes the 3 lines of code after it?

The [m]cond[/m] clause dealing with the case when [m]l[/m] is empty is [m]((null l) nil)[/m]. The next clause handles the case when [m](listp (car l))[/m] is true, i.e., the head of [m]l[/m] is a list. So, if [m]l[/m] is empty, return the empty list. If the head of [m]l[/m] is itself a list, then reverse the tail of [m]l[/m], reverse the head, and add the reversed head as the last element of the reversed tail.