How would I write a function in Dr. Racket which consumes a list of 2 possible symbols ('c or 'v) and replaces them with something else? If the symbol is 'c, then it gets replaced with 'c 'v If the symbol is 'v, then it gets replaced with 'v 'c
Here is my code so far:
(define (awesome c)
(cond
[(equal? c 'c) (list 'c 'v)]
[else (list 'v 'c)]))
(define (substitute los)
(map awesome los))
If I type in:
(substitute (list 'c 'v 'c 'c))
My desired output is
(list 'c 'v 'v 'c 'c 'v 'c 'v)
Instead, I get:
(list (list 'c 'v) (list 'v 'c) (list 'c 'v) (list 'c 'v))
Why is this happening? How can I correct my code to achieve the correct output? Thanks.
Each symbol in the input is generating a list of two symbols in the output. Use append
to combine the lists, e.g.:
scratch.rkt> (append '(c v) '(v c) '(c v) '(c v))
'(c v v c c v c v)
Since map
is creating a list that contains sublists, use apply
to apply append
to the sublists:
(define (substitute los)
(apply append (map awesome los)))
Sample interaction:
scratch.rkt> (substitute (list 'c 'v 'c 'c))
'(c v v c c v c v)
You could take a more flexible approach by using a list of term rewriting rules. This would allow you to change the substitution rules without changing your code. The term rewriting rules could be represented as a list of lists, with an arrow separating the input term from the rewrites:
(define cv-rules '((c -> c v)
(v -> v c)))
It is useful to define a couple of functions that get the rule for a term and a list of rewrites from a rule. Abstracting these operations to functions makes it easier to change the representation of a rule later, and helps keep the code clear:
(define (get-rule term rules)
(assoc term rules))
(define (get-rewrites rule)
(cddr rule))
This get-rewrites
function can be used in another function that rewrites a term based on the rules. Here, any symbol which does not have a specific rule is just returned in a list by itself:
(define (rewrite-term x rules)
(let ((rule (get-rule x rules)))
(if rule
(get-rewrites rule)
(list x))))
Now the rewrite-term
function can be mapped over the input, together with rewrite rules. As before, the mapping results in a list of sublists, so append
is applied to the result before returning:
(define (rewrite terms rules)
(apply append (map (lambda (x) (rewrite-term x rules)) terms)))
Now you can easily change the way that substitutions are made by defining a new set of rewrite rules.
Sample interactions:
scratch.rkt> (rewrite '(c v c c) cv-rules)
'(c v v c c v c v)
scratch.rkt> (rewrite '(c v c x c) cv-rules)
'(c v v c c v x c v)
With a small change to the rewrite-term
function, you can apply the rewrite rules recursively to nested lists of terms. When the term to rewrite is itself a nonempty list with no rewrite rule, rewrite
is called on that term. Note that all rewrites are wrapped in lists before being returned. This new function behaves as before for the original rules, but allows more complex rules, too:
(define (rewrite-term x rules)
(let ((rule (get-rule x rules)))
(cond (rule (get-rewrites rule))
((pair? x) (list (rewrite x rules)))
(else
(list x)))))
Sample interactions:
scratch.rkt> (define cv2-rules '((c -> v)
(v -> (c v))))
scratch.rkt> (rewrite '(c v c c) cv2-rules)
'(v (c v) v v)
scratch.rkt> (rewrite '(v (c v) v v) cv2-rules)
'((c v) (v (c v)) (c v) (c v))
scratch.rkt> (rewrite '((c v) (v (c v)) (c v) (c v)) cv2-rules)
'((v (c v)) ((c v) (v (c v))) (v (c v)) (v (c v)))