Тот факт, что это может работать для простых случаев, не должен вызывать большого удивления: мы уже комфортно используем бесконечные структуры данных в Haskell благодаря лени и сборке мусора. Пока ваш конечный результат не зависит от одновременного наличия всех ваших значений, они могут быть собраны по мере продвижения или не принудительно в первую очередь.
Вот почему этот классический пример Фибоначчи работает в постоянном пространстве: предыдущие записи в списке не нужны после вычисления следующих двух, поэтому они собираются по мере продвижения — до тех пор, пока у вас нет других указателей на список.
fib n = fibs !! n
where fibs = 0 : 1 : zipWith (+) fibs (drop 1 fibs)
Попробуйте запустить эту функцию для разных входных данных и посмотрите на использование памяти. (Запустите его с помощью +RTS -s.)
(Если вам нужно более подробное объяснение с диаграммами, взгляните на этот пост, который я написал.)
Дело в том, что даже если программисту доступен неограниченный объем информации, мы все равно можем собрать большую ее часть, если от нее больше ничего не зависит.
Точно такая же логика может быть использована для эффективной реализации программ FRP.
Конечно, все не так просто. В примере fibs использование памяти увеличилось бы, если бы у нас был активный указатель на начало списка fibs. То же самое происходит с FRP, если ваши вычисления зависят от слишком большого количества прошлых данных: это называется утечкой времени.
Работа с утечками времени — одна из открытых проблем при внедрении эффективной и надежной структуры FRP. Трудно предоставить выразительные абстракции FRP, не допуская возможности плохого или даже катастрофического использования памяти. Я считаю, что большинство современных подходов в конечном итоге предоставляют абстрактные типы FRP вместе с благословенным набором операций, которые с меньшей вероятностью вызовут такого рода утечки; особенно экстремальной формой этого является Arrowized FRP, который вообще не предоставляет тип поведения/сигнала, а скорее выражает все с помощью преобразований между сигналами (в виде стрелок).
Я никогда не пытался реализовать хорошую систему FRP самостоятельно, поэтому я не могу более подробно объяснить проблемы. Если вас интересуют более подробные сведения по этой теме, отличным местом для поиска является блог Конала Эллиотта с этот пост в качестве хорошей отправной точки. Вы также можете ознакомиться с некоторыми из написанных им статей, например "Push-Pull Functional Reactive Programming", а также другие статьи по этой теме, в том числе некоторые о Arrowized FRP, такие как "Функциональное реактивное программирование, продолжение" (выбрано почти случайно).
сноски
¹ Это не на самом деле постоянное пространство, потому что промежуточные результаты сами увеличиваются. Но он должен поддерживать постоянное количество ячеек списка в памяти.
person
Tikhon Jelvis
schedule
30.12.2014
