Saturday, October 4, 2014

Merging Uniquishly in Common Lisp

I've been working on some code with dxf files and I needed to have some generalized merging. In particular, for my first function, I wanted to merge headers without creating duplicate entries. My reader sorts the header values, so when I go to merge I just need to have a simple merge that looks at each of two lists and collects the lowest value and only advances the list that had an element "consumed" (as in, I collected it). If the values are equal, it should collect one instance, and consume from both lists (i.e., advance—take the cdr of—both lists).

The approach I've taken does not guarantee a list of unique items, only that if the original lists are sorted and contain no duplicates, then the resulting list will be sorted and contain no duplicates.  It is also non-destructive, returning a new list

(Confession: Actually, I did it the hard way the first time. Custom code that can only do one thing. Now I'm going back and amending my ways as an ardent Lisper.)

I went with a loop macro for one reason: the collect key word. This is one of the things that keeps me coming back to the loop macro. I like it overall, but when I'm struggling with the loop macro, I sometimes want to use the do* macro.  But I dislike the way do* lends itself to consing and a final call to reverse.  Hence, I come back whimpering to the loop macro.

The code:



Here's some sample output from an EMACS session:



The custom code solution was 23 lines and not so pleasant looking. The tri-test follows the custom of using a negative value to indicate a < b, positive for a > b, and 0 for a = b.  For numeric data, subtraction is the natural choice for a tri-test.

I tried using some for keywords inside of if statements and my horse (compiler) wouldn't make the jump.  But that's okay, I used a for statement at the beginning to initialize some variables (nexta and nextb) which I could then setf within do clauses as necessary.

The more I use the loop macro, the more I like it. Eventually, maybe I will discover all of the things that cause it to choke, stop doing those things, and then I will like it even more.