Collector Idiom in Scheme - Is this a Design Pattern ?

As a newbie into the world of functional programming (one of my new year resolutions for 2007), I started my venture to learn the skills of constructing recursive processes and manipulating recursive data structures with Friedman and Felleisen's The Little Schemer. I am now into Chapter 8, Lambda The Ultimate, sailing through The Ninth Commandment (Abstract Common Patterns with a new function) and into Page 137 of the text. And here I meet multirember&co(), destined to be my thought-process-companion for the last one week. It took me quite some cycles of stepping through the debugger of DrScheme to figure out the actual computation process going on inside the stacks of lambdas that the function defines.

Here is a copy of the function for those uninitiated to the amazing text ..

(define multirember&co
  (lambda (a lat col)
    (cond
      ((null? lat)
       (col (quote()) (quote())))
      ((eq? (car lat) a)
       (multirember&co a
                       (cdr lat)
                       (lambda (newlat seen)
                         (col newlat
                              (cons (car lat) seen)))))
      (else
       (multirember&co a
                       (cdr lat)
                       (lambda (newlat seen)
                         (col (cons (car lat) newlat)
                              seen)))))))



What does this function call (multirember&co a lat f) do ?

In the words of the authors ..

It looks at every atom of the lat to see whether it is eq? to a. Those atoms that are not are collected in one list ls1; the others for which the answer is true are collected in a second list ls2. Finally it determines the value of (f ls1 ls2).

The statement of work is quite straightforward. I tried implementing the same in another functional language, Erlang, and it did not take me too much time to come up with a supposedly meaningful Erlangy implementation ..

filter_atom(A, L, Col) -> filter_atom(A, L, [], [], Col).

filter_atom(A, [H|T], Has, NotHas, Col) ->
  case (H =:= A) of
    true    -> filter_atom(A, T, [H|Has], NotHas, Col);
    false   -> filter_atom(A, T, Has, [H|NotHas], Col)
  end;

filter_atom(A, [], Has, NotHas, Col) ->
  Col(Has, NotHas).


The Erlang implementation looks simple enough and does not have the accidental complexity that we find in the Scheme implementation.

Honest confession : I am also a newbie in Erlang - any suggestions for improvements towards a more Erlangy modeling is welcome!

Why does the Scheme implementation look so complex ?

Coming back to the Scheme implementation, I am not sure if this is the most idiomatic implementation of the solution. But it definitely is an ample demonstration of the power of closures (lambdas). The inner lambdas build the new collectors by getting stuff from the enclosing scope and constructs values that are handed over to the next collector in the stack. This is precisely what the Tenth Commandment preaches - Build functions to collect more than one value at a time.

Is this a Design Pattern ?

The idiom of using the Collector for building up values has been used in subsequent function implementations as well - refer to multiinsertLR&co() and evens-only*&co() in the same chapter of the book. Given a list, and some predicate, the Collector idiom uses continuation passing style (CPS) to create closures that successively collects multiple values from the list. Is there a design pattern lurking around ?

I am not qualified enough to comment on the virtues of the above Scheme implementation. One great thing about it is that the above implementation is tail recursive. I can come up with an accumulator based implementation, which is not tail recursive, but possibly has less of an accidental complexity.

What do the experts have to say about the collector based idiom ?