CODEWITHSUNDEEP
listrecursionreplaceschemeracket
Kiley
Kiley

Reputation: 39

Racket/Scheme - Replacing an item with another element in a non flat list

I'm trying to replace an item with another item when given a list. I've gotten to code out a procedure that can do this for a flat list but I was not sure how to implement it when the list is not a flat list. This is the current code for the replacer:

(define repl
  (lambda (exp1 exp2 exp3)
    (cond
      ((null? exp3) exp3)
      ((equal? (first exp3) exp1) (cons exp2 (repl exp1 exp2 (rest exp3))))
      (else (cons (first exp3) (repl exp1 exp2 (rest exp3)))))))

I'm very new to coding in racket so I wasn't sure how I would then be able to apply this when it's not a flat list A valid test case is the following

(repl 'a 'b '((f a) (f (a)))) => '((f b) (f (b)))

But when I run my current procedure it produces

'((f a) (f (a)))

How would I go about applying my current code to work for non flat lists?

Upvotes: 1

Views: 455

Answers (3)

Shawn
Shawn

Reputation: 52334

This would be trivial in Common Lisp, which has a function subst that does exactly this kind of replacement.

* (subst 'b 'a '((f a) (f (a))))
((F B) (F (B)))
* (subst 'x 'm '((a (b (c (d e (f (m))) h) i (j) (k (l (m)))) n) o (p)))
((A (B (C (D E (F (X))) H) I (J) (K (L (X)))) N) O (P))
* (subst 'x '(f (g)) '((a (b (c (d e (f (g))) h) i (j) (k (l (m)))))) :test #'equal)
((A (B (C (D E X) H) I (J) (K (L (M))))))

Unfortunately, the CL functions that work on trees/non-flat lists never made their way into the Scheme ecosystem. I wrote Racket implementations of many of them a while back; here's the one for subst for posterity's sake:

(define (subst new old tree #:test [test eqv?] #:key [key identity])
  (cond
    ((test old (key tree)) new)
    ((pair? tree)
     (let ([new-car (subst new old (car tree) #:test test #:key key)]
           [new-cdr (subst new old (cdr tree) #:test test #:key key)])
       (if (and (eqv? (car tree) new-car)
                (eqv? (cdr tree) new-cdr))
           tree
           (cons new-car new-cdr))))
    (else tree)))

> (subst 'b 'a '((f a) (f (a))))
'((f b) (f (b)))
> (subst 'x 'm '((a (b (c (d e (f (m))) h) i (j) (k (l (m)))) n) o (p)))
'((a (b (c (d e (f (x))) h) i (j) (k (l (x)))) n) o (p))
> (subst 'x '(f (g)) '((a (b (c (d e (f (g))) h) i (j) (k (l (m)))))) #:test equal?)
'((a (b (c (d e x) h) i (j) (k (l (m))))))

One thing to note about this implementation is that it reuses subtrees that aren't modified, potentially saving a lot of memory when used on big data structures with sparse replacements.

Upvotes: 0

Óscar López
Óscar López

Reputation: 235994

You need to consider a new case in the recursion: what if the current element in the list is another list? in that case, we need to do a deeper recursion, and descend over both the current element and the rest of the list. Otherwise, check if the current element needs to be replaced, or leave it alone. This is what I mean, notice that this is a faster solution when we only want to replace atoms:

(define repl
  (lambda (exp1 exp2 exp3)
    (cond
      ; base case: list is empty
      ((null? exp3) exp3)
      ; base case: current element is an atom
      ((not (pair? exp3))
       ; should we replace current element?
       (if (equal? exp3 exp1) exp2 exp3))
      ; recursive case: current element is a list
      (else
       ; recursively descend over both sublists
       (cons (repl exp1 exp2 (first exp3))
             (repl exp1 exp2 (rest exp3)))))))

It works as expected, no matter how deeply nested is the element that you want to replace:

(repl 'm 'x '((a (b (c (d e (f (m))) h) i (j) (k (l (m)))) n) o (p)))
=> '((a (b (c (d e (f (x))) h) i (j) (k (l (x)))) n) o (p))

EDIT: Now, if the elements you want to replace are lists themselves, we have to shuffle around the conditions. Below you'll find the implementation, it's more general than my previous solution, but also it's slower. Thanks to @amalloy for suggesting this approach:

(define (repl exp1 exp2 exp3)
  (cond ; base case: list is empty
        ((null? exp3) exp3)
        ; base case: current element is the one we're looking for
        ((equal? exp1 exp3) exp2)
        ; recursive case: current element is a list
        ((pair? exp3) (cons (repl exp1 exp2 (first exp3)) 
                            (repl exp1 exp2 (rest exp3))))
        ; base case: current element is not the one we're looking for
        (else exp3)))

For example:

(repl '(f (g)) 'x '((a (b (c (d e (f (g))) h) i (j) (k (l (m)))))))
=> '((a (b (c (d e x) h) i (j) (k (l (m))))))

Upvotes: 1

alinsoar
alinsoar

Reputation: 15793

try this:

(define replace
  (lambda (x y l)
    (fold-right (lambda (e acc)
                  (if (pair? e)
                      (cons (replace x y e) acc)
                      (cons (if (eq? e x) y e) acc)))
                '()
                l)))

Upvotes: 1

Related Questions