data-structures - 如何在函数式编程中实现内存有效的集合的无损操作？

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＃的行为？假设是前者，这是否可以在函数式编程中合理地实现内存有效的集合编辑？

(顺便说一句:我知道 Chris Okasaki's book Purely functional data structures，但是还没有时间彻底阅读它。)

Answer 1

I'm trying to figure out how non-destructive manipulation of large collections is implemented in functional programming, ie. how it is possible to alter or remove single elements without having to create a completely new collection where all elements, even the unmodified ones, will be duplicated in memory.

This page对F＃中的数据结构进行了一些描述和实现。尽管AVL树是我自己的实现，因为其中没有出现在本书中，但它们大多来自Okasaki的Purely Functional Data Structures。

现在，正如您所询问的，关于重用未修改的节点，让我们看一个简单的二叉树:

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节点。

请注意，我们仅沿插入节点的路径修改了节点。这在包括列表在内的大多数不可变数据结构中非常典型。因此，我们创建的节点数完全等于为了插入数据结构而需要遍历的节点数。

Do functional programming languages generally re-use values instead of cloning them to a new memory location, or was I just lucky with F#'s behaviour? Assuming the former, is this how reasonably memory-efficient editing of collections can be implemented in functional programming?

是。

但是，列表并不是很好的数据结构，因为列表上的大多数非平凡操作都需要O(n)时间。

平衡的二叉树支持O(log n)插入，这意味着我们在每个插入上创建O(log n)副本。由于log2(10 ^ 15)为〜= 50，因此对于这些特定的数据结构，开销非常小。即使您在插入/删除后保留每个对象的每个副本，您的内存使用量也会以O(n log n)的速率增加-我认为这非常合理。