hey guys, I have a test on this stuff and I've answered most of the ?s but there still are a few I'm not sure about. So before going to bed, I thought I'd post here to see if anyone can post answers and explain them so I understand them (please don't rag on me, these aren't hw ?s, but we need to know the answers to such ?s in case they're on the stinkin' test). Anyway, here we go: 1. (define (delete a b) (cond ((= b 0) 1) ((even? b) (delete a (/ b 2))) (else (delete a (- b 1))))) Exactly how many calls to delete are generated by the call (delete 21, 31), inlucding the original call? 2. (define test-let (lambda () (define (f) (display "woof") 7) (let ((n (f))) (+ n 5) (+ n 2)))) (define test-define (lambda () (define (f) (display "woof") 7) (+ (f) 5) (+ (f) 2))) Write an example call to each one. Below each call, write what is displayed (approximately) and what is returned (exactly by each call. Did you write all 6 things? (I know you can test them by enter > (test-let) woof 9 >(test-define) woofwoof 9 I don't complete understand the outputs...I don't know what is 'returned' at all). 3. Use one or more procedures from the sequence tool kit (filter, enumerate, accumulate, map) to write a single expression that returns the PRODUCT of all elements of the series {0,5 10 15 ... n} for some pre-defined variable n. You're provided only n, not a list to use as input. (I can't get this right :( ) 4. Represent the complexity of the precedure in big O notation for both time and space. Be sure to note what your parameters represent, i.e. ifyou write O(n) be sure to say what n is in the procedure definition. Example: (define (append-iter a b) ...) Time: O(size a) Space O(1) (define (fcn1 alist) (if (null? alist) () (cons (+ 1(car alist)) (cdr alist)))) (define fcn2 (lambda (alist blist) (if (null? alist) 0 (+ (fcn2 (cdr alist) blist) (fcn2 (cdr alist) blist))))) (define (fcn3 alist blist) (if (null? alist) blist (fcn3 (cdr alist) (cons (car alist) blist)))) (I have no clue on this time and size thing, so an explanation would be nice.... in case it's not clear, prove time and space in big O notation.) 5. Define a procedure apply that takes as arguments an integer 'count', a number 'arg', and a function 'f', and returns the value of count repeated applications of the function called on arg. Thus if count =3, arg=5, and f is the function times6, the result would be (((5 * 6) * 6) * 6) = 1080 (define (times6 x) (* x 6) I have this code here (for #5.) which isn't a 100% what above is asking for (need to change names etc), and I thought it would work, but it isn't. Can someone figure out the problem with it: (define repeat-proc (lambda (num-repeats proc-name arg) (cond ((= 0 num-repeats) ()) (else (proc-name arg) (repeat-proc (- num-repeats 1) proc-name arg))))) 6. Write a Scheme expression that calls your procedure 'apply' (from above' to compute the value of the following expression. Do not call "define". (((215 * 2 -6) * 2 - 6) * 2 - 6) Lastly, I've tried googling and all but didn't have much success with finding code for these functions: deep-member, flatten, and make-list (ex for make-list is: >(make-list 3 'a) ---> (a a a) ). If anyone can point me to the right direction, I'd apprecaite it (I searched within DrScheme, but couldn't find the code itself). I know this is a lot of stuff and very last min., but any answers/explanations will be helpful. I did this as a last resort and even if you can't help me, wish me luck ;)

going to bed now and taking this test early tomorrow, so I can't reply to any ?s you may have.
thanks in advance if anyone can help me with any questions!

bump....... no scheme pros here? :(

Is this really scheme? I do not remember using several function calls in one statement one after another withous using (and . . .) or (begin . . )...

But wathever. Let it be as it is.

1) You are not using value of "a" at all so it's just about b.
d 31 -> d 30 -> d 15 -> d 14 -> d 7 -> d 6 -> d 3 -> d 2 -> d 1 -> d 0
count for yourself.

2) I would rather write:
(define (f) (begin (display "woof") 7))
or
(define (f) (and (display "woof") 7))
so the last element is returned, but if the original syntax compiles - let it be the same.

"woof" displays, when the "f" function is computed.
In example with "let", "f" is called once and the returned value(7) is remembered as "n", and so n(=7) is used later.
In the second example, f is called directly, so two times.
The returned value is the last statement in the "let" or in pure "define" or in whatever. All the mid-calls are computed, but their results are simply ignored.

3) It depends on what your: "filter, enumerate, accumulate" functions really do. I'm pretty sure you were supposed to write them on your own many times. I was using the for sure, but under different names (apply, fold...).
Map takes a list "l" and a function "f" and returnes a list of elements, that were returned when f was called with each of the elements of the original list "l":
(a, b, c, ...) -> (f(a), f(b), f(c), ...)
so:
(define map (lambda (l f)
(if (null? l) nil
(cons (f (car l)) (map (cdr l) f)))))

I suppose filter chooses from a list those elements, that return true(#t) for a fixed function f:

(define filter (lambda (l f)
(cond ((null? l) nil)
((f (car l)) (cons (car l) (filter (cdr l) f))) ;take the element
(else (filter (cdr l) f))))) ;skip the element

oh, (define nil '()), of course...


4)
fcn1 - just adds 1 to first element of the list, time O(1), memory O(1)

fcn2 - function is somewhat stupid, returns 0 in all cases. Time O(2^n) n=sizeof(a), it just calculates two times longer, if you increase the lenght of a by one. Memory O(n), it expands it's uncalculated calls until it reaches the end of a, having always one path fully expanded(it's like tree-dfs).

fcn3 - merges a with b, reversing the a. Time O(n) n=sizeof(a). Additional memory O(1), cause it's a tail-recurse. Of course it uses additional O(n) for constructing the result.

5) You are calling
(proc-name arg)
and then going on with calculations, so the result of the
(proc-name arg)
is totally ignored.
What would work is:
(define repeat-proc (lambda (num-repeats proc-name arg)
(cond ((= 0 num-repeats) arg) ;original arg.
(else
(repeat-proc (- num-repeats 1) proc-name (proc-name arg))
))))

6) ...qiuckly renaming repeat-proc for apply...
And the answer is:
(apply
3 ;3 times
(lambda (x) (- (* x 2) 6)) function to apply, dynamicaly created, w/o define
215)


Lastly:
No, I cannot remember using any outer functions only the ones I made myself. No DrScheme "almost" never can help you with that... sorry.


That's all I could do ;)

I like sheme.
Cheers.
/def

Quote:Original post by red-dragonX
(I know you can test them by enter
> (test-let)
woof
9
>(test-define)
woofwoof
9
I don't complete understand the outputs...I don't know what is 'returned' at all).

The interpreter outputs the "return value" of everything it is asked to evaluate. So "what is returned" is everything the interpreter shows, which cannot be explained by a (display ) call.

Quote:
3. Use one or more procedures from the sequence tool kit (filter, enumerate, accumulate, map) to write a single expression that returns the PRODUCT of all elements of the series {0,5 10 15 ... n} for some pre-defined variable n. You're provided only n, not a list to use as input.

(I can't get this right :( )

One possible way is to enumerate from 0 to n, filter out everything not divisible by 5, and accumulate the product of each pair of those.

That's a procedural description; to do things functionally, work from the inside out:

(accumulate (lambda (x y) (* x y)) (expression_that_yields_series))

And so on, substituting the (filter) expression in, then the (enumerate) into the filter.

Or something like that. I'm rusty.

Another way to do it is to observe that the series always contains 0, so the product is 0 ;)

Quote:
I have this code here (for #5.) which isn't a 100% what above is asking for (need to change names etc), and I thought it would work, but it isn't. Can someone figure out the problem with it:
(define repeat-proc (lambda (num-repeats proc-name arg)
(cond ((= 0 num-repeats) ())
(else
(proc-name arg)
(repeat-proc (- num-repeats 1) proc-name arg)))))

If you apply the function zero times, then the argument is unchanged. So you should be returning arg in your base case, not ().

When you do the recursion, you seem to be trying to calculate the result of applying the method once, and then doing the recursion with arg. This doesn't work for two reasons:

One, you can't give multiple things to the 'else', at least not without wrapping them in (begin).

Two, the (proc-name arg) returns the result of applying proc-name to arg, but does not actually change arg in the current context.

You could use a let-related thingy here, but that's really ugly and contrary to how functional programming is supposed to work. What you want to do is pass the result of that evaluation directly in to the recursive call. Remember, not a procedural language; no "temporaries" -> "inline" everything.

Quote:
6. Write a Scheme expression that calls your procedure 'apply' (from above' to compute the value of the following expression. Do not call "define".
(((215 * 2 -6) * 2 - 6) * 2 - 6)

Simple: write a lambda in one parameter, which evaluates x * 2 - 6 (doing the appropriate conversion to prefix notation). Provide that as the 'proc-name', and 3 as the 'num-repeats' (and 215 as the 'arg' of course).

You would probably have no problem doing this with a define: you would give your "procedure" a name, and then use that name in the call. Since you don't get to use "define", you should just put the lambda in place. Notice a theme consistent with the last question? :)

Quote:
Lastly, I've tried googling and all but didn't have much success with finding code for these functions: deep-member, flatten, and make-list (ex for make-list is: >(make-list 3 'a) ---> (a a a) ). If anyone can point me to the right direction, I'd apprecaite it (I searched within DrScheme, but couldn't find the code itself).

I have no idea what deep-member is.

The flattened version of a list can be found by flattening each element (recursively) and concatenating the flattened things together. Since you're iterating over the list, you want to work with car and cdr. (flatten ()) is (). Otherwise, it's something like (cons (flatten (car l)) (flatten (cdr l))), except that you don't really want to cons, but instead join the two lists in a "flattened" way.

(make-list 0 'a) -> (). Then you implement it for X copies recursively by relying on the function for X-1 copies.