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

Связные списки — один из наиболее простых взглядов на математическое понятие последовательности.

В математике (конечную) последовательность (элементов множества \(A\)) обычно определяют одним из двух способов:

  • как нечто, сопоставляющее каждому не слишком большому натуральному числу элемент множества \(A\) (совсем формально: как отображение \(\mathbb{N}\supset[1,n]\to X\))
  • как нечто, являющееся либо «пустой последовательностью», либо элементом множества \(A\), «приделанным» к последовательности (совсем формально: как начальную алгебру или же терминальную коалгебру функтора \(X\mapsto 1+A\times X\))

В информатике первому способу соответствует понятие массива. А вот второй способ соответствует как раз связному списку.

Абстрактные типы данных

Вообще говоря, когда мы говорим про какой-то тип данных, мы имеем в виду некий набор операций (интерфейс) с некоторыми правилами их композиции и некоторым набором свойств, которые от этих операций ожидаются.

Например, выражая какой-нибудь алгоритм в терминах массивов, мы обычно используем следующие операции:

  • создать массив заданных длины и содержания
  • узнать длину массива
  • посмотреть на значение такого-то элемента массива
  • изменить значение такого-то элемента массива
  • (иногда) добавить в массив новый элемент
  • (иногда) удалить из массива такой-то элемент

От них мы ожидаем весьма много различных свойств. В частности:

  • если номер элемента меньше длины массива, то изменение этого элемента на значение x с последующим просмотром этого элемента выдаст своим результатом x
  • если добавить в массив новый элемент, его длина увеличится на 1
  • верхняя асимптотическая сложность просмотра элемента массива — (неотрицательная) степень логарифма длины массива

Полный список свойств приводить не будем: он весьма длинный.

Идея такого подхода в следующем: после того, как выписаны все операции и их свойства (набор операций и свойств называется абстрактным типом данных), можно рассматривать конкретные реализации этих операций. Если алгоритм написан в терминах операций абстрактного типа данных, то он будет работать для любой конкретной реализации.

Заметим, что в любом языке программирования большинство встроенных типов данных являются абстрактными: они определяются именно операциями и свойствами, а не конкретной реализацией.

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

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

empty()     # выход: пустой связный список
join(a,l)   # входы: что угодно, связный список; выход: непустой связный список
is_empty(l) # вход: связный список; выход: булево значение
head(l)     # вход: непустой связный список; выход: что-то
tail(l)     # вход: непустой связный список; выход: связный список

Эти операции должны обладать следующими свойствами:

is_empty(empty()) == True
is_empty(join(a,l)) == False
head(join(a,l)) == a
tail(join(a,l)) == l

Под == в этих свойствах понимается не встроенная в Python эквивалентность, а «идеализированная». В Python она может быть приближена выражением вида id(foo) == id(bar).

Также желательно, чтобы асимптотическая сложность всех этих операций была константой (ну или хотя бы степенью логарифма длины списка).

Внимательный читатель может заметить, что на первый взгляд интерфейс связных списков и его свойства совпадают с таковыми у типа «опциональная пара». Это почти так! Единственное различие: типы входов и выходов head и join.

Ещё более внимательный читатель может заметить, что указанных свойств, вообще говоря, недостаточно для предсказуемого поведения: is_empty, например, может очищать поданный ему на вход список. И второе его применение к этому же списку выдаст True. Поэтому нужно дополнительно потребовать, чтобы все вышеописанные функции не имели побочных эффектов. Формально это означает, что добавление вызовов этих функций в произвольные места произвольной программы с произвольными входами не меняет наблюдаемое поведение этой программы (если игнорировать вопрос расхода вычислительных ресурсов).

Изоморфизм массивов и связных списков

Массивы и связные списки, являясь представлениями одной и той же математической концепции — последовательности, — могут быть преобразованы друг в друга:

def list_to_array(l):
  a = []
  
  while not is_empty(l):
    h, l = head(l), tail(l)
    a.append(h)

  return a


def array_to_list(a):
  l = empty()

  ## Обратите внимание на то, что список заполняется в обратном порядке!
  for x in reversed(a):
    l = join(x,l)

  return l

Отметим, что в этих преобразованиях нетривиальным образом участвуют все 5 операций интерфейса связных списков.

Типичные алгоритмы на связных списках

Длина списка:

def list_length(l):
  result = 0

  while not is_empty(l):
    l = tail(l)
    result += 1

  return result

Разворот списка:

def list_reverse(l):
  result = empty()

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

  return result

Применение функции к каждому элементу:

def list_map(l, f):
  result = empty()

  l = list_reverse(l)
  while not is_empty(l):
    h, l = head(l), tail(l)
    result = join(f(h), result)

  return result

Отсев всех элементов, не удовлетворяющих условию:

def list_filter(l, p):
  result = empty()

  l = list_reverse(l)
  while not is_empty(l):
    h, l = head(l), tail(l)
    if p(h): result = join(h, result)

  return result

Слияние двух списков:

def list_concat(l1, l2):
  result = l2
  
  l = list_reverse(l1)
  while not is_empty(l):
    h, l = head(l), tail(l)
    result = join(h, result)

  return result

Проверка двух списков на равенство:

def list_equal(l1, l2):
  while not is_empty(l1):
    if is_empty(l2): return False
    h1, l1 = head(l1), tail(l1)
    h2, l2 = head(l2), tail(l2)
    if h1 != h2: return False

  return is_empty(l2)

Редукция списка

Все эти алгоритмы (с некоторыми оговорками) являются частными случаями следующего:

def reduce(l, init, update):
  result = init

  while not is_empty(l):
    h, l = head(l), tail(l)
    result = update(result, h)

  return result

А именно:

def list_length(l): return reduce(l, 0, lambda s,x: s+1)

def list_reverse(l): return reduce(l, empty(), lambda s,x: join(x,s))

def list_map(l, f):
  return reduce(list_reverse(l), empty(), lambda s,x: join(f(x),s))

def list_filter(l, p):
  return reduce(list_reverse(l), empty(), lambda s,x: join(x,s) if p(x) else s)

def list_concat(l1, l2):
  return reduce(list_reverse(l1), l2, lambda s,x: join(x,s))

## Вот эта вот функция не эквивалентна вышеприведённому аналогу 
## вычислительной сложностью лучшего случая (да и выглядит страшнее).
def list_equal(l1, l2):
  def step(s,x):
    if len(s) == 0: return []
    
    l = s[0]
    if is_empty(l): return []
    if x != head(l): return []
    return [tail(l)]

  result = reduce(l1, [l2], step)
  if len(result) == 0: return False
  return is_empty(result[0])

Функция reduce по-научному называется левой свёрткой списков.

Слияние упорядоченных списоков

Это было одним из домашних заданий:

def list_merge(l1, l2):
  result = empty()

  while not (is_empty(l1) or is_empty(l2)):
    h1, t1 = head(l1), tail(l1)
    h2, t2 = head(l2), tail(l2)

    if h1 < h2: result = join(h1, result); l1 = t1
    else:       result = join(h2, result); l2 = t2

  result = list_reverse(result)
  result = list_concat(result, l1)
  result = list_concat(result, l2)
  return result

Как нетрудно видеть, код почти аналогичен слиянию упорядоченных массивов. Только без «указателей».

Несколько конкретных реализаций связных списков

Здесь мы приведём несколько распространённых кодировок связных списков. Необходимо понимать хотя бы первую из них: остальные приведены для расширения кругозора.

Будем идти от простых к сложным (последние две кодировки интересны тем, что в них не используется вообще ни одной встроенной в язык операции, помимо констант True и False и оператора вызова функции).

Кодировка №1

Вложенные пары:

def empty():     return None
def join(x,l):   return (x,l)
def is_empty(l): return l == None
def head(l):     return l[0]
def tail(l):     return l[1]

Кодировка №2

Словарик:

def empty():     return {}
def join(x,l):   return { "head": x, "tail": l }
def is_empty(l): return len(l) == 0
def head(l):     return l["head"]
def tail(l):     return l["tail"]

Кодировка №3

Объект:

## иерархия -- чисто "для галочки" (она дальше не используется)
class List: pass
class Empty(List): pass
class Node(List):
  def __init__(self, head, tail):
    self.head = head
    self.tail = tail

def empty():     return Empty()
def join(x,l):   return Node(x,l)
def is_empty(l): return isinstance(l,Empty)
def head(l):     return l.head
def tail(l):     return l.tail

Кодировка №4

Ленивые вложенные пары:

def empty():     return lambda: None
def join(x,l):   return lambda: (x,l)
def is_empty(l): return l() == None
def head(l):     return l()[0]
def tail(l):     return l()[1]

Особенностью этой кодировки является возможность моделировать бесконечные списки. Например:

# единицы
ones = lambda: (1, ones)

# целые числа, начиная с заданного
beginning_from = lambda x: lambda: (x, beginning_from(x+1))

# натуральные числа
nats = beginning_from(0)

Впрочем, общаться с ними при помощи алгоритмов, описанных выше, почти невозможно.

Кодировка №5

Катаморфизм (кодировка Чёрча):

def empty():     return lambda z,s: z
def join(x,l):   return lambda z,s: s(x, l(z,s))
def is_empty(l): return l(True, lambda x,r: False)
def head(l):     return l(None, lambda x,r: x)
def tail(l):     return lambda z,s: l(lambda _: z, lambda x,r: lambda u: u(x, r(s))) (lambda a,b: b)

Списки кодируются т.н. правой свёрткой по ним:

def foldr(l,z,s):
  if is_empty(l): return z
  return s(head(l), foldr(tail(l),z,s))
## join(a_1, join(a_2, ... join(a_n, empty()) ... ))
## преобразуется в
## s(a_1, s(a_2, ... s(a_n, z) ... ))

Особенностью этой кодировки является очень неэффективный tail при аппликативном порядке вычисления формул (принятом в большинстве языков программирования, в том числе — в Python).

Также в Python такая кодировка довольно быстро упирается в ограничение глубины рекурсии.

Если интересно, как этот tail работает, то вот так:

# здесь join условно обозначен точкой-с-запятой (;), а empty() -- буквой E
# лямбда-выражения (lambda x1,x2,...,xn: y) кратко обозначены (\x1,x2,...,xn:y)
tail(1;2;3;4;E)(z,s) = 
## далее x&r = \u:u(x,r(s))
(1&2&3&4&(\_: z)             ) (\a,b:b) =       
(1&2&3&(\u:u(4, z))          ) (\a,b:b) =
(1&2&(\u:u(3, s(4, z)))      ) (\a,b:b) =
(1&(\u:u(2, s(3, s(4, z))))  ) (\a,b:b) =
(\u:u(1, s(2, s(3, s(4, z))))) (\a,b:b) =
s(2, s(3, s(4, z)))

Более элементарная кодировка tail может выглядеть так:

def fst(p): return p(lambda a,b:a)
def snd(p): return p(lambda a,b:b)
def tail(l): return snd(l(lambda u: u(empty(), empty()), 
                          lambda x,r: lambda u: u(join(x,fst(r)), fst(r))))

Кодировка №6

Терминальная коалгебра (кодировка Скотта):

def empty():     return lambda z,s: z
def join(x,l):   return lambda z,s: s(x,l)
def is_empty(l): return l(True, lambda x,xs: False)
def head(l):     return l(None, lambda x,xs: x)
def tail(l):     return l(None, lambda x,xs: xs)

Списки кодируются оператором деструктурирования (ветвления по структуре):

def destruct(l,z,s):
  if is_empty(l): return z
  return s(head(l), tail(l))

В этой кодировке (как и в кодировке №4) присутствуют бесконечные списки:

ones = lambda z,s: s(1,ones) 

beginning_from = lambda x: lambda z,s: s(x, beginning_from(x+1))