Scheme recursion error

Question

This recursive function seems to work properly, adding to the result list the exact letters I want it to, B and C, and then when it finishes, it correctly sees that the last element has been reached.

It then executes the base case, and an error occurs which I cannot explain. What is causing this error?

    (define(preceding-R X Vector result)    
      (if (eq? '() (cdr (vector->list Vector)))
               result
              (helper X Vector result)))

(define (helper X Vector result)
   (if(eqv? X (cadr (vector->list Vector))) ((set! result (cons result (car (vector->list Vector)))) (preceding-R X (list->vector (cdr (vector->list Vector))) result))
                            (preceding-R X (list->vector (cdr (vector->list Vector))) result)))

(preceding-R 'a #(b a c a) '()))

The error:

procedure application: expected procedure, given: #; arguments were: ((() . b) . c)

Please format your code and briefly explain what the code must do. — ffriend
– ffriend, Commented Nov 14, 2010 at 1:25

erjiang · Accepted Answer · 2010-11-14 03:11:42Z

Here's some code that isn't "absolutely horrible":

(define preceding-R 
  (lambda (x vec)
    (define helper
      (lambda (ls)
        (cond
          ((null? ls) '())
          ((null? (cdr ls)) '())
          ((eq? (cadr ls) x) (cons (car ls) (helper (cdr ls))))
          (else (helper (cdr ls))))))
    (helper (vector->list vec))))

> (preceding-R 'a #(b a c a))
(b c)

Eli Barzilay has a point; if I were grading the original code, I would probably award fewer than half credit because of the things he pointed out:

set! should be avoided in most circumstances, and is generally not permitted on homework problems involving basic Scheme code. Having to use set! is a usual tell that recursion isn't understood too well.
Since begin "throws away" the results of everything but the last expression, it means that the non-tail expressions had side-effects (like set!) and so begin usually doesn't show up in educational problems either.
Conversion back-and-forth over and over and over and over again is obviously a waste. One conversion will do, but you probably could've used lists instead of vectors to begin with. Lists are the most common data structure used in Scheme, especially since they work well with recursion.
Your code will error out on an empty list in your second line: (preceding-R 'a #()) => Error: Attempt to apply cdr on '()
If you do use set! to modify result, then there's no reason to pass result around. It's extra baggage.
Eli's last point was that you can write:

.

(define (helper X Vector result)
  (preceding-R X (list->vector (cdr (vector->list Vector)))
               (if (eq? X (cadr (vector->list Vector)))
                   (cons (car (vector->list Vector)) result)
                   result)))

saving some repeated code.

Marek Sapota · Accepted Answer · 2010-11-14 01:27:33Z

1

(define (preceding-R X Vector result)    
  (if (eq? '() (cdr (vector->list Vector)))
    result
    (helper X Vector result)))

(define (helper X Vector result)
  (if (eqv? X (cadr (vector->list Vector)))
    (begin
      (set! result (cons (car (vector->list Vector)) result))
      (preceding-R X (list->vector (cdr (vector->list Vector))) result))
    (preceding-R X (list->vector (cdr (vector->list Vector))) result)))

(preceding-R 'a #(b a c a) '())

I've added begin call. If you want multiple expressions in if you can't just wrap them in (), it was interpreted as function call on void (returned by set!) with argument returned by recursive call to preceding-R.

answered Nov 14, 2010 at 1:27

Marek Sapota

20.6k3 gold badges37 silver badges48 bronze badges

2 Comments

cliff259 Over a year ago

thank you very much, I knew that the problem was something to do with that, but I had tried using cond to fix that issue, since I knew it used begin by default. apparently I was no implementing it correctly. Thanks again.

Eli Barzilay Over a year ago

This code is absolutely horrible. It uses set! for no good reason, it uses begin just for that, it will throw errors on some cases, it keeps converting the vector to a list and back to vectors, it has if at the outer level of helper when it could easily be pushed inside to the last aregument, etc.

Collectives™ on Stack Overflow

Scheme recursion error

2 Answers 2

Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related