假设我有一群人的数据,我希望能够以不同的方式查找他们。也许有某种数据结构(如二叉树)有助于按名称查找。也许还有另一个(如列表)是按创建顺序排列的。也许还有更多。
在许多语言中,您会让每个人在堆上只分配一次。每个数据结构都包含指向该内存的指针。因此,每次添加新的查找方式时,您都不会分配一组新的人员。
在 Haskell 怎么样?当不同的数据结构需要索引相同的数据时,有什么办法可以避免内存重复?
假设我有一群人的数据,我希望能够以不同的方式查找他们。也许有某种数据结构(如二叉树)有助于按名称查找。也许还有另一个(如列表)是按创建顺序排列的。也许还有更多。
在许多语言中,您会让每个人在堆上只分配一次。每个数据结构都包含指向该内存的指针。因此,每次添加新的查找方式时,您都不会分配一组新的人员。
在 Haskell 怎么样?当不同的数据结构需要索引相同的数据时,有什么办法可以避免内存重复?
我确信这个问题有一个更深入、更有知识的答案,但目前......
由于在纯函数式编程语言中数据是不可变的,因此除了复制指针而不是复制其目标之外,不需要做任何事情。
作为一个快速且非常肮脏的示例,我启动了 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
.