# beginner Scheme/Lisp learner :)

This topic is 4910 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

hey guys, i'll be learning Scheme/Lisp this semester but i can already tell i'll need help with this stuff. the teacher has been going over 'car', 'cudr', and 'cons' and using them with lists in DrScheme. I'm not sure if I even understand the definitions, so while I'm also looking it up on the book, it'd be nice to learn from you guys in here (though it seems I may not get replies; seems heavy on C++ here!). if i get a few replies, i may post a couple of problems that the teacher gave us permission to practice/share with others. i'm sure i'll need help ;) anyways, let the fun begin.

##### Share on other sites
Um. You didn't post a question...

So, hi. What don't you get?

##### Share on other sites
ah sorry. i had wanted definitions of cdr, cons, and car but i just looked 'em up.
ok i'll post a question here:
Write the simple recursive procedure 'count' that returns the number of elements in a list.
> (count (list 2 2 2 2)
4

##### Share on other sites
Quote:
 Original post by sspeedyah sorry. i had wanted definitions of cdr, cons, and car but i just looked 'em up.ok i'll post a question here:Write the simple recursive procedure 'count' that returns the number of elements in a list.> (count (list 2 2 2 2)4

That's a homework problem, not a question.

##### Share on other sites
Quote:
 Original post by RussellThat's a homework problem, not a question.

Yeah. Just in case this isn't clear. Try to answer the question yourself, and then see what you can't figure out.

##### Share on other sites
(define count  (lambda (lst kollect)    (if (null? lst)        (kollect 0)        (count (cdr lst) (lambda (n) (kollect (+ 1 n)))))))

If he turns that in his teacher will stab him.

##### Share on other sites
gee thanks anonymous poster. i'd love to be stabbed--Not.
anyways, didn't mean to come off as I just want an answer (I realize I won't be learning crap).

the book talks about Fibonacci numbers and defines it into a recursive procedure (for computing Fibonacci numbers). i guess what's disturbing me (and i know this sounds stupid) but the def. of (fib n) calls itself in its own definition
(+ (fib(-n 1)) (fib (-n 2))). how does it know what to do if in its own definition it calls itself?

and for the count thing, i just keep staring at it. i don't know where to begin. any hints would be nice. the only thing i have down is:
(define (count alist)
(if (null? alist)
;i know here that alist is empty, so count should be 0

i don't know how to state that comment, or how i would call the function recursively to keep checking for numbers in the list and to count 'em.

beginner blues. hope my questions make sense. please keep in mind that i just started out.

##### Share on other sites
What is the count of an empty list? Suppose you have count-k which will return the count for lists with size less than or equal to k. How would you use count-k to complete the definition of count? That is, if given a function to compute the length of a k-length list, how do you compute the length of a k+1-length list?

You have two problems: 1) solve the easy case, 2) solve the induction case.

##### Share on other sites
You have the part about the count of '() being 0 correct, now try to express the count of a non-empty list in the count of the cdr (all except the first element) of that list.

About functions calling themselves, don't worry too much about it, it works. The identifiers you use inside functions are not actually used until the function is called, so it can safely call itself - by the time it executes the define statement will have finished and thus the function name will be correctly bound to the function.

##### Share on other sites
I take it you know about htdp.org

##### Share on other sites
Quote:
 Original post by marijnhAbout functions calling themselves, don't worry too much about it, it works. The identifiers you use inside functions are not actually used until the function is called, so it can safely call itself - by the time it executes the define statement will have finished and thus the function name will be correctly bound to the function.

Actually the recursive call is bound to an intermediate value, which is later bound to the actual entry point of the function. In functional languages this is generally known as the imperative Y-combinator, or in Scheme the imperative letrec.

##### Share on other sites
Exactly. Recursion works basically the same way in Scheme or Lisp as it does in a C-family language; it's just that the design of Scheme and Lisp encourages you to use recursion more often. Each invocation of a function gets its own set of variables on the stack, and it doesn't matter if the invocation of the function which called the current invocation, was an invocation of the same function.

From what you have so far:

(define (count alist)
(if (null? alist)
;i know here that alist is empty, so count should be 0

This is the syntax for an if:

(if condition true-expression false-expression)

Now, an expression can be any list or single item that's recognized. When this is evaluated, the parser sees 'if', then grabs the next expression, the 'condition', and evaluates it. If it evaluates true, then it will evaluate the true-expression, and the result of evaluation there becomes the result of evaluating the whole thing. Similarly for the false-expression if the condition evaluates false.

So, for the true-expression, you want to put the thing that you want to get out when you write (count foo) and foo is empty. You know what that thing is, you just said it.

For the false expression, you know the list is not empty. Here's a hint: given that list is not empty, how does the size of (cdr list) compare to the size of list? Ok, so for the false expression, you want an expression that somehow involves the size of (cdr list). Assume for a moment that your procedure already worked. How would you ask it for the size of (cdr list)? Now, given that, how do you create the size of list?

To the AP: Cute example there with the use of kollect. But it looks to me like the base case is going to return 1 for an empty list instead of 0, and wouldn't you need to supply the kollect lambda as an argument when you first call (count)?

##### Share on other sites
Petewood mentioned the excellent book "How To Design Programs". I would also like to point out the slightly more advanced but also very good Structure and Interpretation of Computer Programs, also known as "The Wizard Book."

Also, it might be worth mentioning the recently opened Scheme Cookbook site.

##### Share on other sites
Quote:
 Original post by sspeedythe book talks about Fibonacci numbers and defines it into a recursive procedure (for computing Fibonacci numbers). i guess what's disturbing me (and i know this sounds stupid) but the def. of (fib n) calls itself in its own definition

Yep, that's what recursion *is*. ;)
It's also a very big part of languages like Scheme
As have been said, the point about recursion is that the function will call itself over and over with slightly smaller/simpler input, until it reaches a base case that's easy to handle.

Another (and in my opinion simpler) example is the factorial function, n!
In case you don't know, 7! = 7*6*5*4*3*2*1
That could be done like this in Scheme (It could be done similarly in Java or C++ or any other language. They all support recursion):
(define (fac n) (if (zero? n)   (1)   (* n (fac (- n 1)) ))

It checks whether n is 0. If so, it just returns 1.
If not, it calls itself with a smaller n, multiplies with n *and uses the result as return value*. So sooner or later, it will have to reach n=0, and can stop the recursion.
(unless you give it a negative n. Then you're just screwed :D)
Thats basically what recursion boils down to. The function calls itself until it reaches some very simple input that can be handled directly.

I know, it's a good source of headaches if you haven't used it before. :)
Only one cure... Solve some exercises about it.
Run the above code by hand. What happens if you call the function with, say, 5 as argument? Write it up, and every time you get to the recursive function call, insert a copy of the function body (although with the new value for n).
Sooner or later, you'll reach the base case, where it just returns 1 instead of calling itself recursively. Once the innermost call has returned, replace that function call by it's return value, and suddenly, voila, you can calculate the return value of the next function.

Try going through all that by hand.

Zahlman did a pretty good write-up on your count problem. So I'll just be brief and add a few pointers on how to return values (Seems you're not sure how that works):
Here's what you have:
(define (count alist)  (if (null? alist)     ;i know here that alist is empty, so count should be 0

Right, if it's empty, you know count is 0.
So, how to return 0 if the list is empty?

Scheme is really simple in that respect. If it runs into a value, then that's what is returned. If it runs into an expression, then it computes that, and returns the result. So, if you want to return 0, you just insert 0 instead of the comment.
If the list is empty, the if statement will send you to the 0, which is a value that can be returned.
If the list isn't empty, then whatever is in the expression following 0 will be returned. This might require some calculations and function calls first, but whatever ends up on that position, will be returned.)
Conceptually, you can replace each expression with its return value, and then look at the resulting expression. For example, look at this:

(* 1 (+ 2 3))
Ok, so first, you run into an expression involving multiplication. That can't be returned directly, so you'll have to calculate the result. That means you take 1 and... Another expression. You can't multiply 1 with that, so leave that, and concentrate on the new expression. That says take 2 and add 3 to it. That is easy enough. The return value is 5.

So, insert that instead of the offending expression:
(* 1 5)
Now, we can resume where we left off. You take 1 and 5, and multiply them. That's easy enough too. So replace the expression by the result:
5
And hey, that's just a number. We can return that.
So, the return value is 5.

In the above example, I only used + and *, but it's the exact same thing for your own functions (or for if-statements). If you run into something like
(1 + (count x)) then you'll need to call count on x, and when that is done, insert the return value instead of this. Now you can calculate 1 + <the return value>, and use that as the return value for this expression.
If you run into something like
(1 + (if (whatever) 7 2) then calculate the value of the if-statement, which is either 7 or 2 in this case, then return that, and you can add the 1 to that to get the final return value. It's really just copy/paste work. For each expression, calculate the result, and paste that in instead of the expression.

##### Share on other sites
Quote:
 Original post by SpoonsterIn the above example, I only used + and *, but it's the exact same thing for your own functions (or for if-statements). If you run into something like (+ 1 (count x)) then you'll need to call count on x, and when that is done, insert the return value instead of this. Now you can calculate 1 + , and use that as the return value for this expression.If you run into something like(+ 1 (if (whatever) 7 2) then calculate the value of the if-statement, which is either 7 or 2 in this case, then return that, and you can add the 1 to that to get the final return value. It's really just copy/paste work. For each expression, calculate the result, and paste that in instead of the expression.

^^

Although IIRC Common Lisp also defines a "1+" operator (note this is a single token) for the common case of incrementing by one.

##### Share on other sites
Quote:
 Original post by ZahlmanExactly. Recursion works basically the same way in Scheme or Lisp as it does in a C-family language; it's just that the design of Scheme and Lisp encourages you to use recursion more often. Each invocation of a function gets its own set of variables on the stack, and it doesn't matter if the invocation of the function which called the current invocation, was an invocation of the same function.

Scheme stores variables in heap allocated continuations.

Quote:
 To the AP: Cute example there with the use of kollect. But it looks to me like the base case is going to return 1 for an empty list instead of 0, and wouldn't you need to supply the kollect lambda as an argument when you first call (count)?

(count '() (lambda (k) k)) ; -> 0

If you don't like the system stack, kollect your own.