CODEWITHSUNDEEP
recursionschemelispracket
mdo123
mdo123

Reputation: 1897

scheme:: contract violation: recursive procedure

I have a requirement to write a scheme procedure that takes a list as a parameter, which defines points awarded, player A score, and player B score. The function should determine who is the winner based on the scores:

For example, this the list of lists of scores I use below:

(define scores '(
                 (5 . (5 . 3)) ; points awarded = (car (car scores)) 5; player A score = cadr (car scores)) 5; player B score (cddr (car scores)) 3;
                 (5 . (6 . 2))
                 (5 . (8 . 4))
                 (5 . (5 . 1))))

So just to clarify, breaking down the first list in the list:

5 = points awarded (car (car scores)) ;

A = Player A Score (cadr (car scores)) ; (which is 5 on the first element, 6 on the 2nd, etc.)

B = Player B Score (cddr (car scores)) ; (which is 3 on the first element, 2 on the 2nd, etc.)

The problem is I have made a recursive function which blows up on the 1st iteration of the recursion. But I don't understand why?

#lang scheme

(define (game-winner scores)  
  (define A 0)
  (define B 0)
  (cond
    ((empty? scores) '()))
  (if ( > (cadr (car scores)) (cddr (car scores)) )
      (+ A (car (car scores)))
      (+ B (car (car scores))))
  (game-winner (cdr scores)))

OUTPUT:

car: contract violation
  expected: pair?
  given: ()

The part that confuses me is that when I simulate running through the 1st iteration of the recursion and get the values the function should have, I get correct values:

;first loop through function

    (car (car scores))  ; 5
    (cadr (car scores)) ; 5
    (cddr (car scores)) ; 3

;second loop (1st recursive call)

    (cadr (car (cdr scores))) ; 6
    (cddr (car (cdr scores))) ; 2

So if I don't understand why it's blowing up? It should work in the same way as the first call before the recursion. But I obviously am missing something. Any ideas?

P.S. if I just return the A or B instead of the recursive call I get 0:

(define (game-winner scores)  
  (define A 0)
  (define B 0)
  (cond
    ((empty? scores) '()))
  (if ( > (cadr (car scores)) (cddr (car scores)) )
      (+ A (car (car scores)))
      (+ B (car (car scores))))
  A)

OUTPUT: 0

How come the value of A (which should be 5) after the first call doesn't show when I oupout A? Is A only in scope of the if loop? If so, how do I get it to exist outside that scope?

based on feedback from @Sylwester I modified by procedure to:

#lang scheme

(define (game-winner scores)  
  (define A 0)
  (define B 0)
  (cond
    ((empty? scores) '())
    (( > (cadr (car scores)) (cddr (car scores)))    
     (cons (+ A (car (car scores))) (game-winner (cdr scores))))
    (cons (+ B (car (car scores))) (game-winner (cdr scores)))))

OUTPUT:

(5 5 5 5)

So I feel like I'm getting closer. But I need to be able to add these all together for A or for B and output the winner (A or B). How do I build on top of this to get that to work?

Upvotes: 0

Views: 108

Answers (1)

Sylwester
Sylwester

Reputation: 48745

You code has a lot of dead code that is never used no matter what is the outcome and in the end the last expression will do (cdr scores) no matter if it's empty or not.

(define (game-winner scores)  
  ;; Two constants that never change from 0
  (define A 0)
  (define B 0)

  ;; Dead code. Werther it's '() or #<undefined>
  (cond
    ((empty? scores) '()))

  ;; Dead code. Becomes (+ 0 (car scores)) but never used
  (if ( > (cadr (car scores)) (cddr (car scores)) )
      (+ A (car (car scores)))  ; + never mutates A
      (+ B (car (car scores)))) ; + never mutates B

  ;; Infinite recursion. Happens no matter what is the outcome of the dead code
  (game-winner (cdr scores)))

So when you write a cond or if it should handle all the things that happen so that it is the last expression:

(define (game-winner scores)
  ; local defines
  (define some-var some-expression)
  ...

  ; one expression, the result of this is the result of the procedure.
  (if (empty? scores)
      '()
      (if ....)))

EDIT

Here is an example of a recursion using arguments to accumulate the scores and in the end determine who has the highest score: 

(define (game-winner scores)
  (let loop ((scores scores) (a 0) (b 0))
    (if (empty? scores)
        (cond ((> a b) 'A)
              ((< a b) 'B)
              (else 'TIE)))
        (loop (cdr scores)
              (+ a (cadar scores))
              (+ b (cddar scores))))))

(game-winner scores)
; ==> A

Upvotes: 2

Related Questions