Scheme: Count number of lambda symbols in function

0
votes

So we had taken a test over Scheme and I got one of the problems wrong, but I have no idea how to correct it. What it asks for is:

write a Scheme function count_lambda which takes an arbitrary expression, y, and returns the number of 'lambda symbols in y. For example, invoking (count_lambda '(lambda x . lambda y . x y) z) should return 2.

The way I thought of for how to do this was to check to see if the variable was of type "lambda". However, lambda might not be a type....... Also, I pictured the expression being a list.... not sure if I can do that either...so this is what I have:

 (define count_lambda
  (lambda (y)
    (if (null? y) 0
    (cond
      ((lambda? y) 1)
      ((number? y) 0)
      ((cons? y) (+ (count_lambda(car y)) (count_lambda(cdr y)))))))

It says lambda is an undefined function so that right there tells me I'm looking at it wrong. Unfortunately, I have no idea what I should do for it.

Any help would be appreciated.

Thanks

2
lambdacountscheme
The sample input you provided isn't correct, it has parentheses problems and this: x.lambda looks like an error, perhaps you meant x . lambda? Please check and fix it. - Óscar López
it looks like there's no space, but maybe. What is the difference? - user2869231
it makes all the difference in the world. x.lambda is not a lambda symbol, whereas x . lambda contains a lambda symbol. It's very important that you provide correct input, even with the proper spaces in place, the sample you gave won't compile, it's an invalid expression, because of misplaced dots and parentheses - Óscar López
Ok, didn't know that. And I see the parenthesis wrong; I just figured that what she gave us to enter was correct. To me, it looks like there should be one in between the x and the y? - user2869231
Wait a second, I shouldn't be adding parenthesis - user2869231

2 Answers

0
votes

It's simpler than you think. Notice that the input is a list of symbols, you're required to count the number of times the symbol 'lambda appears in the list, not the number of times an actual lambda appears.

Also, the template for iterating over a list of lists isn't quite right. This is how it should look like:

(define count_lambda
  (lambda (y)
    (cond ((null? y) 0) ; is the list empty?
          ((not (pair? y)) ; if the current element is an atom
           (if (eq? y 'lambda) 1 0)) ; then check to see if is a lambda
          (else (+ (count_lambda (car y)) ; otherwise advance recursion
                   (count_lambda (cdr y)))))))
0
votes

Óscar has a good answer, but I just want to point out that using lambda? is not an bad idea, but you need to make it. In addition cons? is not a primitive in scheme but perhaps the cousin language #!racket which has it's own SO-tag.

Here is a Scheme implementation using the latest ratified standard R7RS:

#!r7rs
(import (scheme base)
        (only (scheme) display))

(define (lambda? x)
    (eq? x 'lambda))

(define (count-lambda lst)
  (cond
    ((lambda? lst) 1)
    ((not (pair? lst)) 0) ; cons? is not a scheme primitive
    (else (+ (count-lambda (car lst)) 
             (count-lambda (cdr lst))))))


(display (count-lambda '(yatta (lambda . lambda) #f #t 34 
                        (hey (ho lambda . yiu) lambda )))) ; displays 4

Compared to your code I have removed the check for a number (since what is not a pair or a lambda can be a different symbol, a number, #t), instead I have added a base case that actually does the same.

It will work in R6RS (since R7RS only supported by chibi and we have a lot of good R6RS-implementations like DrRacket and Ikarus by replacing the 3 first lines with:

#!r6rs
(import (rnrs base)
        (only (rnrs) display))