Вы говорите «либо списки, либо неизменяемые массивы», но на самом деле это две совершенно разные вещи, и во многих случаях алгоритмы, естественным образом подходящие для списков, не будут быстрее (и, возможно, медленнее) при использовании с изменяемыми массивами.
Например, рассмотрим алгоритм, состоящий из трех частей: построение списка из некоторого ввода, преобразование списка путем объединения соседних элементов, а затем фильтрация списка по некоторому критерию. Наивный подход к полному созданию нового списка на каждом этапе действительно был бы неэффективным; изменяемый массив, обновляемый на каждом этапе, будет улучшением. Но еще лучше заметить, что одновременно требуется только ограниченное количество элементов и что линейная природа алгоритма соответствует линейной структуре списка, что означает, что все три шага могут быть объединены вместе, а промежуточные списки полностью исключены. Если исходный ввод, использованный для построения списка, и отфильтрованный результат значительно меньше, чем промежуточный список, вы сэкономите много накладных расходов, избегая дополнительного выделения, вместо заполнения изменяемого массива элементами, которые просто будут отфильтрованы. все равно позже.
Изменяемые массивы, скорее всего, будут полезны при выполнении множества частичных обновлений произвольного доступа к массиву без очевидной линейной структуры. При использовании неизменяемых массивов Haskell во многих случаях это можно выразить с помощью функции accum в Data.Array, которая, как я считаю, уже реализована с использованием ST.
Короче говоря, во многих простых случаях либо доступны лучшие оптимизации, либо они уже обработаны.
Редактировать: Я заметил, что этот ответ был отклонен без комментариев, и мне любопытно, почему. Обратная связь приветствуется, я хотел бы знать, сказал ли я что-то глупое.