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 ..
(lambda (a lat col)
(col (quote()) (quote())))
((eq? (car lat) a)
(lambda (newlat seen)
(cons (car lat) seen)))))
(lambda (newlat seen)
(col (cons (car lat) newlat)
What does this function call
(multirember&co a lat f)do ?
In the words of the authors ..
It looks at every atom of the
latto see whether it is
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)
filter_atom(A, , Has, NotHas, Col) ->
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
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 ?