merging two lists positionally in Scheme

问题:

Example

First list: (1 2 3 4)

Second list: (* slot (- slot (/ slot slot)))

Output: (* 1 (- 2 (/ 3 4)))

The first list's elements will be inserted to the second list.

The symbol slot in second list means the position for insertion.

My Solution

I have written a code snippet and it works for the above example.

(define (insert-slot numbers slots)
  (cond
    [(null? slots)
     '()]
    ;; operate on the nested list and come back to the element after
    [(pair? (car slots))
     (cons 
           (insert-slot numbers (car slots))     ;; nested list
           (insert-slot numbers (cdr slots)))]   ;; element after
    ;; insert number to slot
    [(equal? (car slots) 'slot)
     (cons (car numbers)
           (insert-slot (cdr numbers) (cdr slots)))]
    ;; just take the original element in slots
    (else
     (cons (car slots)
           (insert-slot numbers (cdr slots))))))

Problem

However, the second clause(operate on the nested list) of the cond has some problems, the numbers used in the nested list and the element after should be different. The later numbers is the result of the previous numbers. It works correctly for the example above, but if the second list likes this (* (+ slot slot) (- slot slot)), it will get the wrong answer.

I figured out that I can store states in the numbers and return different value based on the times it has called, but it's not like the Scheme way(no extra stored data). Is there a simple way to solve this problem ?

回答1:

TL;DR: yes, with continuation-passing style.

---

Very interesting question! Nested list is a tree, so you're merging a linear list of values into a tree's fringe, according to the presence of a keyword 'slot there.

So we start, as is usual in structural recursions tasks, with traversing a tree to just create an exact copy of it, to get a hang of it,

(define (copy-tree tree)
    (cond
       [(not (pair? tree)) tree]                   ; return the leaf
       [else (cons (copy-tree (car tree))          ; combine results from car
                   (copy-tree (cdr tree)))]))      ;     and results from cdr

Next we linearize it by going CPS,

(define (copy-tree tree k)
    (cond
       [(not (pair? tree)) (k tree)]               ; "return" the leaf into k
       [else (copy-tree (car tree) (lambda (r)     ; collect results from car as r
               (copy-tree (cdr tree) (lambda (q)   ;  collect results from cdr as q
                 (k (cons r q))))))]))             ;   "return" combined r and q into k

and then we thread our state through, traversing the list of given values to substitute for each instance of the keyword:

(define (merge-tree-fringe vals tree keywd k)
  (cond
    [(not (pair? tree))                  ; for each leaf:
     (if (not (eq? tree keywd))          ; if it is not the keyword,
       (k vals tree)                     ;   "return" vals AND leaf into k, or
       (k (cdr vals) (car vals)))]       ;   USE the first of vals, if it is
    [else
     (merge-tree-fringe vals (car tree) keywd (lambda (Avals r)    ; collect from car,
      (merge-tree-fringe Avals (cdr tree) keywd (lambda (Dvals q)  ;  collect from cdr,
       (k Dvals (cons r q))))))]))       ; return the last vals and the combined results

We call it as

> (merge-tree-fringe '(1 2 3 4) 
                     '(* slot (- slot (/ slot slot))) 
                     'slot
                     (lambda (v r) r))
'(* 1 (- 2 (/ 3 4)))

> (merge-tree-fringe '(1 2 3 4) 
                     '(* (+ slot slot) (- slot slot))
                     'slot
                     (lambda (v r) r))
'(* (+ 1 2) (- 3 4))

This can be further cleaned up by adding error checking, and converting to an internal definition with shorter name and fewer arguments.

edit: In a pattern-matching pseudocode, which might be easier to read/follow, it is

merge-tree-fringe vals tree keywd = g vals tree (v r => r)
  where
  g vals [a, ...d] k = g vals a (avals r =>
                           g avals d (dvals q => 
                               k dvals [r, ...q]))
  g [v, ...vs] lf  k 
             | lf == keywd = k vs   v     -- use first value for a matching leaf
  g vals       lf  k       = k vals lf

This computational pattern of threading a changing state through the computations is exactly what (Haskell's) State monad is about; the above would be written there (sans the particulars of the "tree" type) as

merge_tree_fringe vals tree keywd = evalState (g tree) vals
    where
    g (a:d)            = do { r <- g a ; q <- g d ; return (r:q) }
    g lf | lf == keywd = do { (v:vs) <- get ; put vs ; return v }
         | otherwise   = do { return lf }

where the state - our "values" - is passed around as part of a "stateful computation pipeline" implicitly, with automatically correct sequencing (which we had to take care of manually, using the avals and dvals carefully each in its appropriate place in our Scheme code); and evalState performs this whole combined computation while discarding the end state, returning only the finally computed value just like our collector/continuation-function (lambda (v r) r) did.

Turning the latter into the former is a matter of a purely syntactic transformation. So it's nothing special, this "monad" thing, after all. It's a computational pattern, explicated, captured.