Let's use some equational pseudocode with some parentheses omitted for clarity (so, we write f x y for the call (f x y), where this is unambiguous):
multirember&Co a lat col
= col [] [] , IF lat == []
= multirember&Co a (cdr lat)
( newlat seen =>
col newlat
(cons (car lat) seen) ) , IF (car lat) == a
= multirember&Co a (cdr lat)
( newlat seen =>
col (cons (car lat) newlat)
seen ) , OTHERWISE
Isn't it just self-evident, what this does? :) Not yet? :) Re-writing again with an imagined pattern-matching pseudocode (with guards), we have
multirember&Co = g where
g a [b, ...lat] col | b == a = g a lat ( n s => col n [b, ...s] )
| else = g a lat ( n s => col [b, ...n] s )
g a [] col = col [] []
The semantics of pattern matching should be quite obvious: [b, ...lat] matches [1,2,3] where b = 1 and lat = [2,3]. This is thus just a three-cased equation:
When the second argument is an empty list, the "collector" function col is fed two empty lists as its two arguments right away;
When the second argument's (which is a list) head element is the same as the first argument, the result is the same as that for recursing with the tail of the list, with the amended collector which -- after it will receive its two arguments, n and s, -- will prepend the current head element (which is a) to the s list, and will feed the two lists to this invocation's collector function col;
Otherwise, the head element will be prepended to the n list, after n and s are received by the constructed collector, and the both will be fed further into the current collector function.
In other words we're dealing with two results coming back from the recursive call, prepending the head to the second if the head was a, or to the first if it wasn't.
Thus the call
(g 1 [ 2, 1, 3, 1, 4, 5 ] col)
is the same as (will result in) the call
(col [ 2, ...[3, ...[4, ...[5, ...[]]]]]
[ 1, ...[1, ...[]] ])
i.e.
(col [ 2, 3, 4, 5 ]
[ 1, 1 ])
Another way to look at it is that the following is another, equivalent formulation:
multirember&Co a lat col = g a lat id id where
id x = x ; identity function
(f ∘ g) x = f (g x) ; function composition
g a [b, ...lat] c d
| b == a = g a lat c (d ∘ (x => cons b x)) ; (d ∘ {cons b})
| else = g a lat (c ∘ (x => cons b x)) d ; (c ∘ {cons b})
g a [] c d = col (c []) (d [])
and thus
multirember&Co 1 [ 2, 1, 3, 1, 4, 5 ] col
=
col (((((id ∘ {cons 2}) ∘ {cons 3}) ∘ {cons 4}) ∘ {cons 5}) []) ; { } is for
( ( (id ∘ {cons 1}) ∘ {cons 1} ) []) ; partial application
=
col (id (cons 2 (cons 3 (cons 4 (cons 5 [])))))
(id (cons 1 (cons 1 []) ) )
which is self-evidently the same thing.
In yet another pseudocode (with list comprehensions), this reveals itself to be
multirember&Co a lat col
= col [ b for b in lat if (b /= a) ]
[ b for b in lat if (b == a) ]
= ( ((n,s) => col n s) ∘ {partition {/= a}} ) lat
except that only one traversal of the list lat is performed (in the original code), efficiently, building the nested chain of lambda functions mimicking the original list structure; which chain is then evaluated to create the two results, passing them to the top-most collector function col.
All this shows us the power of Continuation-Passing Style (which is what this is) to, in effect, create its own function call protocol, here for example passing back two results from each recursive function call, even though normally in lambda calculus a function can only have one result (even if, say, a pair).
