Допустим, fn(x)
это чистая функция, которая делает что-то дорогое, например, возвращает список основных факторов x
.
И скажем, мы запоминаем версию той же самой функции memoizedFn(x)
. Он всегда возвращает один и тот же результат для заданного ввода, но поддерживает частный кэш предыдущих результатов для повышения производительности.
Формально говоря, memoizedFn(x)
считается чистым?
Или есть какое-то другое имя или квалифицирующий термин, используемый для обозначения такой функции в обсуждениях FP? (т.е. функция с побочными эффектами, которые могут повлиять на вычислительную сложность последующих вызовов, но могут не повлиять на возвращаемые значения.)
terminology
pure-function
Каллум
источник
источник
funcx(){sleep(cached_time--); return 0;}
каждый раз возвращает одно и то же значение val, но будет работать по-разномуОтветы:
Да. Запомненная версия чистой функции также является чистой функцией.
Все, что заботится о чистоте функции, - это влияние входных параметров на возвращаемое значение функции (передача одного и того же входа всегда должна давать один и тот же выход) и любые побочные эффекты, относящиеся к глобальным состояниям (например, текст к терминалу, пользовательскому интерфейсу или сети). , Время вычислений и использование дополнительной памяти не имеют значения для чистоты функций.
Кэши чистой функции практически невидимы для программы; функциональному языку программирования разрешается автоматически оптимизировать чистую функцию до запомненной версии функции, если он может определить, что это будет выгодно. На практике автоматическое определение того, когда памятка полезна, на самом деле является довольно сложной проблемой, но такая оптимизация будет действительной.
источник
Википедия определяет «Чистую функцию» как функцию, которая имеет следующие свойства:
Его возвращаемое значение одинаково для тех же аргументов (без изменений с локальными статическими переменными, нелокальными переменными, изменяемыми ссылочными аргументами или входными потоками от устройств ввода-вывода).
Его оценка не имеет побочных эффектов (нет мутации локальных статических переменных, нелокальных переменных, изменяемых ссылочных аргументов или потоков ввода-вывода).
По сути, чистая функция возвращает тот же вывод при том же входе и не влияет ни на что, кроме функции. В целях чистоты не имеет значения, как функция вычисляет свое возвращаемое значение, при условии, что она возвращает те же выходные данные при одинаковых входных данных.
Функционально чистые языки, такие как Haskell, обычно используют запоминание для ускорения функции путем кэширования ее ранее вычисленных результатов.
источник
static const
локальная переменная в C ++ (но не в C) или лениво оцененная структура данных в Haskell. Есть еще одно условие: инициализация должна быть поточно-ориентированной.Да, запоминаемые чистые функции обычно называются чистыми. Это особенно распространено в таких языках, как Haskell, в которых запоминаемые, лениво оцениваемые, неизменяемые результаты являются встроенной функцией.
Есть одно важное предостережение: функция запоминания должна быть поточно-ориентированной, иначе вы можете получить условие гонки, когда два потока пытаются ее вызвать.
Один пример компьютерного ученого, использующего термин «чисто функциональный» таким образом, - это сообщение в блоге Конала Эллиотта об автоматическом запоминании:
Есть много примеров в рецензируемой литературе, и были на протяжении десятилетий. Например, в этой статье 1995 года «Использование автоматической мемоизации в качестве инструмента разработки программного обеспечения в реальных системах искусственного интеллекта» используется очень похожий язык в разделе 5.2 для описания того, что мы сегодня называем чистой функцией:
Некоторые императивные языки имеют похожую идиому. Например,
static const
переменная в C ++ инициализируется только один раз, прежде чем ее значение используется, и никогда не изменяется.источник
Это зависит от того, как вы это делаете.
Обычно люди хотят запоминать, изменяя какой-то словарь кеша. У этого есть все проблемы, связанные с нечистой мутацией, такие как беспокойство о параллелизме, беспокойство о слишком большом кеше и т.д.
Тем не менее, вы можете помнить без нечистой мутации памяти. Один из примеров - в этом ответе , где я отслеживаю запомненные значения с помощью
lengths
аргумента.В ссылке, предоставленной Робертом Харви , ленивая оценка используется, чтобы избежать побочных эффектов.
Другая техника, которую иногда можно увидеть, - это явно пометить памятку как нечистый побочный эффект в контексте
IO
типа, например, с помощью функции памятки кошачьего эффекта .Этот последний пункт поднимает вопрос о том, что иногда целью является просто инкапсуляция мутации, а не ее устранение. Большинство функциональных программистов считают его «достаточно чистым», чтобы сделать примеси явными и инкапсулированными.
Если вы хотите, чтобы термин отличал его от действительно чистой функции, я думаю, что достаточно просто сказать «запоминается изменяемым словарем». Это позволяет людям знать, как использовать его безопасно.
источник
collatz(100)
иcollatz(200)
к сотрудничеству. И IIUIC, проблема с кешем, увеличивающимся слишком большим, остается (хотя у Haskell могут быть некоторые хорошие уловки для этого?).IO
чисто. Все нечистые методы наIO
Cats и названыunsafe
.Async.memoize
также чист, поэтому нам не нужно соглашаться на «достаточно чистое» :)Обычно функция, которая возвращает список, вообще не является чистой, потому что она требует выделения памяти и, таким образом, может дать сбой (например, с помощью исключения, которое не является чистым). Язык, который имеет типы значений и может представлять список как тип значений ограниченного размера, может не иметь этой проблемы. По этой причине ваш пример, вероятно, не чистый.
В общем, если запоминание может быть выполнено способом, не зависящим от сбоя (например, с помощью статически выделенного хранилища для запомненных результатов и внутренней синхронизации для контроля доступа к ним, если язык допускает потоки), разумно рассмотреть такую функцию чистый.
источник
Вы можете реализовать памятку без побочных эффектов, используя монаду состояния .
В вашем случае состоянием будет запомненное значение или ничего (например, Haskell
Maybe
или ScalaOption[A]
). Если запомненное значение присутствует, оно возвращается какA
, в противном случаеA
вычисляется и возвращается как в переходном состоянии, так и в результате.источник