little help with scheme

R

romeoagogo

Limp Gawd
Joined
Aug 25, 2004
Messages
159
Okay I am half-way through this scheme course and everything has been pretty easy thus far, but I am pretty stuck on this abstraction for reducing an arbitrary list of trees.

The assignment asks for me to take the following reduction function for a single tree and change it to handle N number of trees:

Code: 
(define tree-reduce 
  (lambda (f op id t) 
    (if (null? t) 
      id 
      (if (pair? t) 
        (op (tree-reduce f op id (car t)) 
              (tree-reduce f op id (cdr t))) 
        (f t)))))

So I know I have to use the variable arity lambda to get an arbitrary number if trees into a list and I also know I have to make use of 'apply', but I am not sure if I'm using it completely correctly. Here is what I came up with:

Code: 
(define tree-reduceN
     (lambda (f op id . t)
       (if (null? t)
           id
           (if (pair? t)
              (op (apply tree-reduceN f op id (car t))
                  (apply tree-reduceN f op id (cdr t)))
              (apply f t)))))

This seems to me like it should work, but when testing this with the following function:

Code: 
 (define tree-sumN
    (lambda t
       (apply tree-reduceN + + 0 t)))

On the input: (tree-sumN '(1 (2) 3))

I get the error: 'Error in apply: 3 is not a proper list.'

Now I understand why the error is popping up, I just don't know what to do about it. The last argument of apply must be a proper list, but besides cons-ing an empty list to each recursive call (which I dont think works either) I don't know how to avoid this case. Any tips here would be really appreciated.
Thanks
 
I just wrote 'tree-reduceN' in 3 lines of code.

Hint: You have a list of trees. You need to do the same thing (tree-reduce) to each tree (and you have a list of trees). What function processes a list one element at a time?

I have another hint as well, but I'm afraid I've given away a lot with the first. Perhaps I will post it after you make some progress if you still don't have the answer.
 
You need to do the same thing (tree-reduce) to each tree (and you have a list of trees).
Click to expand...

I think my professor wants us to completely re-write this, as in not using the original tree-reduce at all. Does your solution still hold?

What function processes a list one element at a time?
Click to expand...

As far as I know, this is what apply does, but as I said my knowledge of apply is shaky at best. I understand how it takes its arguments and what is supposed to be happening but I use it in my code whimsically, basically guessing where it is needed. If there is some other function you are referring too then I may not know it yet because of the way the prof is teaching this course, he is introducing new functions as we learn this stuff, not all in the beginning.

I am going to try and do a solution that uses 'tree-reduce' just to get something working possibly, but any more hints would be good. I have been sitting here for > 2 hours and all the other assignments have taken less than 30 minutes.

Thanks for helping out tho!
-alex

update:

okay I went ahead and tried implementing it using tree-reduce just for kicks like so:

Code: 
13 (define tree-reduceM
 14    (lambda (f op id . t)
 15       (apply tree-reduce f op id t)))

but this does not work if given more than one tree. I either not familiar with the function you are talking about, or you do mean 'apply' and I know less about it than I thought. Regardless, I am pretty positive my solution must be completely re-written, so can you maybe point out where I am going wrong in my original code? What concept I am missing?
 
romeoagogo said:
I think my professor wants us to completely re-write this, as in not using the original tree-reduce at all. Does your solution still hold?
Click to expand...

Nope, my solution doesn't take that into account, it uses tree-reduce.


As far as I know, this is what apply does, but as I said my knowledge of apply is shaky at best. I understand how it takes its arguments and what is supposed to be happening but I use it in my code whimsically, basically guessing where it is needed. If there is some other function you are referring too then I may not know it yet because of the way the prof is teaching this course, he is introducing new functions as we learn this stuff, not all in the beginning.
Click to expand...

This isn't exactly what apply does. Apply takes a function and uses the given arguments and the given list as arguments to that function. See http://www.scheme.com/tspl3/control.html#./control:s3
 
Code: 
13 (define tree-reduceM
 14    (lambda (f op id . t)
 15       (apply tree-reduce f op id t)))
Click to expand...

That's actually pretty close to what I have. I use another function as well.. called 'map'.
 
romeoagogo said:
well do you have any ideas as accomplishing it without tree-reduce?
Click to expand...

Yup, write a function called 'flatten' to flatten the list and then use 'apply' to apply the function to the flattened list. Although, this will work on more than just trees.

Edit: Ths is actually the wrong solution, because it will ignore one of the two input functions.
 
I'm going to be getting off of the computer now, so I won't be able to help any more tonight. I do have to say though, one of the great things about scheme is the ability to use simple functions, like tree-reduce and use map, apply, reduce, etc. to build bigger/better functions.

One thing you might consider is still using the given code for tree-reduce, as-is, and assign it to a let-bound variable and use 'map' and 'apply'

Good luck.
 
well I think this will be the first assignment that doesnt get handed in, but I really appreciate you trying to help me out. Hopefully this will just be a wake up call that I need to figure out this stuff a bit more :)

thanks
 
romeoagogo said:
well I think this will be the first assignment that doesnt get handed in, but I really appreciate you trying to help me out. Hopefully this will just be a wake up call that I need to figure out this stuff a bit more :)

thanks
Click to expand...

Don't give up! (yeah, I know I said I wouldn't be online, I just felt bad leaving someone stranded).

Ok, I just re-wrote my solution. Have you learned about 'letrec' yet?
 
sorry just was grabbing some food. PMed you my aim SN and I do not know what letrec is.
 
You must log in or register to reply here.
Back
Top