Scheme Question/Help

J

JC0724

Weaksauce
Joined
Oct 11, 2008
Messages
105
;to compute the number of elements in a list.

(define (myListLength Lst)
(if (null? Lst)
0
(+ 1 (myListLength (cdr Lst) ))
)
)


;to compute the sum of elements in a list of numbers

(define (myListSum Lst)
(if (null? Lst)
0
(+ (car Lst) (myListSum (cdr Lst) ))
)
)

I am taking a Scheme class and I was doing well up until this point. My professor handed out some examples and i am having serious trouble understanding them.

I don't get how these functions work?? I don't understand how it is going threw the entire list like a loop but its a IF statement?

I also don't understand how +1 can be added to list since its not a number.

Any insight on this would be greatly appreciated.
 
JC0724 said:
I don't get how these functions work?? I don't understand how it is going threw the entire list like a loop but its a IF statement?
Click to expand...
They're recursive. They work by calling themselves (with a smaller list).

car gives you the first element in the list, and cdr gives you the remainder. i.e. car [1,2,3] = 1 and cdr [1,2,3] = [2,3].

So myListSum [1,2,3] ends up calling myListSum [2,3], which calls myListSum [3], which calls myListSum [], which returns 0 (thanks to that null check). That's how it works its way through the list.

JC0724 said:
I also don't understand how +1 can be added to list since its not a number.
Click to expand...
It's adding 1 to the result of myListLength, which definitely is a number.
 
JC0724 said:
;to compute the number of elements in a list.

(define (myListLength Lst)
(if (null? Lst)
0
(+ 1 (myListLength (cdr Lst) ))
)
)
Click to expand...

From my understanding (and keep in mind that I haven't played with a language like scheme in a long time), the function is working as follows:

If the list Lst is null, the function returns 0. Otherwise, the function returns the expression 1 + myListLength(cdr Lst). In Scheme, cdr takes a cell (a data type with a left and a right pointer) and returns whatever is referenced by the right pointer. Lists in scheme are linked lists, and they're implemented by using the value in the current link as the left pointer in a cell, and the rest of the chain as the right pointer.

The list [4, 8, 7] as a cell-based linked-list:
Code: 
[ | , | ]
 4  [ | , | ]
      8  [ | , | ]
           7  NULL

Therefore, calling cdr on a list returns a sublist containing everything but the first element. The function keeps recursing until there's nothing left in the list (that's what the null check is for), and then it returns 0 and works it's way back up the call stack populating return expressions.

In other words, the function works like so. Let's take the list [4,8,7].

myListLength [4,8,7] will return (1 + myListLength [8,7]), but before we can figure out what that actually is, we need to evaluate myListLength [8,7]. myListLength [8,7] returns (1 + myListLength [7]), and myListLength [7] returns (1 + myListLength []). Since myListLength [] is being evaluated with a null list parameter, it returns 0 (that's what the null check in the if statement is for).

Now that we know the return values in terms of recursive calls, and we know the value of the base step, we can substitute the values in and work back up to the return value of myListLength [4,8,7].

myListLength [4,8,7] = (1 + myListLength[8,7]) = (1 + (1 + myListLength[7])) = (1 + (1 + (1 + myListLength[]))) = (1 + (1 + (1 + (0))) = 3

...and as a syntax tree:

Code: 
myListLength [4,8,7]
          |
          +   
        /    \ 
      1     myListLength [8,7]
                      |   
                      +   
                     /   \ 
                   1    myListLength [7]
                                  |
                                  +
                                /   \
                               1   myListLength []
                                             |
                                             0

Which reduces to the expression tree:

Code: 
             3
              |
             +
           /    \
          1     +
               /    \
              1     +
                  /   \
                1      0

With that in mind, do you think you can figure out how the myListSum function works?
 
Last edited:
JC0724 said:
;to compute the number of elements in a list.

(define (myListLength Lst)
(if (null? Lst)
0
(+ 1 (myListLength (cdr Lst) ))
)
)
Click to expand...

See the bolded text shows where the function calls itself

LuminaryJanitor said:
They're recursive. They work by calling themselves (with a smaller list).
Click to expand...

This is correct. Basically, this function returns 0 if the list is empty. Else it returns 1 + the size of the list AFTER the first element. You definitely have to understand the difference between CAR and CDR. One returns the first element, one returns the element after the first

Another interesting question is why this function doesn't stack overflow when given a large list.
 
thank you, this all makes sense now.

I do have another question. trying to understand how to use cons.

> (cons (cons 1 2) (cons 3 4) )
((1 . 2) 3 . 4)

Why does this not create ( (1.2) . (3.4) )

How can I create that using cons? Am I using cons wrong here?
 
You must log in or register to reply here.
Back
Top