# Collectors in Scheme

Collector functions are a functional way of processing and accumulating collections of data. I recently encountered this pattern while going through the book The Little Schemer. In the discussion of lambdas, there’s a function named `multirember&co`, which stands for “remove multiple members and collect”. Basically, it removes multiple elements from a list and collects the removed elements."

This function is a good, nontrivial example of collector functions. Once I worked through it, I decided writing a short blog post about it would be helpful so others could benefit.

``````(define multirember&co
(lambda (a lat col)
(cond
; (1) Base case. Collect empty lists.
((null? lat) (col (quote ()) (quote ())))
; (2) The head of the list is equal to `a`. Collect it in `seen`.
((eq? a (car lat))
(multirember&co a
(cdr lat)
(lambda (newlat seen)
(col newlat (cons (car lat) seen)))))
; (3) The head of the list is not equal to `a`. Collect it in `newlat`.
(else
(multirember&co a
(cdr lat)
(lambda (newlat seen)
(col (cons (car lat) newlat) seen)))))))
``````

This function has three arguments: the value `a` to be removed from the list, the list `lat`, and a collector function `col`. It looks at every element of the list `lat` to see if it is equal to `a`. If so, it collects them in a list (`seen` ). If not, it collects them in another list (`newlat`).

The recurrence for this function at first seems complicated. At each step, this function recurs by building a new lambda function that uses the given collector to prepend an element to one of the lists. It then passes this new lambda down to the next call of `multirember&co`.

Let’s walk through the expansion of `(multirember&co 'b '(a b c b) list)`. I will name the collector lambda at each step to make it easier to see what’s happening. At each step, comments describe what’s going on with the expansion:

``````; Initial: Name the collector that's passed in as `col-0`
(define col-0 list)

; Step-1:
(multirember&co 'b '(a b c b) col-0)

; `b` does not match the head of the list `a`. The code builds a
; new lambda for recursion. Call it `col-1`.
(define col-1
(lambda (newlat seen)
(col-0 (cons 'a newlat) seen)))

; Step-2:
(multirember&co 'b '(b c b) col-1)

; `b` matches the head of the list. Name the new lambda for the
; recursion as `col-2`.
(define col-2
(lambda (newlat seen)
(col-1 newlat (cons 'b seen))))

; Step-3:
(multirember&co 'b '(c b) col-2)

; `b` does not match the head of the list. Name the new lambda
; for the recursion as `col-3`.
(define col-3
(lambda (newlat seen)
(col-2 (cons 'c newlat) seen)))

; Step-4:
(multirember&co 'b '(b) col-3)

; `b` matches the head of the list. Name the new lambda for the
; recursion as `col-4`:
(define col-4
(lambda (newlat seen)
(col-3 newlat (cons 'b seen))))

; Step-5:
(multirember&co 'b '() col-4)
((null? lat) (col-4 '() '()))
``````

At the last step, the stack of function calls logically looks as follows:

``````(col-4 '() '())
;|_____|
;   |
;   |
(define col-4
(lambda (newlat seen)
(col-3 newlat (cons 'b seen))))
;   |_____|
;      |
;      |
(define col-3
(lambda (newlat seen)
(col-2 (cons 'c newlat) seen)))
;   |_____|
;      |
;      |
(define col-2
(lambda (newlat seen)
(col-1 newlat (cons 'b seen))))
;   |_____|
;      |
;      |
(define col-1
(lambda (newlat seen)
(col-0 (cons 'a newlat) seen)))
;   |_____|
;      |
;      |
(define col-0 list)
``````

Without the labels, the actual expansion (below) is much harder to parse and understand!

``````((lambda (newlat4 seen4) ; col-4
((lambda (newlat3 seen3) ; col-3
((lambda (newlat2 seen2) ; col-2
((lambda (newlat1 seen1); col-1

(col-0 (cons 'a newlat1) seen1)) ; arguments to col-0
newlat2 (cons 'b seen2))) ; arguments to col-1
(cons 'c newlat3) seen3)) ; arguments to col-2
newlat4 (cons 'b seen4))) ; arguments to col-3

'() '()
)
``````

Executing the above block results in `'((a c) (b b))`, which is what we expect.

Another way of looking at the expansion above is with the computed arguments for each lambda:

``````(col-4 '() '())
(col-3 '() '(b))
(col-2 '(c) '(b))
(col-1 '(c) '(b b))
(col-0 '(a c) '(b b))

; `col-0` is `list`
(list '(a c) '(b b))
('(a c) '(b b))
``````

Hopefully this expansion of `multirember&co` gives a clearer idea of how collector functions behave and are used in Scheme. This analysis applies generally to other functional programming languages as well.