对于习惯于命令式编程的人来说，有时很难在不使用数组/向量的情况下用函数式语言编写高效的代码。但是，似乎总有一种聪明的方法可以做到这一点。例如，在命令式和声明式编程语言中，排序都可以在 O(n*log(n)) 时间内完成，并且没有交换操作并不是一个真正的问题。
考虑一种没有数组或任何可以在恒定时间内访问任意元素的数据结构的函数式编程语言。以没有数组的 SML 或 Haskell 子集为例。
当然，每个可计算的问题都可以通过用这种语言编写的程序来解决。但我想知道在命令式世界之外是否存在本质上无法有效解决的问题。“高效”是指解决问题的最知名的命令式算法最多具有相同的时间复杂度。
例如，仅使用 SML 或 Haskell 中的列表可以有效地计算矩阵乘法吗？