Каким образом в функциональном программировании достигается неразрушающее манипулирование коллекциями с эффективным использованием памяти?

Question

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

Вот как далеко я дошел до сих пор:

Используя F#, я придумал функцию insert который разбивает список на две части и вводит новый промежуточный элемент, по-видимому, без клонирования всех неизмененных элементов:

// return a list without its first n elements:
// (helper function)
let rec skip list n =
    if n = 0 then
        list
    else
        match list with
        | []    -> []
        | x::xs -> skip xs (n-1)

// return only the first n elements of a list:
// (helper function)
let rec take list n =
    if n = 0 then
        []
    else
        match list with
        | []    -> []
        | x::xs -> x::(take xs (n-1))

// insert a value into a list at the specified zero-based position:
let insert list position value =
    (take list position) @ [value] @ (skip list position)

Затем я проверил, перерабатываются ли объекты из исходного списка в новые списки с помощью.NET Object.ReferenceEquals:

open System

let (===) x y =
    Object.ReferenceEquals(x, y)

let x = Some(42)
let L = [Some(0); x; Some(43)]
let M = Some(1) |> insert L 1

Следующие три выражения все оценивают как true, указывая, что значение, указанное x повторно используется как в списках L а также Mт.е. что в памяти есть только 1 копия этого значения:

L.[1] === x
M.[2] === x
L.[1] === M.[2]

Мой вопрос:

Функциональные языки программирования обычно используют значения вместо клонирования их в новую область памяти, или мне просто повезло с поведением F#? Предполагая, что первое, это то, как разумно-эффективное редактирование коллекций может быть реализовано в функциональном программировании?

(Кстати: я знаю о книге Криса Окасаки " Чисто функциональные структуры данных", но еще не было времени, чтобы прочитать ее полностью.)

Answer 1

Я пытаюсь выяснить, как неразрушающее манипулирование большими коллекциями реализуется в функциональном программировании, т.е. как можно изменять или удалять отдельные элементы, не создавая совершенно новую коллекцию, в которой все элементы, даже неизмененные, будут дублироваться в памяти.

На этой странице есть несколько описаний и реализаций структур данных в F#. Большинство из них исходят из чисто функциональных структур данных Окасаки, хотя дерево AVL - это моя собственная реализация, так как оно не было представлено в книге.

Теперь, поскольку вы спросили, о повторном использовании неизмененных узлов, давайте возьмем простое двоичное дерево:

type 'a tree =
    | Node of 'a tree * 'a * 'a tree
    | Nil

let rec insert v = function
    | Node(l, x, r) as node ->
        if v < x then Node(insert v l, x, r)    // reuses x and r
        elif v > x then Node(l, x, insert v r)  // reuses x and l
        else node
    | Nil -> Node(Nil, v, Nil)

Обратите внимание, что мы повторно используем некоторые из наших узлов. Допустим, мы начнем с этого дерева:

Когда мы вставляем e в дерево мы получаем совершенно новое дерево, некоторые узлы которого обращены назад к нашему исходному дереву:

Если у нас нет ссылки на xs Если дерево выше, то.NET будет собирать любые узлы без живых ссылок, особенноd, g а также f узлы.

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

Функциональные языки программирования обычно используют значения вместо клонирования их в новую область памяти, или мне просто повезло с поведением F#? Предполагая, что первое, это то, как разумно-эффективное редактирование коллекций может быть реализовано в функциональном программировании?

Да.

Списки, однако, не очень хорошая структура данных, так как большинство нетривиальных операций над ними требуют O(n) времени.

Сбалансированные двоичные деревья поддерживают O(log n) вставок, то есть мы создаем O(log n) копий при каждой вставке. Поскольку log₂(10 ^ 15) составляет ~= 50, накладные расходы очень и очень малы для этих конкретных структур данных. Даже если вы будете хранить каждую копию каждого объекта после вставки / удаления, ваше использование памяти будет увеличиваться со скоростью O(n log n) - на мой взгляд, очень разумно.

Answer 2

Как можно изменить или удалить отдельные элементы, не создавая совершенно новую коллекцию, в которой все элементы, даже неизмененные, будут дублироваться в памяти.

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

let shared = ["two", "three", "four"]
let l      = "one" :: shared
let l'     = "1a"  :: shared

Эти два списка имеют shared общие части и их первые элементы разные. Что менее очевидно, так это то, что каждый список также начинается с уникальной пары, часто называемой "cons-ячейкой":

• Список l начинается с пары, содержащей указатель на "one" и указатель на общий хвост.

• Список l' начинается с пары, содержащей указатель на "1a" и указатель на общий хвост.

Если бы мы только объявили l и хотел изменить или удалить первый элемент, чтобы получить l'мы бы сделали это:

let l' = match l with
         | _ :: rest -> "1a" :: rest
         | []        ->  raise (Failure "cannot alter 1st elem of empty list")

Существует постоянная стоимость:

• Трещина l в его голову и хвост, исследуя камеру против.

• Выделите новую ячейку минусов, указывающую на "1a" и хвост.

Новая ячейка cons становится значением списка l',

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

• Застежка-молния Джерарда Хуэта может быть определена для любой древовидной структуры данных и может использоваться для обхода и точечных модификаций при постоянных затратах. Молнии легко понять.

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

Answer 3

Хотя ссылочные объекты в вашем коде одинаковы, я считаю, что место для хранения самих ссылок и структура списка дублируется take, В результате, в то время как упомянутые объекты одинаковы, а хвосты совместно используются двумя списками, "ячейки" для начальных частей дублируются.

Я не эксперт в функциональном программировании, но, возможно, с каким-то деревом вы могли бы добиться дублирования только элементов log(n), так как вам пришлось бы воссоздавать только путь от корня до вставленного элемента.

Answer 4

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

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

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

Аналогичным образом неизменные структуры данных обладают внутренней ссылочной прозрачностью своей структуры (но не их содержимого). Предполагая, что все содержащиеся значения также являются неизменяемыми, это означает, что фрагменты структуры можно безопасно использовать в новых структурах. Например, хвост списка минусов часто можно использовать повторно; в вашем коде я бы ожидал, что:

(skip 1 L) === (skip 2 M)

... также будет правдой.

Повторное использование не всегда возможно, хотя; начальная часть списка, удаленная вашим skip функция не может быть повторно использована, например. По той же причине добавление чего-либо в конец списка "против" является дорогостоящей операцией, поскольку оно должно реконструировать целый новый список, аналогично проблеме с конкатенацией строк с нулевым символом в конце.

В таких случаях наивные подходы быстро попадают в область ужасной производительности, которая вас беспокоит. Часто необходимо существенно переосмыслить фундаментальные алгоритмы и структуры данных, чтобы успешно адаптировать их к неизменным данным. Методы включают разбиение структур на многоуровневые или иерархические части для изоляции изменений, инвертирование частей структуры для предоставления дешевых обновлений часто изменяемым частям или даже сохранение исходной структуры вместе с коллекцией обновлений и объединение обновлений с оригиналом только на лету когда к данным обращаются.

Поскольку вы используете F# здесь, я предполагаю, что вы, по крайней мере, немного знакомы с C#; у бесценного Эрика Липперта есть множество постов о неизменных структурах данных в C#, которые, вероятно, просвещают вас намного дальше того, что я мог бы предоставить. В течение нескольких постов он демонстрирует (достаточно эффективные) неизменяемые реализации стека, двоичного дерева и двусторонней очереди, среди прочего. Восхитительное чтение для любого программиста.NET!

Answer 5

Возможно, вас заинтересуют стратегии сокращения выражений в функциональных языках программирования. Хорошая книга на эту тему - "Внедрение языков функционального программирования" Саймона Пейтона Джонса, одного из создателей Haskell. Обратите особое внимание на следующую главу Сокращение графа лямбда-выражений, так как в ней описывается совместное использование общих подвыражений. Надеюсь, это поможет, но я боюсь, что это применимо только к ленивым языкам.