Function not reading all the element in a list

Questions & Answers
1

Hi,
I am not an English native, so, if you see any fault or incoherence, please correct me.
I'm currently learning SCHEME language, and our teacher told us to create two programs: one which counts the number of occurrence of an element in a list, and the other which verifies if the element is present or not.
The first program works for simple list, but for the lists with imbrication, it seems like it doesn't count all the element (the one inside the imbrication). For the second, I think it's a similar problem.

Here is what I have done for the first one:

(define occur (lambda (x L)
                (cond
                  ((null? L)             0)
                  ((eq? x (car L))  (+ 1 (occur x (cdr L))))
                  (#t                       (occur x (cdr L)))
                )))

This is an example where it doesn't work:

> (occur 'a '(b (a b)))
0

Here is the second one.

(define ppt (lambda (x L)
              (cond
                ((null? L)            #f)
                ((eq? x (car L)) #t)
                (#t                      #f))
              ))

This is an example where it doesn't work:

> (ppt '1 '(2 (0 2 1)))
#f

Update:
I have done some verification and the reason, why it doesn't work, is because of the function "cdr".

> (cdr '(a (b c) d))
'd
> (cdr '(a (b c)))
'()

Do you have any suggestion?
Thanks in advance.

2

Here's what I get from cdr:

Welcome to Racket v8.9.0.3 [cs].
> (cdr '(a (b c)))
'((b c))

Are you using a different language, or some other library that changes what cdr does?

3

No, there is only this line at the start of the code.

#lang racket
4

Ok, I don't have any idea what happened with your cdr examples, but the problem in your functions is that you are iterating through all the elements in the list and comparing them with x but 'a is not an element of the first list. The first list has only two elements: the symbol 'b and the list '(a b). If you want to look at the elements of sublists then you will need to traverse them explicitly or flatten the list first.

5

Racket's cond has else, you know. Don't need to use #t as a catch-all like it was Common Lisp.

Hint: You're missing the case where you need to recurse if the car of the list is itself a list.

(define occur (lambda (x L)
                (cond
                  ((null? L) 0)
                  ((eq? x (car L))  (+ 1 (occur x (cdr L))))
                  ((list? (car L)) #;(Fill in the blanks))
                  (else (occur x (cdr L))))))

You might want to use a test other than eq? too.

1 Like
6

Note that '(b (a b)) is (list b (list a b)) that is different from (list b a b). The first example has an additional "container".

7

Hello,
Sorry for the late response. I found the solution.

(define occur2 (lambda (x L)
                (cond
                  ((null? L)         0)
                  ((list? (car L))  (+ (occur2 x (car L)) (occur2 x (cdr L))))
                  ((eq? x (car L))  (+ 1 (occur2 x (cdr L))))
                  (#t               (occur2 x (cdr L)))
                )))

All I had to do was to verify if (car L) was a list and use imbrication with this.

8

Great Job!

Can it be simplified?

#lang racket

;; count the number of times that 'x' occurs in the s-expression L
(define occur2 (lambda (x L)
                (cond
                  [(pair? L) (+ (occur2 x (car L)) (occur2 x (cdr L)))]
                  [else (cond [(equal? x L) 1]
                              [else 0])])))

(require rackunit)
(check-equal? (occur2 'a '(a (b a) a (b b (a) b))) 4)

It's true that the inner cond can be flattened, but this one clearly adheres to the s-expression template, so it reads more nicely to me. I also like the "one-or-zero" clarity of the inner cond.

9

It's simpler than mine, but my professor told us to use only the basic function of Scheme while we're still at the beginner level. So no 'if' or 'else', etc., but I will keep this one as another solution.

10

I'd call if simpler than cond... :thinking:

(cond is often defined as a macro that expands to a series of if's)

1 Like
11

That makes sense. In that case, replace else with #t and you're done.