Re: substitution in a list

[Ian Grant]

On Tue, 23 Jan 2007 12:20:34 +0100
"orianaparo" <address@hidden> wrote:

> Hi. I'm a newbie and I'm trying to write some programs in Guile.
> I'd like to know how I can perform a substitution in a list.
> I mean:I want to write a function that takes two arguments: a list
> (possibly nested) of symbols [e.g ((a (b c) d) a (f b))] and another
> list that indicate what sort of substitution the function should
> perform [e.g. ((a z) (b y))].

Hi,

It's easiest to first make the program just do flat lists. Then modify
it to work for trees.

To do it for flat lists you first have to be able to do it for just
symbols:

    (define (sym-subst sym sub)
      (let ((rep (assq-ref sub sym)))
         (if (not rep)
             sym
             (car rep))))

Then to do it for a flat list, you just have to be able to do it for the
head of the list (which is a symbol!) and the tail, which is another
list! So 

(define (substitute lst sub)
   (define (iter lst res)
      (if (null? lst)
          (reverse res)
          (iter (cdr lst)       
                (cons (sym-subst (car lst) sub) res))))
   (iter lst '()))

Here you construct the list backwards and then reverse it at the very
end so that (iter ...) is tail-recursive and can handle very long lists
without building up a huge stack.

Now to do it for trees, you just need to check whether (car lst) is a
pair and if so, call cons (iter (car lst) '()) onto the front of the
result instead of (sym-subst (car lst)) You can also make sym-subst a
local procedure so you don't need to pass the substitution lst down as a
parameter each time:

(define (substitute lst sub)
   (define (sym-subst sym)
      (let ((rep (assq-ref sub sym)))
         (if (not rep)
             sym
             (car rep))))
   (define (iter lst res)
      (if (null? lst)
          (reverse res)
          (let ((hd (car lst))) ;; saves lots of calls to car
            (iter (cdr lst)
              (cons
                 (if (symbol? hd)
                     (sym-subst hd)
                     (if (pair? hd)
                         (iter hd '())
                         hd)) ;; not a symbol nor a pair so leave alone
                  res)))))
   (iter lst '()))

Keep practicing, it gets easier!

Cheers
Ian