Как часто seq используется в производственном коде Haskell?

23

У меня есть некоторый опыт написания небольших инструментов на Haskell, и я нахожу его очень интуитивно понятным, особенно для написания фильтров (использующих interact), которые обрабатывают их стандартный ввод и передают его на стандартный вывод.

Недавно я попытался использовать один такой фильтр для файла, который был примерно в 10 раз больше обычного, и я получил Stack space overflowошибку.

После некоторого чтения (например, здесь и здесь ) я определил два руководства по экономии места в стеке (опытные Хаскелеры, пожалуйста, исправьте меня, если я напишу что-то не то):

  1. Избегайте рекурсивных вызовов функций, которые не являются хвостово-рекурсивными (это справедливо для всех функциональных языков, которые поддерживают оптимизацию хвостовых вызовов).
  2. Введение seqдля принудительной ранней оценки подвыражений, чтобы выражения не становились слишком большими, прежде чем их уменьшать (это характерно для Haskell или, по крайней мере, для языков, использующих ленивую оценку).

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

Так как я не опытный программист на Haskell, я хотел спросить, является ли введение seqтаким способом обычной практикой, и как часто это можно увидеть seqв рабочем коде Haskell. Или есть какие-то методы, которые позволяют избегать seqслишком частого использования и при этом все еще использовать мало стекового пространства?

Джорджио
источник
1
Оптимизация, подобная той, которую вы описали, почти всегда сделает код немного менее элегантным.
Роберт Харви
@ Роберт Харви: Существуют ли альтернативные методы, позволяющие снизить использование стека? Я имею в виду, что мне нужно переписать свои функции по-разному, но я понятия не имею, существуют ли устоявшиеся методы. Моей первой попыткой было использование хвостовых рекурсивных функций, которые помогли, но не позволили мне полностью решить мою проблему.
Джорджио

Ответы:

17

К сожалению, есть случаи, когда приходится использовать seqэффективную / хорошо работающую программу для больших данных. Поэтому во многих случаях вы не можете обойтись без этого в производственном коде. Вы можете найти больше информации в Real World Haskell, Глава 25. Профилирование и оптимизация .

Тем не менее, есть возможности, как избежать использования seqнапрямую. Это может сделать код чище и надежнее. Некоторые идеи:

  1. Используйте вместо этого канал , трубы или итерацииinteract . Известно, что у Lazy IO есть проблемы с управлением ресурсами (не только памятью), и итераторы созданы именно для того, чтобы преодолеть это. (Я бы посоветовал избегать ленивого ввода-вывода вообще, независимо от того, насколько велики ваши данные - см . Проблему с ленивым вводом-выводом .)
  2. Вместо seqнепосредственного использования (или разработки собственных) комбинаторов, таких как foldl ' или foldr' или строгих версий библиотек (таких как Data.Map.Strict или Control.Monad.State.Strict ), которые предназначены для строгих вычислений.
  3. Используйте расширение BangPatterns . Это позволяет заменить seqна строгое сопоставление с образцом. Объявление строгих полей конструктора также может быть полезно в некоторых случаях.
  4. Также возможно использовать Стратегии для форсирования оценки. Библиотека стратегий в основном предназначена для параллельных вычислений, но также имеет методы для принудительного преобразования значения в WHNF ( rseq) или full NF ( rdeepseq). Существует множество полезных методов для работы с коллекциями, комбинирования стратегий и т. Д.
Петр Пудлак
источник
+1: спасибо за полезные советы и ссылки. Пункт 3 кажется довольно интересным (и самое простое решение для меня, чтобы использовать прямо сейчас). Что касается предложения 1, я не понимаю, как избегание ленивого ввода-вывода может улучшить ситуацию: насколько я понимаю, ленивый ввод-вывод должен быть лучше для фильтра, который должен обрабатывать (возможно, очень длинный) поток данных.
Джорджио
2
@Giorgio Я добавил ссылку на Haskell Wiki о проблемах с Lazy IO. С ленивым вводом-выводом вам может быть очень трудно управлять ресурсами. Например, если вы не полностью прочитали ввод (например, из-за ленивой оценки), дескриптор файла остается открытым . И если вы идете и закрываете дескриптор файла вручную, часто бывает, что из-за ленивого чтения оценки он откладывается, и вы закрываете дескриптор перед чтением всего ввода. И часто бывает довольно сложно избежать проблем с памятью при ленивом вводе-выводе.
Петр Пудлак
У меня недавно была эта проблема, и в моей программе заканчивались файловые дескрипторы. Поэтому я заменил ленивый ввод-вывод на строгий ввод-вывод, используя строгий ByteString.
Джорджио