CODEWITHSUNDEEP
listrecursionscheme
Reuben Tanner
Reuben Tanner

Reputation: 5565

Find and replace in scheme

I need to write a scheme program that finds and replaces a given pattern and I've gotten it to work on only one layer of nesting but when the next car from the list is a list itself, my program doesn't properly recurse in it.

Here is what I have so far:

(define replace 
    (lambda (source target replacement) 
        (if (eqv? source target)
            replacement
            (if (null? source)
                '() ;;base case

                (if (equal? target (car source))
                    (cons replacement (replace (cdr source) target replacement))

                    (cons (car source)
                    (replace (cdr source) target replacement))
                )
            )
        )
    )
)

Upvotes: 0

Views: 3968

Answers (3)

Sylwester
Sylwester

Reputation: 48745

Your error is that you don't do replace on the car when it's not a match and it's not an atom. It's possible to write this very compact by allowing to follow all pairs.

(define (replace source target replacement) 
  (cond ((equal? source target) replacement) ;; equal, return replacement
        ((not (pair? source)) source)        ;; not equal && not pair, return source
        (else (cons (replace (car source) target replacement) ;; recurse
                    (replace (cdr source) target replacement)))))

Upvotes: 0

GoZoner
GoZoner

Reputation: 70135

Use should replace eqv? with equal?. Using eqv? doesn't give the result you'd expect as in the following:

> (eqv? (list 1 2 3) (list 1 2 3))
#f
> (eqv? '(1 2) '(1 2))
#f ; some Schemes may return #t

Regarding your code, it is more readably and compactly written as a series of cond clauses:

(define (replace source target replacement) 
  (cond ((eqv? source target) replacement)
        ((null? source)      '()) ;;base case
        ((equal? target (car source))
         (cons replacement (replace (cdr source) target replacement)))
        ((not (list? (car source)))
         (cons (car source) (replace (cdr source) target replacement)))
        (else
         (cons (replace (car source) target replacement) 
               (replace (cdr source) target replacement)))))

Also, another approach that might more clearly illustrate the algorithm ('handle car and cons it to handing of cdr') is:

(define (replace source target replacement)
  (cond ((null? source)'())
        ((equal? source target) replacement)
        (else (let ((next (car source))
                    (rest (cdr source)))
                (cons (if (not (list? next))
                          next
                          (replace next target replacement))
                      (replace rest target replacement)))))

Upvotes: 1

Reuben Tanner
Reuben Tanner

Reputation: 5565

In my initial version I was not checking to see if (car source) was a list and it was thereby being treated as an individual token, to avoid that I added one more condition:

(define replace 
    (lambda (source target replacement) 
        (if (eqv? source target)
            replacement
            (if (null? source)
                '() ;;base case

                (if (equal? target (car source))
                    (cons replacement (replace (cdr source) target replacement))

                    (if (not (list? (car source)))
                        (cons (car source) (replace (cdr source) target replacement))
                        (cons (replace (car source) target replacement) (replace (cdr source) target replacement))))))))

Upvotes: 0

Related Questions