CODEWITHSUNDEEP
recursionschemelispracket
Alex_adl04
Alex_adl04

Reputation: 560

How is add1 being used in this Racket program?

I am trying to understand how add1 is being used in this recursion example:

(define (my-length a-list)
  (if (empty? a-list)
      0
      (add1(my-length (rest a-list)))))

If given (my-list '(1 2 3 4)) the program will return the number 4.

I understand that after each iteration of the function my-lenght the code will take apart the list until the list is empty. What I don't understand is how is it that (add1) adds each iteration to the function.

Upvotes: 0

Views: 475

Answers (4)

ಠ_ಠ
ಠ_ಠ

Reputation: 3078

For the sake of another explanation:

This is where we start

(my-length '(a b c d))

By filling in the argument into the function, that turns into

(if (empty? '(a b c d))
  0
  (add1 (my-length (rest '(a b c d)))))

Obviously, '(a b c d) isn't empty. So the "else" case of the if is evaluated:

(add1 (my-length (rest '(a b c d))))
(add1 (my-length '(b c d)))

Now, what does (my-length '(b c d)) mean? Well, if we copy paste the body of the function into our last line, we get:

(add1 (if (empty? '(b c d))
        0
        (add1 (my-length (rest '(b c d))))))

Continuing...

(add1 (add1 (my-length (rest '(b c d)))))
(add1 (add1 (my-length '(c d))))

This continues until we get an empty list:

(add1 (add1 (add1 (add1 (if (empty? '())
                              0
                              (add1 (my-length (rest '()))))))))

'() is empty, so the if statement returns a 0:

(add1 (add1 (add1 (add1 0))))
(add1 (add1 (add1 1)))
(add1 (add1 2))
(add1 3)
4

It's like we're diving into the function further and further, because for each step we take, we need to go one more to actually evaluate what we have.

How is this different from (add1 '(a b c d))? You can see from how the evaluation played out that add1 was never actually applied to a, b, c or d. We never even checked to see what was in the list. You could've had a list of four lists, that each contained lists of lists, and it would evaluate all the same.

Specifically, saying (add1 '(a b c d)) is like saying "What's 1 plus strawberry?", while your function is more like:

"How many things are in this list?"

"Well, if you don't see anything on top ((first my-list)), then there's definitely none."

"Okay, well...I see an "a" on top!"

"Nice! Take it out. That's at least 1 in the list."

"Okay, but how many are in the rest?"

"How about we try the same thing again? Just keep taking items out from the top of the list until the list is empty. Then, we'll put it back together, and count as we go."

"Okay, I've taken them all out. I'm going to put them back in now: d, that's 1; c, that's 2; b, that's 3; and a, that makes 4!"

"There you go, 4 in the list!"

Upvotes: 1

uselpa
uselpa

Reputation: 18917

The evaluation is as follows:

   (my-list '(1 2 3 4))
-> (add1 (my-list '(2 3 4)))
-> (add1 (add1 (my-list '(3 4))))
-> (add1 (add1 (add1 (my-list '(4)))))
-> (add1 (add1 (add1 (add1 (my-list '())))))
-> (add1 (add1 (add1 (add1 0))))
-> (add1 (add1 (add1 1)))
-> (add1 (add1 2))
-> (add1 3)
-> 4

Upvotes: 0

Metaxal
Metaxal

Reputation: 1113

If your problem is recursion, I suggest you trace the repeated calls to my-length. For example in DrRacket, write the following in the definition window:

#lang racket

(require racket/trace)

(define (my-length a-list)
  (if (empty? a-list)
      0
      (add1(my-length (rest a-list)))))

(trace my-length)
(my-length '(a b c d))

Hit Run and observe:

>(my-length '(a b c d))
> (my-length '(b c d))
> >(my-length '(c d))
> > (my-length '(d))
> > >(my-length '())
< < <0
< < 1
< <2
< 3
<4
4

You can see that (my-length '(a b c d)) calls (my-length '(b c d)) (because that's what (rest '(a b c d)) is), which calls (my-length '(c d)) and so on. When (my-length '()) is called, it returns 0 (first branch of the if). This return value is given (returned) to the previous call, that of (my-length '(d)), which add1s to it, and so returns 1. This latter return value is returned to (my-length '(c d)), which returns 2 and so on until (my-length '(a b c d)) which finally returns 4.

The crucial point here is that add1 is apply to the return value of the recursive call, and thus has to wait for this call to return before being able to do something with this return value. In other words, the add1s are applied in reverse order compared to how the list is processed.

See racket/trace for more info and examples.

Upvotes: 1

Barmar
Barmar

Reputation: 780818

add1 adds 1 to its argument and returns that sum. So if the length of the rest of the list is 3, (add1 (my-length (rest a-list))) will add 1 to 3 and return 4.

In the base case of an empty list, my-length returns 0.

(my-length '(4)) calls (my-length '()) in the recursion, which returns 0, then calls add1 on this to return 1.

(my-length '(3 4)) calls (my-length '(4)) in the recursion. As stated above, this returns 1, it then calls add1 on this, which returns 2.

and so on.

Upvotes: 0

Related Questions