Gab*_*iel 9 theory arrays complexity-theory haskell functional-programming
对于习惯于编程的人来说,有时很难在不使用数组/向量的情况下在函数式语言中编写高效的代码.然而,似乎总有一种聪明的方法.例如,排序可以在命令式和声明式编程语言中的O(n*log(n))时间内完成,并且交换操作的缺乏不是真正的问题.
考虑一种函数式编程语言,它没有数组或任何可以在恒定时间内访问任意元素的数据结构.例如,在没有数组的情况下获取SML或Haskell的子集.
当然,每个可计算的问题都可以通过用这种语言编写的程序来解决.但我想知道是否存在任何本质上无法在命令式世界之外有效解决的问题.通过"有效",我的意思是最多同时解决问题的最着名的命令式算法的复杂性.
例如,只使用SML或Haskell中的列表可以有效地计算矩阵乘法吗？