CODEWITHSUNDEEP
racket
user13017933
user13017933

Reputation: 31

How does this reverse list function work in Dr. Racket?

I am using Dr. Racket - Advanced Student Lanaguage. I was looking to make a function that reverses a list. I know there is already the reverse function in Dr. Racket, but I am trying to understand things and work it out. Anyways, I can't understand how this function actually works. From what I understand is that it takes the first element in a list and appends it. I don't understand to what list it is appended to, and how does appending the first letter of the list work? To me it seems like it would just create the same list ("a" "b" "c" "d"). I am assuming that append means attaching an element to the end of a list. (list "a") (list "a" "b") (list "a" "b" "c") (list "a" "b" "c" "d")

Again, my questions are:

  1. What list is the reversed list appended to? (e.x. LOL or lst?)
  2. How is it actually reversing the list?
(define LOL (list "a" "b" "c" "d"))


(check-expect (reverse-list empty) empty)
(check-expect (reverse-list LOL) (list "d" "c" "b" "a")) 

(define (reverse-list lst)
  (if (null? lst) empty
      (append (reverse-list (cdr lst)) (list (car lst)))))

I tried playing with the debug function, but can't seem to understand how it works.

Upvotes: 1

Views: 267

Answers (2)

coredump
coredump

Reputation: 38967

The puzzling part of the code is:

(append (reverse-list (cdr lst))
        (list (car lst)))

You are appending two lists:

  • (reverse-list (cdr lst))
  • (list (car lst))

Let's assume that reverse-list works and actually reverses a list. So we rely on the fact that reverse-list takes a list, and reverse it.

If your input list is (1 2 3), then (cdr list) is (2 3), and (reverse-list (cdr list)) is (3 2).

The second term for append is a list constructor (list (car list)), which in our example would be (list 1), which evaluates to a list of a single element (1).

You can now append them together, which gives (3 2 1), which is indeed the reverse of your initial list.

Upvotes: 1

Sylwester
Sylwester

Reputation: 48775

Start with the simplest lists. Try it like this:

(reverse-list '())    ; goes though base case ok, => ()
(reverse-list '(1))   ; => (append (reverse-list '()) (list 1))
(reverse-list '(2 1)) ; => (append (reverse-list '(1)) (list 2))

Now in the last example you know (reverse-list '(1)) is (1) so the final would be (append '(1) '(2)) which gives (1 2) which happens to be the reverse. You can continue by adding one more element:

(reverse-list '(3 2 1))
; => (append (reverse-list '(2 1)) (list 3))
; => (append '(1 2) '(3))
; ==> (1 2 3)

Upvotes: 0

Related Questions