Subject: Re: Walking two lists together?
From: rpw3@rpw3.org (Rob Warnock)
Date: Sat, 09 May 2009 20:07:58 -0500
Newsgroups: comp.lang.lisp
Message-ID: <69GdnQ3BgpVztZvXnZ2dnUVZ_uSdnZ2d@speakeasy.net>
GP lisper  <spambait@clouddancer.com> wrote:
+---------------
| For future reference, is there a simple way to walk two lists
| simultaneously?  I can only think of 'aref as a solution, with
| careful "pointer" manipulation.
+---------------

Others have dealt with the case of truly *simultaneous* (synchronized)
walking [MAP, LOOP, etc.], but you indicated you wanted something
more like pushing an examination window down each list independently.
ISTM that the general name for this just might be "merge sort" ;-}  ;-}
<http://en.wikipedia.org/wiki/Merge_sort>, or at least the merge
phase of it.

I've occasionally had to do things like that, and the result tended
to look something like one of the following three examples [from more
generic to more low-level/bit-fiddly], which all just a LOOP wrapped
around one of the common forms of a finite state machine [with only
one state(!), though more states could easily be added]:

    (loop with in1 = input-list-1
	  and in2 = input-list-2
	  while (or in1 in2)
	  ;; CHOICE-FUNCTION returns a keyword naming the desired action.
	  for next-pick = (choice-function (first in1) (first in2)
					   (second in1) (second in2)
					   ...extend-window-as-needed...)
      when (eq next-pick :in1)
	collect (pop in1)
      when (eq next-pick :in2)
	collect (pop in2)
      when (eq next-pick :both)
	collect (pop in1)
       and
	collect (pop in2)
      when (eq next-pick :drop1)
	do (pop in1)
      when (eq next-pick :drop2)
	do (pop in2)
      when (eq next-pick :drop-both)
	do (pop in1) (pop in2))

Or you may prefer to do the collection yourself for more Lispy control:

    (loop with in1 = input-list-1
	  and in2 = input-list-2
	  and result = nil
	  while (or in1 in2)
      do (case (choice-function (first in1) (first in2)
				(second in1) (second in2)
				...extend-window-as-needed...)
	   ((:in1) (push (pop in1) result))
	   ((:in2) (push (pop in2) result))
	   ((:both) (push (pop in1) result) (push (pop in2) result))
	   ((:drop1) (pop in1))
	   ((:drop2) (pop in2))
	   ((:drop-both) (pop in1) (pop in2)))
      finally (return (nreverse result)))

Or even finer-grained spreading of the choice function [note that this
version does *not* implement exactly the same algorithm as the above]:

    (loop with in1 = input-list-1
	  and in2 = input-list-2
	  and result = nil
	  while (or in1 in2)
      do (cond
	   ((strange-deep-look-test (first in1) (first in2)
				    (second in1) (second in2))
	    (push (average (first in1) (second in2)) result)
	    (push (average (first in2) (second in1)) result)
	    (pop1 in1)
	    (pop1 in1)
	    (pop1 in2)
	    (pop1 in2))
	   ((definitely-better-p (first in1) (first in2))
	    (push (pop in1) result)
	    (pop in2))
	   ((definitely-better-p (first in2) (first in1))
	    (push (pop in2) result)
	    (pop in1))
	   ((good-enough-p (first in1))
	    (push (pop in1) result))
	   ((good-enough-p (first in2))
	    (push (pop in2) result))
	   (t ; Neither is even "good enough", so drop both.
	    (pop in1)
	    (pop in2)))
      finally (return (nreverse result)))

The above styles can all be easily extended to three or more input
lists [or sets, or vectors, whatever], along with more states to
remember history of previous choices/actions, but the choice functions
and actions sections will get messier and messier. As some point it
will become advantageous to define a DSL for the desired processing
which compiles into a giant TAGBODY.  ;-}


-Rob

-----
Rob Warnock			<rpw3@rpw3.org>
627 26th Avenue			<URL:http://rpw3.org/>
San Mateo, CA 94403		(650)572-2607