CODEWITHSUNDEEP
listrecursionappendscheme
Keagansed
Keagansed

Reputation: 183

How to recursively add elements to a list based on the evaluation of another function in scheme

I have the following code in which I am trying to add all elements of a list to a new list based on if they are prime numbers:

(define (findPrimes newLis lis)
    (cond
            ((null? lis) ())
            (else 
                (
                    (cond 
                        ((#t (isPrime (CAR lis)))
                            (append newLis (CAR lis))))
                    (findPrimes newLis (CDR lis))
              ))
          )

        newLis
    )

I however get an error. I am extremely new to scheme so I apologise if this code is completely wrong.

Upvotes: 0

Views: 49

Answers (1)

Will Ness
Will Ness

Reputation: 71065

Yes, you have lots of extraneous parentheses. Each pair of parentheses count, in Scheme, we cant just through them around for good measure. (f x) means "do call function f with an argument x", so ((f x)) means "call function f with an argument x, and then treat the result of that call as a function, and call it (again) without any arguments". Which is bound to cause troubles, more likely than not.

What you meant to write was

(define (findPrimes newLis lis)
    (cond
            ((null? lis)   (set! newLis '()))
            (else 
                (cond 
                   ((equal? #t (isPrime (CAR lis)))
                           (set! newLis 
                                 (append newLis (list (CAR lis))))
                           (findPrimes newLis (CDR lis)))
                   (else
                           (findPrimes newLis (CDR lis)))))))

but that's all kinds of wrong. For starters, (findPrimes '() (list 2 3 4 5 6 7 8 9 10)) doesn't return anything -- no matter the arguments.

You need to change the base case handling. In the recursive case you build up the list passed in as the first argument; then, when we've reached the end of the input list (second argument), what do you do with the new list that is now ready? You set it to '()! And you return no value (because set! doesn't return any value).

So this is easy to fix: just return the value that you've built. The value of the last expression is what is returned as the value of the whole function. And you have the value you want returned, the new list. So you make it be the last expression in the base case cond clause. So now it works.

But, it isn't working well. It is quadratic in time (because of repeated append). This usually means disastrously slow execution times. Also, the use of set! is an indicator that something's might not be quite right.

The usual Scheme way of doing this is,

(define (findPrimes lis)
    (cond
            ((null? lis)               '() )
            (else 
                (cond 
                   (           (isPrime (CAR lis))
                           (cons                      (CAR lis)
                             (findPrimes        (CDR lis))))
                   (else
                             (findPrimes        (CDR lis)))))))

see how much less stuff you had to type in?

Here it is again, with the normal spacing:

(define (findPrimes lis)
  (cond
    ((null? lis) '() )
    ((isPrime (car lis))
     (cons (car lis)
           (findPrimes (cdr lis))))
    (else
     (findPrimes (cdr lis)))))

There was one or two more things that I've changed there as well. Can you tell what it was?

Upvotes: 1

Related Questions