Использование ограничений времени использования пространства Haskell

Мне очень нравится Haskell, но утечки пространства немного беспокоят меня. Я обычно думаю, что система типа Haskell делает ее более безопасной, чем С++, однако с циклом в стиле C я могу быть уверен, что она завершится без исчерпания памяти, тогда как "складка" Haskell может закончиться без памяти, если вы не будете осторожны, соответствующие поля строги.

Мне было интересно, есть ли библиотека, использующая систему типа Haskell, чтобы обеспечить сбор и запуск различных конструкций, таким образом, чтобы не создавать грозди. Например, no_thunk_fold выкидывает ошибку компилятора, если вы используете его таким образом, чтобы можно было создать thunks. Я понимаю, что это может ограничивать то, что я могу сделать, но я бы хотел несколько функций, которые я мог бы использовать в качестве опции, которая сделала бы меня более уверенным, что я случайно не оставил какое-то важное нестрогое место где-то и что у меня кончится пространства.

Ответ 1

Похоже, вы беспокоитесь о некоторых слабых сторонах ленивой оценки. Вы хотите, чтобы ваша сгиб, цикл, рекурсия обрабатывались в постоянной памяти.

Итерационные библиотеки были созданы для решения этой проблемы, pipes, conduit, enumerator, iteratee, iterIO.

Самые популярные, а также последние pipes и conduit. Оба они выходят за рамки итерационной модели.

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

conduit не так теоретически, как хорошо известно, как трубы, но имеет большое преимущество в настоящее время иметь больше связанных библиотек, построенных на нем для синтаксического анализа и обработка HTTP-потоков, потоков XML и многое другое. Посмотрите раздел канала на hackage на странице пакетов. Это использовано yesod одна из больших и хорошо известных веб-фреймворков Haskell.

Мне понравилось писать мои потоковые приложения с библиотекой труб, в частности, возможность делать стеки прокси-трансформатора. Когда мне нужно было получить веб-страницу или проанализировать некоторый xml, я использовал библиотеки кабелепроводов.

Я также должен упомянуть io-streams, который только сделал свой первый официальный релиз, Целью этого является, в частности, IO, не удивительно, что это от его имени, и использование более простого типа машин, меньшее количество параметров типа, тогда pipes или conduit. Основная нижняя сторона заключается в том, что вы застряли в монаде IO, поэтому это не очень полезно для чистого кода.

{-# language NoMonoMorphismRestriction #-}                                       
import Control.Proxy

Начните с простого перевода.

map (+1) [1..10]

становится:

runProxy $ mapD (+1) <-< fromListS [1..10]

Итерации, подобные предложениям, немного более подробные для простых переводов, но предлагают большие выигрыши с более крупными примерами.

Пример библиотеки proxy, pipe, которая генерирует числа фибоначчи в константе sapce

fibsP = runIdentityK $ (\a -> do respond 1                                       
                                 respond 1                                       
                                 go 1 1)                                         
  where                                                                          
    go fm2 fm1 = do  -- fm2, fm1 represents fib(n-2) and fib(n-1)                                                            
        let fn = fm2 + fm1                                                       
        respond fn -- sends fn downstream                                                              
        go fm1 fn

Они могли бы транслироваться на stdout с помощью runProxy $fibsP > → printD - printD печатает только значения нисходящего потока, Proxies - это двунаправленное предложение пакета труб.

Вы должны проверить прокси-учебник и учебник по каналу, который я только что узнал, теперь находится в FP Complete School of Haskell.

Один способ найти среднее будет:

> ((_,l),s) <- (`runStateT` 0) $ (`runStateT` 0) $ runProxy $  foldlD' ( flip $ const (+1)) <-< raiseK (foldlD' (+)) <-< fromListS [1..10::Int]
> let m = (fromIntegral . getSum) s / (fromIntegral . getSum) l
5.5

Теперь легко добавить карту или фильтровать прокси.

> ((_,l),s) <- (`runStateT` 0) $ (`runStateT` 0) $ runProxy $  foldlD' ( flip $ const (+1)) <-< raiseK (foldlD' (+)) <-< filterD even <-< fromListS [1..10::Int]

edit: код переписан, чтобы воспользоваться государственной монадой.

обновление:

В еще одном способе многократного вычисления по большому потоку данных компаским способом запись прямой рекурсии демонстрируется в сообщении в блоге красивая складка. Складки превращаются в данные и объединены при использовании строгого аккумулятора. Я не использовал этот метод с какой-либо регулярностью, но, похоже, он изолирует, где требуется строгость, что упрощает его применение. Вы также должны посмотреть на ответ на другой вопрос, аналогичный вопросу, который реализует тот же метод с аппликативным и может быть легче читать в зависимости от ваших пристрастий.

Ответ 2

Система типа Haskell не может этого сделать. Мы можем доказать это с полностью полиморфным термином, чтобы есть произвольные количества барана.

takeArbitraryRAM :: Integer -> a -> a
takeArbitraryRAM i a = last $ go i a where
  go n x | n < 0 = [x]
  go n x | otherwise = x:go (n-1) x

Для выполнения необходимых действий требуются подструктурные типы. Линейная логика соответствует эффективно вычислимому фрагменту лямбда-исчисления (вам также нужно будет управлять рекурсией). Добавление аксиом структуры позволяет взять супер экспоненциальное время.

Haskell позволяет вам подделывать линейные типы для управления некоторыми ресурсами с помощью монодаров индекса. К сожалению, пространство и время выпекаются на языке, поэтому вы не можете сделать это для них. Вы можете сделать то, что предложено в комментарии, и использовать Haskell DSL для генерации кода с ограничениями производительности, но вычисления терминов в этой DSL могут занимать произвольные длинные и использовать произвольное пространство.

Не беспокойтесь о утечке пространства. Поймайте их. Профиль. Причина вашего кода, чтобы доказать границы сложности. Этот материал вам нужно делать независимо от того, какой язык вы используете.