Sign in to follow this  

beginner Scheme/Lisp learner :)

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

If you intended to correct an error in the post then please contact us.

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 this post


Link to post
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 this post


Link to post
Share on other sites
Quote:
Original post by sspeedy
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


That's a homework problem, not a question.

Share this post


Link to post
Share on other sites
Quote:
Original post by Russell
That'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.

Then ask us. after showing your current attempt at the solution.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster

(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 this post


Link to post
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 this post


Link to post
Share on other sites
Guest Anonymous Poster
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 this post


Link to post
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 this post


Link to post
Share on other sites
Guest Anonymous Poster
Quote:
Original post by marijnh
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.


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 this post


Link to post
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 this post


Link to post
Share on other sites
Quote:
Original post by sspeedy
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

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 this post


Link to post
Share on other sites
Quote:
Original post by Spoonster
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.


^^

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

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Quote:
Original post by Zahlman
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.


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.

Share this post


Link to post
Share on other sites

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

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this