Связные списки

Автоматическая переассоциация бинарных операций

Каноническое слияние связных списков имеет вид

def concat(a, b):
  if is_empty(a): return b
  return join(head(a), concat(tail(a), b))

или же, в итеративном (левосвёрточном) варианте,

def concat(a, b):
  a = reverse(a)  ## предполагается, что reverse разворачивает список
  result = b

  while not is_empty(a):
    result = join(head(a), result)
    a = tail(a)

  return result

Вычислительная сложность такого алгоритма — длина первого входа. По этой причине выражение

concat(a1, concat(a2, concat(a3, ...)))

имеет линейную (по количеству входных списков) сложность, а выражение

concat(...concat(concat(a1, a2), a3) ... )

имеет квадратичную сложность.

В связи с этим очень актуальным является приём (по-видимому, впервые применённый в районе 1854 года математиком Артуром Кэли), позволяющий автоматически «прижимать» (или, по-научному, переассоциировать) все скобки в выражении, использующем некоторую бинарную операцию, вправо.

Продемонстрируем его на примере вычитания чисел. Каждое из чисел, участвующих в формуле нужно обернуть в функцию

def wrap(x): return (lambda y: x-y)

Заметим, что функция wrap является обратимой: wrap(x)(0) == x. В связи с этим реализуем обращение

def unwrap(wrapped): return wrapped(0)

Каждое вычитание нужно заменить на

def sub(a, b): return (lambda x: a(b(x)))

После чего результат такой замены, произведённой над всей формулой, нужно обратить при помощи unwrap:

unwrap(sub(wrap(a), sub(wrap(b), wrap(c)))) ## (a-(b-c))
unwrap(sub(sub(wrap(a), wrap(b)), wrap(c))) ## тоже (a-(b-c))

В тех случаях (весьма редких на практике), когда wrap не является обратимым, приходится искусственно отделять самый правый лист формулы и применять к нему результат преобразования остальной части формулы.

Связь левой и правой свёрток

На настоящий момент является домашним заданием.