Давайте используем эквациональный псевдокод с некоторыми круглыми скобками, опущенными для ясности (поэтому мы пишем f x y для вызова (f x y), где это однозначно):
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
Разве это не самоочевидно, что это делает? :) Еще нет? :) Переписав снова с воображаемым псевдокодом для сопоставления с образцом (с защитой), мы получим
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 [] []
Семантика сопоставления с образцом должна быть достаточно очевидной: [b, ...lat] соответствует [1,2,3], где b = 1 и lat = [2,3]. Таким образом, это всего лишь три уравнения:
Когда второй аргумент является пустым списком, функция «сборщик» col сразу получает два пустых списка в качестве двух аргументов;
Когда элемент второго аргумента (который является списком) head совпадает с первым аргументом, результат такой же, как и для рекурсии с хвостом списка с измененным коллектором, который - после получит два аргумента, n и s, - добавят к текущему элементу head (который является a) в список s, и эти два списка будут переданы в функцию сбора этого вызова col;
В противном случае элемент заголовка будет добавлен к списку n, после того как n и s будут получены построенным коллектором, и оба будут далее использованы в функции токосъемника.
Другими словами, мы имеем дело с двумя результатами, возвращающимися из рекурсивного вызова, с добавлением головы ко второму, если голова была a, или к первому, если это не так.
Таким образом, вызов
(g 1 [ 2, 1, 3, 1, 4, 5 ] col)
- это то же самое, что (вызовет) вызов
(col [ 2, ...[3, ...[4, ...[5, ...[]]]]]
[ 1, ...[1, ...[]] ])
т.е. * * тысяча пятьдесят-семь
(col [ 2, 3, 4, 5 ]
[ 1, 1 ])
Еще один способ взглянуть на это состоит в том, что следующее является другой, эквивалентной формулировкой:
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 [])
и, следовательно,
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 []) ) )
что самоочевидно одно и то же.
В еще одном псевдокоде (со списком) это показывает, что оно
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
за исключением того, что только один обход списка lat выполняется (в исходном коде), эффективно, создавая вложенную цепочку лямбда-функций, имитирующую исходную структуру списка; какая цепочка затем оценивается для создания двух результатов, передавая их самой верхней функции коллектора col.
Все это показывает нам мощь Стиль продолжения-продолжения (что и есть) для создания собственного протокола вызова функций, например, для передачи обратно two результат каждого рекурсивного вызова функции, хотя обычно в лямбда-исчислении функция может иметь только один результат (даже если, скажем, пара).