Design pattern for consuming two lists in parallel, and returning the remainder of one of the lists

Question

Absract: The abstract problem is:

• a list of values
• a list of modifiers, things that act on the values to return new values (for the example code I'm just multiplying the value by the modifier value)
• the list of modifiers is not constrained to be the same size as the list of values.
• apply the modifiers to the values, and get back any unused modifiers

Here's a version that that uses two separate functions: one to actually apply the modifiers, one to get the remaining modifiers

;; Return the modified list
(define (apply-mods vals mods) 
    (if (or (null? vals) (null? mods)) vals
      (cons (* (car vals) (car mods)) (apply-mod (cdr vals) (cdr mods)))
    )
)
;; trim the modifiers 
(define (trim-mods vals mods)
    (if (or (null? vals) (null? mods)) mods
    (trim-mods (cdr vals) (cdr mods))
)

The idea is that after I apply the list of modifiers, (apply-mods vals mods) I may want to use the remaining modifiers (trim-mods vals mods) in subsequent operations.

Currently, the best approach I've come up with is the two function approach, but it seems wasteful to iterate though the list twice.

Is there a clean way to return both the modified values, and the unused modifiers?

Concrete The concrete problem is:

• my values are musical notes; each has a volume and a duration. Something like: (vol: 1, dur: 1 beat)(vol: 1 dur: 2 beats)(vol: 1 dur: 1 beat)...
• my modifiers are "changes to the volume", each has a volume change and a duration (dvol: +1 dur: 4 beats)(dvol: -2 dur: 4 beats)...
• as I recurse through the lists, I keep track of the net accumulated time to determine which modifier is in effect for a given note.

So in the real problem there is not the easy 1-1 mapping of modifiers to values, and thus I expect to run into situations where I'll apply a list of modifiers to a list of note that is shorter (in terms of duration) than the note list; I'll then want to apply the remaining modifiers to the next note list (I plan on breaking the overall music into chunks).

Answer 1

Assuming these are the expected results:

> (apply-mods '((1 . 10)) '((1 . 4) (2 . 4) (3 . 4)))
'((2 . 4) (3 . 4) (4 . 2))
'((3 . 2))

> (apply-mods '((1 . 1) (1 . 2) (1 . 1)) '((+1 . 4) (-2 . 4)))
'((2 . 1) (2 . 2) (2 . 1))
'((-2 . 4))

this is a simple loop processing 2 lists in parallel:

(define (apply-mods vals mods)
  (let loop ((vals vals) (mods mods) (res null))
    (cond
      ((null? vals) (values (reverse res) mods))
      ((null? mods) (error "not enough mods"))
      (else
       (let ((val (car vals)) (mod (car mods)))
         (let ((vol (car val)) (dur (cdr val)) (dvol (car mod)) (ddur (cdr mod)))
           (cond
             ; case 1. duration of note = duration of mod => consume note and mod
             ((= dur ddur)
              (loop (cdr vals) 
                    (cdr mods) 
                    (cons (cons (+ vol dvol) dur) res)))
             ; case 2. duration of note < duration of mod => consume note, push back shorter mod
             ((< dur ddur) 
              (loop (cdr vals) 
                    (cons (cons dvol (- ddur dur)) (cdr mods)) 
                    (cons (cons (+ vol dvol) dur) res)))
             ; case 3. duration of note > duration of mod => push back part of note, consume mod
             (else         
              (loop (cons (cons vol (- dur ddur)) (cdr vals)) 
                    (cdr mods) 
                    (cons (cons (+ vol dvol) ddur) res))))))))))

It seems that your requirement is even simpler, and you probably only need to cover case 1, but I can only speculate while waiting for an example. In any case, you will be able to adapt this code to your specific need quite easily.

Answer 2

It sounds like you may want a mutable data structure such as a queue.

(make-mod-queue '(dvol: +1 dur: 4 beats)(dvol: -2 dur: 4 beats)...))

#queue((4 (dvol: +1)) (4 (dvol: -2)) ...)

(make-note-queue '(vol: 1, dur: 1 beat)(vol: 1 dur: 2 beats)(vol: 1 dur: 1 beat))

#queue((1 (vol" 1)) (1 (vol: 1)) (2 (vol: 1))

Then a function to combine them

(define (apply-mods note-queue mod-queue)
 (let ((new-queue make-empty-queue))
       (get-note-dur (lambda () 
                      (if (emtpy-queue? note-queue)
                          #f  
                          (car (front-queue note-queue)))))
       (get-mod-dur (lambda () 
                      (if (empty-queue? mod-queue)
                          #f
                          (car (front-queue mod-queue)))))
       (get-vol 
          (lambda () 
            (if (or (empty-queue? mod-queue) (empty-queue? mod-queue))
                 #f        
                 (+ (note-vol (front-queue note-queue)) 
                    (mod-vol  (front-queue mod-queue)))))))
   (let loop ((d1 (get-note-dur)) ;;should return #f is note-queue is empty
              (d2 (get-mod-dur))  ;;ditto for mod-queue
              (vol (get-volume))) 
    (cond ((not vol) 
           (cond ((and d2 (not (= d2 (get-mod-dur))))
                  (set-car! (front-queue mod-queue) d2) new-queue)
                  new-queue)
                 ((and d1 (not (= d1 (get-note-dur))))
                  (set-car! (front-queue note-queue) d1) new-queue)
                  new-queue)
                 (else new-queue)))
          ((= d1 d2)
           (insert-queue! new-queue (cons d1 (list 'vol: vol)))
           (delete-queue! note-queue)
           (delete-queue! mod-queue)
           (loop (get-note-dur) (get-mod-dur) (get-volume)
          ((< d1 d2)
           (insert-queue! new-queue (cons d1 (list 'vol: vol)))
           (delete-queue! note-queue)
           (loop (get-note-dur) (- d2 d1) (get-volume)))
          ((> d1 d2)
           (insert-queue! new-queue (cons d2 (list 'vol: vol)))
           (delete-queue! mod-queue)
           (loop (- d1 d2) (get-mod-dur) (get-volume)))))))

Would return #queue (1 (vol" 2)) (1 (vol: 2)) (2 (vol: 2) and your mod-queue (whatever you passed it in as would now be mutated to #queue (4 (dvol: -2)) ...), and the original note-queue is now an empty-queue

queues as described in SICP

http://mitpress.mit.edu/sicp/full-text/sicp/book/node62.html