Ami*_*ory 4 haskell const data-structures
数据结构具有变异和非变异操作.例如,字典插入可以更改其基础数据结构的状态,但查找通常不会.
一些数据结构改变了它们的内部结构 - 即使在逻辑上非变异操作 - 但是以不改变可观察状态的方式.例如,展开树在查找时将元素移向根,并且移动到前面的列表在查找时将元素移向头部.从逻辑上讲,这组键不会改变.
在C++中,这可以通过定义具有const方法但mutable数据成员的数据结构来传达.有没有办法在Haskell中这样做？我唯一能想到的是
setContains :: Set k -> k -> (Set k, Bool)
但这很难看,因为底层数据结构改变了界面.
如果不使用不安全的原语,就无法实现这种低级优化,因此允许从纯代码中突变数据结构.
首先,请注意,在GHC运行时,纯代码确实会修改数据结构 - 通过评估它们.例如
x = (3+2, 4+5)
main = print (fst x) >>> print (fst x)
在GHC中,第一个print调用将实际重写 x为(5, 4+5),用结果重写其第一个组件.这样,第二次print不必再次执行添加.当然,这种重写永远不会改变它的语义x,因此它是一种特殊的,"安全"的变异.
有时这还不足以实现一些低级优化,例如问题中描述的优化.然后,不安全的原语是唯一的选择.
我相信这种技术的典范就是Data.Array.Diff.这是一个不可变的数组数据结构,具有恒定的时间访问和更新(!).在引擎盖下,有一个可变数组,其中必须执行更新.由于这会严重破坏对不可变数组的旧引用,因此这些引用也指向在更新之前存储旧值的(可变的)"changelog".因此,我们得到了一种"修订控制"系统:最后一个版本很快,旧版本变得越来越慢.从外面看,只能观察到纯粹的行为; 在里面,发生了很多变异.
该实现使用MVars来阻止并发访问,以避免OP在上面的注释中描述的多线程问题.
让我再次强调,这种技巧在Haskell中肯定被认为是单一的.在日常编程中,这不是编写好的,可读的,可靠的Haskell代码的方法.