Я пытаюсь понять, как неразрушающая манипуляция большими коллекциями реализована в функциональном программировании, т.е. как можно изменять или удалять отдельные элементы без необходимости создания совершенно новой коллекции, где все элементы, даже немодифицированные, будут дублироваться в памяти. (Даже если исходная коллекция будет собрана в мусор, я ожидаю, что объем памяти и общая производительность такой коллекции будут ужасными.)
Вот как далеко я до сих пор:
Используя 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 #? Предполагая первое, заключается в том, насколько разумно эффективное редактирование коллекций может быть реализовано в функциональном программировании?
(Btw: Я знаю о Книга Криса Окасаки. Совершенно функциональные структуры данных, но еще не успели прочитать ее полностью. )
