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

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

Используя 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)

Затем я проверил, "объекты" из исходного списка "переработаны" в новых списках с помощью .NETObject.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 #? Предполагая, что первое, это то, как разумно-эффективное редактирование коллекций может быть реализовано в функциональном программировании?

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