Выполнение, связанное с «императивными» алгоритмами в haskell

Question

У меня есть обучение в семействе языков lisp, и теперь я немного разбираюсь в Haskell для моего же блага. В lisp, функциональный стиль в порядке, но есть несколько случаев , где императивный стиль необходим для достижения достойной производительности, например.

• Append

  Append медленно, поскольку он должен скопировать свой первый аргумент (иногда x100 так медленно, как версии, которые добились успеха, чтобы избавиться от него). Средство устранения - , чтобы переместить последний указатель первого списка в начало второго списка вместо добавления. Конечно, это разрушительная операция.

• рода

  Функциональные варианты сортировки создают множество промежуточных списков, , которые каким-то образом побеждает цель алгоритма, который должен быть как можно быстрее. AFAIR, в общем lisp, sort - единственная деструктивная функция, которая не имеет функциональной версии.

• длина

  Это дорогостоящая операция в лепет, так как один должен идти вниз весь список, чтобы получить его длину. Этого не должно быть, afaik clojure вычисляет длину списка в логарифмическом времени. Решение часто бывает , чтобы вычислить длину «на лету» в императивном цикле.

Вопрос в том, как мы справляемся с этими проблемами в haskell?

Answer 1

Как сказал Дельнан, эти проблемы связаны с использованием неправильной структуры данных, такой как связанный список, когда вы хотите вектор.

Ваши конкретные операции

• Append: минусы есть O (1), так что я подозреваю, что вы имеете в виду акт выделения ячейки минусы, сопоставления с образцом на клетку, и в конечном итоге ГХ клетка. Это довольно неизбежно, если вы не оптимизируете список, что происходит в определенных ситуациях.

• сортировка: Предлагаю вам посмотреть монаду ST, которая позволяет использовать алгоритмы, требующие мутации внутри чистого контекста. Для примера см. Реализацию vsort.

• длина: Конечно, единственный способ получить длину связанного списка - пересечь список. Если вам нужна длина часто, подумайте об использовании набора, карты или вектора - все из которых записывают общий размер, к которому можно получить доступ в O (1).

В общем

• Посмотрите в ST для изменчивости.
• Используйте правильную структуру данных для правильной проблемы.Узнайте, какие структуры может предложить Hackage (векторы, массивы, хэшмапы, хеш-таблицы, цветущие фильтры и т. Д.).

Answer 2

append не универсальная вещь. Добавление в очередь с двойным завершением отличается от добавления в список cons. Добавление деструктивно отличается от copy-on-append. В зависимости от ваших критериев вы можете оптимизировать для медлительности или безопасности потоков или простоты, и ваше определение «проблемы» изменится.

Как известно, Дельнан и Томас Дюбусон упоминают, что у Haskell есть все эти опции, если вы выбрали правильный тип данных.

Таким образом, если у вас есть определенный алгоритм, который вы хотите оптимизировать, вероятно, это будет либо метод, чтобы перевести его на быструю неразрушающую версию, а вариант для имитации разрушений, как правило, мультипликативный log(n) замедление или возможность запускать ссылочно прозрачные разрушения при замедлении аддитивной постоянной.

Для получения хороших примеров проблем с этим переводом рассмотрите алгоритмы поиска постоянных соединений или библиотеки функциональных графов.