相同数据的多个查找结构:内存重复？

Question

假设我有很多人的数据,我希望能够以不同的方式查找它们.也许有某种数据结构(如二叉树)有助于按名称查找.也许还有另一个(如列表)按创作顺序排列.也许还有更多.

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

在哈斯克尔怎么样？当不同的数据结构需要索引相同的数据时,有没有办法避免内存重复？

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.