Re: substitution in a list

[Luca Saiu]

orianaparo 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))]. This means that the symbol "a" 
has to be substituted by the
> symbol "z" and the symbol "b" by "y".

Ok. I think you should start trying to break this into more manageable 
subproblems: think you have a function substitute-single which takes
your possibly nested list, a symbol s to be replaced and its 
replacement, and returns a new list with all occurrences of s substituted.

By the way, Abelson and Sussman call this way of proceeding 'wishful
thinking'. If you think you need some procedure, just act as you
indeed had it already defined, and just use it. You'll
implement it later.

Ok, what would you do if you had substitute-single ? You'd use to 
perform all the substitutions in your list of pairs
<symbol, replacement>. That's easy, and it will be your substitute
procedure:

(define (substitute list list-of-pairs)
  ...) ; you can call substitute-single here

Hints: to get the first symbol to be replaced from list-of-pairs, you 
can use caar: you want the head of the head of the list. To get the 
replacement for the first symbol you can use cadar: you want the head of 
the rest of the head of the list. To get the other pairs after you're 
done with the first one you can just use cdr (get the rest of the list 
of pairs).
Note that this would be different if you used dotted lists (you should 
try to implement also that case).

Finally you have to implement substitute-single: with only one symbol
to replace it's easy: you just recur on the list searching for all
the occurrences of symbol.

(define (substitute-single list symbol replacement)
  ...)

Both functions, as it's very usual, are built on case analysis. You
should use cond, or if.

Feel free to write again if you have problems.
Bye,

--
Luca Saiu, maintainer of GNU epsilon
http://www.gnu.org/software/epsilon
http://www.di.unipi.it/~saiu