Given an s-expression '((a . b) . (c . d)) and a list '(e f g h), how can I traverse the s-expression create an s-expression with the same shape, but with elements taken from the list? E.g., for the s-expression and list above, the result would be '((e . f) g . h)?
Traversing a tree of pairs in left to right order isn't particularly difficult, as car and cdr let you get to both sides, and cons can put things back together. The tricky part in a problem like this is that to "replace" elements in the right hand side of a tree, you need to know how many of the available inputs you used when processing the left hand side of the tree. So, here's a procedure reshape that takes a template (a tree with the shape that you want) and a list of elements to use in the new tree. It returns as multiple values the new tree and any remaining elements from the list. This means that in the recursive calls for a pair, you can easily obtain both the new left and right subtrees, along with the remaining elements.
(define (reshape template list)
;; Creates a tree shaped like TEMPLATE, but with
;; elements taken from LIST. Returns two values:
;; the new tree, and a list of any remaining
;; elements from LIST.
(if (not (pair? template))
(values (first list) (rest list))
(let-values (((left list) (reshape (car template) list)))
(let-values (((right list) (reshape (cdr template) list)))
(values (cons left right) list)))))
(reshape '((a . b) . (c . d)) '(e f g h))
;=> ((e . f) g . h)
;=> ()
(reshape '((a . b) . (c . d)) '(e f g h i j k))
;=> ((e . f) g . h)
;=> (i j k) ; leftovers
この記事はインターネットから収集されたものであり、転載の際にはソースを示してください。
侵害の場合は、連絡してください[email protected]
コメントを追加