Большинство функциональных языков используют связанные списки в качестве основной неизменяемой структуры данных. Почему списки, а не, например, деревья? Деревья также могут повторно использовать пути и даже списки моделей.
functional-programming
Филип Хаглунд
источник
источник
Ответы:
Потому что списки проще, чем деревья. (Вы можете увидеть это тривиально по тому факту, что список является вырожденным деревом, где у каждого узла есть только один дочерний элемент.)
Список минусов - это самая простая рекурсивная структура данных произвольного размера.
Во время разработки языка программирования Fortress Гай Стил утверждал, что для массивно параллельных вычислений будущего и наши структуры данных, и наш поток управления должны быть в форме дерева с несколькими ветвями, а не линейными, как сейчас. Но в настоящее время большинство наших базовых библиотек структуры данных были разработаны с учетом последовательной итеративной обработки (или хвостовой рекурсии, это не имеет значения, это одно и то же), а не параллельной обработки.
Обратите внимание, что, например, в Clojure, чьи структуры данных были разработаны специально для параллельного, распределенного, «облачного» современного мира, даже массивы (называемые векторами в Clojure), вероятно, самая «линейная» структура данных из всех, фактически реализованы как деревья.
Итак, вкратце: список минусов - это самая простая из возможных постоянных рекурсивных структур данных, и нет необходимости выбирать более сложное «по умолчанию». Другие, конечно, доступны в качестве опций, например, у Haskell есть массивы, очереди с приоритетами, карты, кучи, трепы, попытки и все, что вы только можете себе представить, но по умолчанию это простой список минусов.
источник
data Tree a = Leaf a | Branch a (Tree a) (Tree a)файлами. Это усиливает ваш аргумент "простоты".Sequenceили ScalaVector), но не используют деревья, когда им нужно только чтение, поскольку они могут достичь этого в истинное постоянное время (например, HaskellVectorили F # через .NetImmutableArray)pmapping над вектором в Clojure по-прежнему обращается к каждому элементу последовательно; древовидная структура вектора обычно скрыта от конечного пользователя.На самом деле, эти списки являются деревьями! У вас есть узлы с двумя полями,
carиcdr, которые могут содержать больше таких узлов или листьев. Единственное , что делает эти деревья в списки, является конвенция интерпретируют поcdrссылке в качестве ссылки на следующий узел в линейном списке, иcarссылки в качестве значения текущего узла.Тем не менее, я предполагаю, что распространенность связанных списков в функциональном программировании связана с преобладанием рекурсии над итерацией. Когда единственной имеющейся циклической конструкцией является (хвостовая) рекурсия, вам нужны структуры данных, которые легко использовать с этим; и связанные списки идеально подходят для этого.
источник