CODEWITHSUNDEEP
schemeracketr5rs
Seol
Seol

Reputation: 49

Replacing every nth occurence of old

I am trying to replace every nth occurrences of old with new with lst as a list that can be list of atoms or list of lists. I am having trouble replacing the nth occurrence of old with new when lst is a list of lists.

(define (replace lst n old new)
  (cond ((null? lst) '())
        ((and (= n 1) (eq? (car lst) old)) (cons new (cdr lst)))
        ((not (atom? (car lst)))
          (cons (replace (car lst) n old new) (replace (cdr lst) n old new)))
        ((and (atom? (car lst)) (eq? (car lst) old)) (cons old (replace (cdr lst) (- n 1) old new)))
        (else (cons (car lst) (replace (cdr lst) n old new)))))

Calling the function above

(replace '(a b c a d e f g a t y a g) '3 'a 'o)

give me (a b c a d e f g o t y a g), but when I input a list of lists I am unable to get the correct output

(replace '((a a) b c a d e f g a t y a g) '3 'a 'o)

This is probably because when my function goes into the list (a a) my n counter that got decremented does not get returned. Is there a way to pass the n counter?

Upvotes: 1

Views: 209

Answers (2)

Sylwester
Sylwester

Reputation: 48745

In order to pass the current n from processing the car to the cdr you need either have the helper return both the result and the current n. As an example here is something that replaces every match in a tree with its item number: 

(define (replace-with-index haystack needle)
  (define  (result n value) value)
  (let loop ((lst haystack) (n 0) (k result))
    (if (null? lst)
        (k n '())
        (let ((a (car lst)) (d (cdr lst)) (nn (+ n 1)))
          (cond ((equal? needle a)
                 (loop d nn (lambda (cn r) (k cn (cons n r)))))
                ((not (pair? a))
                 (loop d nn (lambda (cn r) (k cn (cons a r)))))
                (else
                 (loop a n (lambda (cn ar)
                             (loop d cn (lambda (cn dr)
                                          (k cn (cons ar dr))))))))))))

(replace-with-index '(a (a b (h e)) (c d (h e) l l)) '(h e)) 
; ==> (a (a b 3) (c d 6 l l))

The technique is called continuation passing style. You could do it without by having it return both the current n and result:

(define (replace-with-index haystack needle)  
  (define (helper lst n)
    (if (null? lst)
        (values n '())
        (let ((a (car lst)) (d (cdr lst)) (nn (+ n 1)))
          (cond ((equal? needle a)
                 (let-values ([(cn r) (helper d nn)])
                   (values cn (cons n r))))
                ((not (pair? a))
                 (let-values ([(cn r) (helper d nn)])
                   (values cn (cons a r))))
                (else
                 (let*-values ([(an ar) (helper a n)]
                               [(dn dr) (helper d an)])
                   (values dn (cons ar dr))))))))
  (let-values ([(n r) (helper haystack 0)])
    r))

The difference between this and the CPS version is just style. As many Scheme implementations actually turn the code into CPS the code executed would be almost identical. As a last example I've removed the multiple values and used encapsulation in forms of cons. 

(define (replace-with-index haystack needle)
  ;; abstraction
  (define nrbox cons)
  (define nrbox-n car)
  (define nrbox-r cdr)

  (define (helper lst n)
    (if (null? lst)
        (cons n '())
        (let ((a (car lst)) (d (cdr lst)) (nn (+ n 1)))
          (cond ((equal? needle a)
                 (let ((nr (helper d nn)))
                   (nrbox (nrbox-n nr) (cons n (nrbox-r nr)))))
                ((not (pair? a))
                 (let ((nr (helper d nn)))
                   (nrbox (nrbox-n nr) (cons a (nrbox-r nr)))))
                (else
                 (let* ((anr (helper a n))
                        (dnr (helper d (nrbox-n anr))))
                   (nrbox (nrbox-n dnr) (cons (nrbox-r anr) (nrbox-r dnr)))))))))
  (nrbox-r (helper haystack 0)))

Basically this cons a lot of temporary pairs while the multiple value and CPS version keeps the values on the stack. Thus the difference is in performance. In form of abstraction they are completely the same code.

Upvotes: 1

soegaard
soegaard

Reputation: 31147

When you replace an old value with a new value, you return (cons new (cdr lst)). The problem is that you don't replace any remaining occurences in (cdr lst).

Try something like (cons new (replace (cdr lst) original-n old new ). You will need the original n, so you can do something like this:

(define (replace lst n old new)
  (replace-helper lst n n old new))

(define replace-helper lst original-n n old new)
    ...your existing solution where replace has been
       renamed to replace-helper...))

Upvotes: 1

Related Questions