Home > OS >  Recursion/Lists in Racket
Recursion/Lists in Racket

Time:06-02

I am trying to make the function remove-member, where I have a list of strings and I give one of the members of the string (i.e. "A") to the function, and it removes that member and returns the rest of the list without that member. At the moment I have created tests and started my function, but I am lost beyond that. I know recursion functions include the first member of the list and the rest of it, but how would I remove the first member of a string?

(define str (list->string (list 'A 'B 'C)))

(check-expect (remove-occurrences "A") (list 'B 'C))
(check-expect (remvove-occurrences '()) (list 'A 'B 'C))

(define (remove-occurrences r)
  (cond
    [(empty? r) str]
    [(??? r)]))

CodePudding user response:

To remove a single element from a list:

  1. Is the list empty? If it is, we're done and the result is the empty list.
  2. OK, it's not empty. Is the first element of the list the same as the element you want to remove? If it is then the result is the rest of the list.
  3. OK, it's not empty, and the first element didn't match. So the answer is a list consisting of a cons of the first element and the result of removing the element from the rest of the list. Which you now know how to do.

Alternatively, to remove all occurrences of an element from a list:

  1. Is the list empty? If it is, we're done and the result is the empty list.
  2. OK, it's not empty. Is the first element of the list the same as the element you want to remove? If it is then the result is the the result of removing all occurrences of the element from rest of the list, which you know how do to now.
  3. OK, it's not empty, and the first element didn't match. So the answer is a list consisting of a cons of the first element and the result of removing the element from the rest of the list. Which you now know how to do.

How these functions differ:

> (remove-one '(a b b c) 'b)
'(a b c)
> (remove-all '(a b b c) 'b)
'(a c)

CodePudding user response:

Let's follow the data type.

This way we get the mundane tasks taken care of automatically for us, and get to focus our creative mental abilities on more interesting, less common aspects of our problem:

(define (list-p ad)
  (cond
    ((null? ad)       ; follow
      #t)
    ((pair? ad)
      (let ((a (car ad))  ; the
            (d (cdr ad))) ; type! 
        (list-p d)))
    (else #f)))

We can see this predicate as a constructor of Boolean values. Creating a list following the same example aka skeleton code is also easy:

(define (list-l ad)
  (cond
    ((null? ad)  ; return proper
      (list))    ; type here, and
    ((pair? ad)
      (let ((a (car ad))
            (d (cdr ad))) 
        (list-l d)))   ; here
    (else #f)))

We've just followed the type's skeleton code, mended it in the few appropriate places, and got ourselves a working code which creates values of the proper type, all by itself!

But does it create any interesting value, fully using the supplied argument? Evidently, not. For that we must mend the recursive call:

(define (list-copy ad)
  (cond
    ((null? ad)  
      (list))    
    ((pair? ad)
      (let ((a (car ad))
            (d (cdr ad))) 
        (cons ...         ; here
              (list-copy d))
           ))
    (else #f)))

Now you get to tweak this further, consing the first element of a pair conditionally, as required by your problem.

(note: null? could be called empty? in your dialect).

  • Related