```
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