Почему списки минусов связаны с функциональным программированием?

Я заметил, что большинство функциональных языков используют односвязный список (список «минусов») в качестве наиболее фундаментальных типов списков. Примеры включают Common Lisp, Haskell и F #. Это отличается от основных языков, где родные типы списков являются массивами.

Почему это?

Для Common Lisp (будучи динамически типизированным) я понял, что минусы достаточно общие, чтобы также быть основой списков, деревьев и т. Д. Это может быть крошечной причиной.

Однако для статически типизированных языков я не могу найти веских аргументов, я даже могу найти контраргументы:

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

Так почему же предпочитаете связанные списки?

Наиболее важным фактором является то, что вы можете добавить к неизменяемому односвязному списку за O (1) время, что позволяет рекурсивно создавать n-элементные списки за O (n) времени следующим образом:

// Build a list containing the numbers 1 to n:
foo(0) = []
foo(n) = cons(n, foo(n-1))

Если вы сделали это с использованием неизменяемых массивов, время выполнения будет квадратичным, потому что каждая consоперация должна будет копировать весь массив, что приведет к квадратичному времени выполнения.

Функциональный стиль поощряет неизменность, а также обмен данными; массив легче разделить "частично", чем связанный список

Я предполагаю, что под «частичным» разделением вы подразумеваете, что вы можете взять подмассив из массива за O (1) время, тогда как со связанными списками вы можете взять хвост только за O (1), а все остальное нуждается в O (n). Это правда.

Однако взятия хвоста достаточно во многих случаях. И вы должны принять во внимание, что возможность дешевого создания подмассивов не поможет вам, если у вас нет способа дешевого создания массивов. И (без умных оптимизаций компилятора) нет способа дешевого создания массива шаг за шагом.

Я думаю, что все сводится к тому, что списки довольно легко реализуются в функциональном коде.

Схема:

(define (cons x y)(lambda (m) (m x y)))

Haskell:

data  [a]  =  [] | a : [a]

Массивы сложнее и не так привлекательны для реализации. Если вы хотите, чтобы они были очень быстрыми, то они должны быть написаны на низком уровне.

Кроме того, рекурсия работает намного лучше для списков, чем для массивов. Подумайте, сколько раз вы рекурсивно использовали / генерировали список по сравнению с индексированным массивом.

Односвязный список - это самая простая постоянная структура данных .

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

Вы можете легко использовать узлы Cons, только если у вас есть язык для сборки мусора.

Минусы Узлы во многом соответствуют стилю функционального программирования рекурсивных вызовов и неизменяемых значений. Так что это хорошо вписывается в модель умственного программиста.

И не забывайте исторические причины. Почему они по-прежнему называются узлами "минусы", а еще хуже - они используют автомобиль и CDR в качестве аксессуаров? Люди изучают это из учебников и курсов и затем используют это.

Вы правы, в реальном мире массивы намного проще в использовании, они занимают только половину пространства памяти и намного эффективнее из-за пропадания уровня кэша. Нет причин использовать их с обязательными языками.

Связанные списки важны по следующей причине:

Как только вы возьмете число, подобное 3, и преобразуете его в последовательность-преемник, например succ(succ(succ(zero))), и затем примените к нему замену {succ=List node with some memory space}, и {zero = end of list}вы получите связанный список (длиной 3).

Фактически важная часть - это числа, подстановка, пространство памяти и ноль.