20

我试图弄清楚如何在函数式编程中实现对大型集合的非破坏性操作，即。如何在不必创建一个全新的集合的情况下更改或删除单个元素，其中所有元素，即使是未修改的元素，都将在内存中复制。（即使原始集合会被垃圾回收，我预计此类集合的内存占用和一般性能也会很糟糕。）

这是我到现在为止的距离：

使用 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中都被重用，即。内存中只有此值的 1 个副本：LM

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

我的问题：

函数式编程语言是否通常重用值而不是将它们克隆到新的内存位置，或者我只是对 F# 的行为感到幸运？假设前者，这是否可以在函数式编程中实现合理的内存高效编辑集合？

（顺便说一句：我知道Chris Okasaki 的书Purely functional data structures，但还没有时间彻底阅读它。）

4

5 回答 5

28

我试图弄清楚如何在函数式编程中实现对大型集合的非破坏性操作，即。如何在不必创建一个全新的集合的情况下更改或删除单个元素，其中所有元素，即使是未修改的元素，都将在内存中复制。

这个页面有一些 F# 中数据结构的描述和实现。它们中的大多数来自 Okasaki 的Purely Functional Data Structures，尽管 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)

请注意，我们重用了一些节点。假设我们从这棵树开始：

当我们将 ane插入树中时，我们会得到一棵全新的树，其中一些节点指向我们原来的树：

如果我们没有对xs上面树的引用，那么 .NET 将垃圾收集任何没有实时引用的节点，特别是d,g和f节点。

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

函数式编程语言是否通常重用值而不是将它们克隆到新的内存位置，或者我只是对 F# 的行为感到幸运？假设前者，这是否可以在函数式编程中实现合理的内存高效编辑集合？

是的。

然而，列表并不是一个很好的数据结构，因为对它们的大多数非平凡操作都需要 O(n) 时间。

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

于 2010-01-03T03:56:50.387 回答
12

如何在不必创建一个全新的集合的情况下更改或删除单个元素，其中所有元素，即使是未修改的元素，都将在内存中复制。

这是有效的，因为无论哪种集合，指向元素的指针都与元素本身分开存储。（例外：某些编译器会在某些时候进行优化，但他们知道自己在做什么。）例如，您可以有两个仅在第一个元素上不同并共享尾部的列表：

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

这两个列表有shared共同的部分，但它们的第一个元素不同。不太明显的是，每个列表也以一个独特的对开头，通常称为“cons cell”：

  • Listl以一对包含指向共享尾部的指针"one"和指向共享尾部的指针开始。

  • Listl'以一对包含指向共享尾部的指针"1a"和指向共享尾部的指针开始。

如果我们只声明l并想要更改或删除第一个要获取的元素l'，我们会这样做：

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

有恒定的成本：

  • l通过检查 cons 单元格将其分成头部和尾部。

  • 分配一个指向"1a"和尾部的新 cons 单元格。

新的 cons 单元格成为 list 的值l'。

如果您在大集合的中间进行点状更改，通常您将使用某种使用对数时间和空间的平衡树。不太频繁地，您可能会使用更复杂的数据结构：

  • Gerard Huet 的zipper几乎可以为任何树状数据结构定义，并且可以用于以恒定成本遍历和进行点状修改。拉链很容易理解。

  • Paterson 和 Hinze 的手指树提供了非常复杂的序列表示，其中包括其他技巧使您能够有效地更改中间的元素 - 但它们很难理解。

于 2010-01-03T05:24:54.370 回答
5

虽然您的代码中引用的对象是相同的，但我相信引用本身的存储空间和列表的结构由take. 结果，虽然引用的对象是相同的，并且尾部在两个列表之间共享，但初始部分的“单元格”是重复的。

我不是函数式编程方面的专家，但也许使用某种树，你可以实现只复制 log(n) 元素，因为你只需要重新创建从根到插入元素的路径。

于 2010-01-03T02:57:00.740 回答
4

在我看来，您的问题主要是关于不可变数据，而不是功能语言本身。数据在纯函数式代码中确实必然是不可变的（参见引用透明性），但我不知道有任何非玩具语言在任何地方强制执行绝对纯度（尽管 Haskell 最接近，如果你喜欢那种东西）。

粗略地说，引用透明性意味着变量/表达式与其持有/评估的值之间不存在实际差异。因为一块不可变的数据（根据定义）永远不会改变，它可以用它的值来简单地识别，并且应该与任何其他具有相同值的数据没有区别。

因此，通过选择在具有相同值的两条数据之间不区分语义，我们没有理由故意构造重复值。因此，在明显相等的情况下（例如，将某些内容添加到列表中，将其作为函数参数传递等），如您所说，可以保证不变性的语言通常会重用现有引用。

同样，不可变数据结构具有其结构（尽管不是其内容）的内在引用透明性。假设所有包含的值也是不可变的，这意味着结构的各个部分也可以安全地在新结构中重用。例如，一个 cons 列表的尾部通常可以重复使用；在您的代码中，我希望：

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

......也是真的。

但是，重用并不总是可行的。例如，您的函数删除的列表的初始部分skip不能真正重用。出于同样的原因，将某些内容附加到 cons 列表的末尾是一项昂贵的操作，因为它必须重建一个全新的列表，类似于连接以 null 结尾的字符串的问题。

在这种情况下，幼稚的方法很快就会进入您担心的糟糕性能领域。通常，有必要从根本上重新考虑基本算法和数据结构，以使它们成功地适应不可变数据。技术包括将结构分解为分层或分层的部分以隔离更改，反转结构的部分以将廉价更新暴露给经常修改的部分，甚至将原始结构与更新集合一起存储，并仅在运行中将更新与原始结构组合当数据被访问时。

由于您在这里使用 F#，因此我假设您至少对 C# 有点熟悉；不可估量的 Eric Lippert 有大量关于 C# 中不可变数据结构的帖子，这些帖子可能会远远超出我所能提供的范围。在几篇文章的过程中，他演示了（相当有效的）堆栈、二叉树和双端队列等的不可变实现。任何 .NET 程序员的愉快阅读！

于 2010-01-03T04:20:17.030 回答
0

您可能对函数式编程语言中表达式的简化策略感兴趣。关于这个主题的一本好书是函数式编程语言的实现，作者 Simon Peyton Jones，他是 Haskell 的创建者之一。尤其是看下Lambda 表达式的图形缩减一章，因为它描述了公共子表达式的共享。希望它有所帮助，但恐怕它只适用于惰性语言。

于 2010-01-03T04:08:44.417 回答