Попытка суммировать вещи, которые возникли в других ответах и в комментариях:
Существует только одно определение "идемпотента".Функция f
является идемпотентной тогда и только тогда, когда f(f(x))
равно f(x)
для всех x
в области f
.
Существует более одного определения "равно".Во многих контекстах у нас есть идея «эквивалентности», которая означает равенство, и определение «эквивалент» может быть различным в разных контекстах.
Существует более одного определения «функции»,В математике (с традиционной теоретико-множественной конструкцией) функция - это набор пар.«Домен» функции - это набор всех элементов, которые появляются в первой позиции пары.Ни один элемент домена не появляется в первой позиции более чем одной пары в функции.«Диапазон» функции - это набор всех элементов, которые появляются во второй позиции пары.Элементы ассортимента могут появляться более одного раза.Мы говорим, что функция «отображает» каждый элемент своей области на определенный элемент своего диапазона, и мы пишем f(x)
, чтобы обозначить «второй элемент пары в f
, который имеет x
в качестве первого элемента».
Итак, ясно, что для функции, которая должна быть идемпотентной, ее диапазон должен быть подмножеством ее области.В противном случае f(f(x))
не имеет смысла.
В вычислениях, и особенно в императивных языках, функция часто определяется как последовательность операторов / инструкций вместе с некоторыми именованными входами и выходами (в большинстве языков)только один выход).«Вызов» функции является обязательной операцией, которая означает выполнение инструкций.Но инструкции на императивном языке могут иметь побочные эффекты: они могут изменить что-то, кроме их результатов.Эта концепция отсутствует в математике, а также в чисто функциональном программировании.
Эти императивные «функции», которые я теперь буду называть «подпрограммами», могут быть согласованы с математическим определением функциидвумя способами:
игнорировать побочные эффекты и говорить, что подпрограмма - это функция, домен которой является набором всех возможных комбинаций значений аргумента, и которая сопоставляет их с выходными данными.рутины.Это находится на слабой теоретической основе, если функция не является «чистой», то есть, если ее вывод зависит от изменяемого состояния за пределами своих аргументов, или если он изменяет состояние за пределами своих выходов.Причина в том, что математическая функция по определению не отображает свои входные данные на разные выходные данные в разное время.Математическая функция также не «меняет» вещи, когда «вызывается», потому что математические функции не «вызываются» определенное количество раз.Они просто «есть».
включают побочные эффекты в математическую функцию, которая описывает эффект, который вызывает , который подпрограмма оказывает на полное состояние машины,включая выходные данные из рутины, но также включая все глобальное состояние и еще много чего.Это стандартная уловка в CS, и это означает, что для каждого оператора, инструкции, вызова подпрограммы или чего-либо еще существует соответствующая функция, которая отображает состояние машины перед вызовом и состояние машины впоследствии.
Теперь, если мы применим определение «идемпотент» в случае 1, мы оцениваем, является ли математическая функция, для которой определенная подпрограмма предназначена для реализации , идемпотентной.Если подпрограмма делает что-то кроме реализации математической функции, например, если у нее есть какие-либо побочные эффекты, тогда мы находимся на очень шатком основании и получим вводящие в заблуждение результаты.Например, функцию int f(int i) { puts("hello!"); return i; }
можно рассматривать как идемпотентную на том основании, что «это реализация функции идентичности!».И это правда, если вы игнорируете побочные эффекты, но это означает, что определение бесполезно для каких-либо практических целей, потому что после учета побочных эффектов выполнение выражения f(f(0))
отличается от выполнения выражения f(0)
.f(f(0))
не эквивалентно f(0)
, даже если их возвращаемые значения равны, и мы можем заменить одно только другим, если не заботимся о (той части) выходных данных программы.
Если мы применим определение «идемпотента» к функциям состояний машины в случае 2, мы оцениваем , является ли вызов функции (с конкретными аргументами) идемпотентной операцией над состоянием машины .Тогда моя функция f
выше, очевидно, равна , а не идемпотентно - состояние машины с «hello! \ N», записанной на его устройство вывода, не совпадает с состоянием машины с «hello!\ nhello! \ n "записано на его устройство вывода.Я думаю, также ясно, что в этом случае ваша функция F
является идемпотентной (хотя она не является «чистой», поскольку ее возвращаемое значение зависит от состояния, отличного от его формальных параметров, и, следовательно, это не просто реализацияматематическая функция), а ваша функция F2
не идемпотентна.Если бы test
были неизменными, то мы могли бы разумно начать описывать F
как чистый.F2
тогда будет недействительным.
Насколько я знаю, когда compscis говорит об идемпотентности в императивных языках, они обычно говорят о том, являются ли функции состояний машины, определенные в случае 2, идемпотентными или нет.,Но использование может варьироваться - если процедура чиста, то они могут говорить о том, является ли математическая функция, которую она представляет, идемпотентной.В чистом функциональном языке нет никакого состояния машины, о котором можно говорить, поэтому случай 2 был бы неуместным, и любое использование термина «идемпотент» по отношению к функции должно быть случаем 1. Функции в чисто функциональных языках всегда похожи на математические функции.