命令型プログラミングに慣れている人にとって、配列/ベクトルを使用せずに関数型言語で効率的なコードを書くのは難しい場合があります。ただし、常にスマートな方法があるようです。たとえば、並べ替えは命令型プログラミング言語でも宣言型プログラミング言語でも O(n*log(n)) 時間で実行でき、スワップ操作がないことは実際の問題ではありません。
一定時間内に任意の要素にアクセスできる配列やデータ構造を持たない関数型プログラミング言語を考えてみましょう。たとえば、配列のない SML または Haskell のサブセットを取り上げます。
もちろん、計算可能な問題はすべて、そのような言語で書かれたプログラムで解決できます。しかし、命令の世界の外では本質的に効率的に解決できない問題があるかどうか疑問に思っています。「効率的に」とは、問題を解決するために、最もよく知られている命令型アルゴリズムの複雑さを最大限に高めることを意味します。
たとえば、SML または Haskell のリストのみを使用して、行列の乗算を効率的に計算できますか?