haskell - 相同数据的多个查找结构 : Memory duplication?

Question

假设我有一群人的数据，我希望能够以不同的方式查找他们。也许有某种数据结构(如二叉树)可以方便按名称查找。也许还有另一个(如列表)按创建顺序排列。也许还有更多。

在许多语言中，你会让每个人在堆上只分配一次。每个数据结构都包含指向该内存的指针。因此，每次添加新的查找方式时，您不会分配一组新的人员。

在 Haskell 中怎么样？当不同的数据结构需要索引相同的数据时，有什么方法可以避免内存重复？

Answer 1

我确信这个问题有一个更深入、更有见地的答案，但就目前而言......

由于在纯函数式编程语言中数据是不可变的，因此除了复制指针而不是复制其目标之外，无需执行任何其他操作。

作为一个快速且非常脏的例子，我启动了 ghci 解释器:

Prelude> let x = replicate 10000 'm' in all (==x) $ replicate 10000 x
True
(1.61 secs, 0 bytes)

我承认这些统计数据不可靠，但它没有做的是为 10000 个字符长的列表的所有 10000 个副本分配内存。

概括:

避免内存重复的方法是
(a) 使用 Haskell
(b) 避免无意义地重建您的数据。

我怎样才能毫无意义地重建我的数据？

一个非常简单且毫无意义的例子:

 pointlessly_reconstruct_list :: [a] -> [a]
 pointlessly_reconstruct_list [] = []
 pointlessly_reconstruct_list (x:xs) = x:xs

这种事情会导致列表结构的重复。

你有没有一些不那么毫无意义但仍然很简单的例子？

有趣的是，如果你这样做 xs ++ ys你基本上是重建 xs为了放置 ys在它的末尾(替换 [] )，所以 xs 的列表结构几乎是抄袭批发。但是，不需要复制实际数据，当然只需要一份 ys 的副本。 .