首页 文章

非持久性数据结构能否以纯粹的功能方式使用?

提问于
浏览
5

这是关于函数式编程的一般性问题,但我也对它在特定语言中的答案感兴趣 .

我只有初学者对功能语言的了解,所以请耐心等待 .

我的理解是,函数式语言把重点放在不同于命令式语言的数据结构上,因为它们喜欢不变性:持久性数据结构 .

例如,它们都有一个不可变列表概念,您可以从现有列表 l 和两个新项 xy 形成新列表 x :: ly :: l ,而不需要复制 l 的所有元素 . 这可能是由新的列表对象实现的,内部指向旧的列表对象作为尾部 .

在命令式语言中,很少使用这样的数据结构,因为它们不像c样式数组那样提供良好的引用局部性 .

一般来说,找到支持功能风格的数据结构是它自己的努力,所以如果一个人不总是必须这样做会很棒 .

现在,我们可以了解如何在函数式编程中使用所有经典数据结构,如果有正确的语言支持的话 .

通常,命令式语言中的数据结构具有在其上定义的修改操作(伪代码):

data.modify(someArgument)

写这个的功能方式是

newData = modified(data, someArgument)

一般的问题是,这通常需要复制数据结构 - 除非语言知道 data 实际上不会被其他任何东西使用:然后,修改可以以变异原件的形式完成,没有人能分辨出来区别 .

有一大类的情况,语言可以推断"never used elsewhere"的属性:当 modified 的第一个参数是未绑定的值时,如下例所示:

newData = modified(modified(data, someArgument))

在这里, data 可以在其他地方使用,但 modified(data, someArgument) 显然不是 .

这就是C中被称为“rvalue”的东西,并且在C的最新版本中,具有讽刺意味的是其根本不起作用,人们可以在这样的rvalues上重载 .

例如,人们可以写:

Data modified(Data const& data) { // returns a modified copy }
Data modified(Data && data) { // returns the modified original }

这意味着在C中,实际上可以采用任何可变的高效数据结构并将其转换为具有不可变的api,可以以纯函数的方式使用,就像命令式版本一样有效 .

(有一点需要注意,在C中仍然有时需要强制转换rvalue . 当然,需要注意实现这样的数据结构,即使用rvalue重载时 . 虽然可能会改进 . )

现在我的问题:

实际的函数式语言是否有类似的机制?或者由于某些其他原因这不是必需的吗?

(我标记了一些我特别感兴趣的特定语言 . )

4 回答

  • 0

    我很确定像别名分析这样的功能(检查数据是否在别处使用)不是Scala编译器的一部分(也不是Haskell和Clojure等其他FP语言的一部分) . Scala中的集合API(例如)显式拆分为 immutablemutable 包 . immutable 数据结构使用结构共享的概念来否定复制数据的需要,从而减少使用不可变结构的开销(就时间数据量而言) .

    正如您已经指出的那样,cons :: 等方法创建了一个新的不可变结构,它在引擎盖下包含对任何现有不可变数据的引用(而不是复制它) .

    mutableimmutable 类型之间的转换(例如,在Scala中)会复制 mutable 数据(通常以惰性方式),而不是使用任何机制,例如检查 mutable 结构是否未在其他任何地方引用并允许它突变 .

    当我第一次从Java迁移到Scala时,我最初认为在处理不可变结构时必须创建的(通常)大量时态数据可能是一个性能约束,并且涉及一些聪明的技术来实际允许在可安全的地方进行突变 . 这样做但事实并非如此,因为这个想法是不可变数据永远不会指向更年轻的 Value 观 . 由于在创建旧值时不存在较年轻的值,因此在创建时不能指向它,并且由于值从未被修改,因此以后也不能指向它 . 结果是像Scala / Haskell这样的FP语言能够实现生成所有这些时间数据,因为垃圾收集器能够在非常短的时间内删除它 .

    简而言之,Scala / Haskell(我不确定F#)不允许对不可变结构进行变异,因为像当前JVM这样的运行时环境的状态具有非常有效的垃圾收集,因此可以非常快速地删除时态数据 . 当然,正如我相信你知道的那样,包含可变元素的不可变结构在Scala这样的FP语言中是完全可能的,但是虽然可变元素可以改变,但是不可变容器不能 . 元素既不能添加/删除 .

  • 6

    确实,持久数据结构比它们的可变对应物慢 . 对此没有争议 . 有时差异可以忽略不计(迭代链表而不是数组),有时它可能很大(反向迭代),但这不是重点 . 使用不可变数据的选择是(或应该)是有意识的数据:我们为了稳定而交易性能 .

    考虑这一点:对于大多数(并非所有)现代计划,本地表现不是一个问题 . 对于今天's programs, the real performance bottleneck is in parallelization - both on local machine with shared memory, as well as across different machines. With the amounts of data we'这些天的处理,挤压内存局部性和分支预测的每一个最后一位都不是正确的 - 突变 .

    现代计划的另一个重要问题是稳定性 . 程序可能会崩溃的日子已经一去不复返了,你刚刚重新启动它并继续工作 . 今天's programs need to work on headless servers, without human intervention at all, for months or years. Today'的程序可以比购买(或租用)另外十台服务器便宜得多,而不是雇用一个人来重新启动程序 .

    确实,人们可以使用变异来制作可并行化且稳定的程序 . 理论上这是可能的 . 这更难了 . 对于不可变数据,您必须首先瞄准您的脚 .

    然后,这里已经有了's some perspective: we' ve . 您多久在代码中使用 goto 指令?你有没有考虑过这是为什么?你可以用 goto 做各种各样的表演技巧,但我们选择不这样做 . 在编程历史的某些时刻,我们已经确定 goto 比它的 Value 更麻烦 . 原始指针也发生了同样的事情:许多语言现在被认为是一种使用它们的糟糕形式 . 今天,我们处于下一阶段的中间:首先我们放弃了 goto ,然后我们放弃了原始指针,现在我们正在慢慢放弃变异 .

    但是,如果你真的发现自己出于正当理由推动本地性能的发展,并且你已经确定不可变数据确实是瓶颈(记住:先测量,然后优化),那么大多数函数式语言(Haskell和Elm除外)尽管不情愿,但是会让你逃避变异 . 就像C#中的原始指针一样,你可以有变异,你只需要明确(并且小心)它 . 例如,在F#中,您可以拥有可变变量,原始数组,可变记录,类,接口等 . 这是可能的,只是不推荐 . 到目前为止,普遍的共识是它本地化(即不泄漏到外部),你真的知道你记录了什么,并将其测试为死亡 .

    一个常见的情况是"value construction",你的函数最终产生一个不可变的值,但在做这个时会做各种各样的混乱 . 一个例子是F#核心库如何实现 List.map :通常,因为列表是从前到后迭代的,但是从前到后构造,需要首先通过迭代构造转换后的列表,然后将其反转 . 所以F#编译器在这里作弊并在构造时改变列表以避免额外的反转 .

    关于"locality"关注的另一个说明 . 还记得我提到过你可以用 goto 做各种各样的表演技巧吗?嗯,那不再那么真实了 . 由于程序员在没有 goto 的情况下开始编写程序,二进制代码变得更加可预测,因为跳转现在由编译器生成,而不是由人类编码 . 这使得CPU可以预测它们,并根据这些预测优化处理 . 最终的结果是,现在你实际上可能通过不加选择地使用 goto 而不是使用像循环这样的公认的高级工具来获得更差的性能 . 在当天,CPU无法做到那么聪明,所以选择不使用 goto 纯粹是一种稳定性措施 . 但现在事实证明它实际上是有帮助的表现,谁会想到?

    我认为同样的事情也会因不变性而发生 . 我不确定它究竟会如何发生,但我执行所有这些可能的优化(尽管它们确实执行了一些),但它们会 . 我们才刚刚开始 . :-)

  • 3

    1)函数式编程语言支持持久性数据结构 . 当数据结构转换为另一个或者对产生新数据结构的数据结构进行任何操作时,通过链接重新使用数据结构的未改变部分,尤其是在列表的情况下 .

    在计算中,持久数据结构是一种数据结构,在修改时始终保留自身的先前版本 . 这样的数据结构实际上是不可变的,因为它们的操作不会(可见地)就地更新结构,而是总是产生新的更新结构 .

    2)在纯懒惰的函数式语言中,计算被推迟,并且只有当表达式的结果用于最终值/结果时才进行评估 . 这种机制有助于避免不必要的计算 .

  • 1

    Haskell中的 ST (状态线程)monad是一种确保按顺序调用某些操作的方法(不可能在该序列之外进行修改) . 在 ST 中,您可以在Haskell中使用命令式,可变的数据结构 . 请注意,Haskell被认为是为数不多的纯功能语言之一 .

相关问题