Суперпозиции
Множество всех возможных не эквивалентных друг другу суперпозиций данного множества функций образует замыкание данного множества функций.
Способы получения суперпозиций
Рассмотрим две булевы функции: функцию [math]f[/math] от [math]n[/math] аргументов [math]f(x_, x_, \ldots, x_)[/math] и функцию [math]g[/math] от [math]m[/math] аргументов [math]g(y_, y_, \ldots, y_)[/math] .
Тогда мы можем получить новую функцию из имеющихся двумя способами:
- Подстановкой одной функции в качестве некоторого аргумента для другой;
- Отождествлением аргументов функций.
Подстановка одной функции в другую
| Определение: |
| Подстановкой (англ. substitution) функции [math]g[/math] в функцию [math]f[/math] называется замена [math]i[/math] -того аргумента функции [math]f[/math] значением функции [math]g[/math] : [math]h(x_, \ldots, x_) = f(x_, \ldots, x_, g(x_, \ldots, x_), x_, \ldots, x_)[/math] |
Допускается также не только подстановка одной функции в другую, но и подстановка функции в саму себя.
При подстановке функции [math]g[/math] вместо [math]i[/math] -того аргумента функции [math]f[/math] , результирующая функция [math]h[/math] будет принимать аргументы, которые можно разделить на следующие блоки:
| 1. [math] x_, \ldots, x_[/math] | — аргументы функции [math]f[/math] до подставленного значения функции [math]g[/math] |
| 2. [math] x_, \ldots, x_ [/math] | — используются как аргументы для вычисления значения функции [math]g(y_, \ldots, y_)[/math] |
| 3. [math] x_, \ldots, x_ [/math] | — аргументы функции [math]f[/math] после подставленного значения функции [math]g[/math] |
- [math] f(a,b) = a \vee b [/math]
- [math] g(a) = \neg a [/math]
[math] h(a,b) = f(a,g(b)) = a \vee \neg b [/math] — подстановка функции [math]g[/math] вместо второго аргумента функции [math]f[/math] . В данном примере при помощи подстановки мы получили функцию [math]h(a,b)=a \leftarrow b[/math] .
Отождествление переменных
| Определение: |
| Отождествлением переменных (англ. identification of variables) называется подстановка [math]i[/math] -того аргумента функции [math]f[/math] вместо [math]j[/math] -того аргумента: [math]h(x_, \ldots, x_, x_, \ldots, x_) = f(x_, \ldots, x_, \ldots, x_, x_, x_, \ldots, x_)[/math] |
Таким образом, при отождествлении [math]c[/math] переменных мы получаем функцию [math]h[/math] с количеством аргументов [math]n-c+1[/math] .
[math] f(a,b) = a \vee b [/math] — исходная функция
[math] h(a) = a \vee a [/math] — функция с отождествленными первым и вторым аргументами
Очевидно, в данном примере мы получили функцию [math]P_[/math] — проектор единственного аргумента.
Ранги суперпозиций
| Определение: |
| Ранг суперпозиции (англ. rank of function composition) — это минимальное число подстановок и отождествлений, за которое суперпозиция может быть получена из исходного множества функций. Суперпозиция [math]K[/math] ранга [math]n[/math] обозначается как [math]K^[/math] |
См. также
- Булевы функции
- Представление функции формулой, полные системы функций
Источники информации
- Осипова В.А., Основы дискретной математики: Учебное пособие, М.: ФОРУМ: ИНФРА-М, 2006, стр 62-63
- Композиция функций в математике
- Е.Л. Рабкин, Ю.Б. Фарфоровская, Дискретная математика, Глава 7: Суперпозиция функций. Замыкание набора функций. Замкнутые классы функций. Полные наборы. Базисы
5. Суперпозиция функций
При функциональном программировании часто используется суперпозиция функций. Для ее реализации используются следующие функции:
- Nest [expr, x, n] — n раз применяет выражение (функцию) ехрг к заданному аргументу х,
- NestList [f, x, n] — возвращает список результатов (п+1)-кратного применения функции f к заданному аргументу х;
- Fold[f, x, list] — дает последний элемент в FoldList [f, x, list];
- FoldList [f, x, ] — возвращает список ;
- ComposeList [ < f , f . >, x] — генерирует список в форме .
Примеры, иллюстрирующие действие этих функций, представлены ниже:
Функции Fixed Point и Catch
В функциональном программировании вместо циклов, описываемых далее, может использоваться следующая функция:
- FixedPoint [ f, expr ] — вычисляет expr и применяет к нему f, пока результат не перестанет изменяться;
- FixedPoint [ f, expr, SameTest->comp] — вычисляет expr и применяет к нему f, пока два последовательных результата не дадут True в тесте SameTest.
Пример применения функции FixedPoint:
Последний результат (ноль) выводится в отдельной (нумерованной) ячейке вывода и означает завершение процесса итераций — деления t на 2.
Следующий пример показывает, как можно создать цепную дробь с помощью функции Nest:
Еще одна функция такого рода — это Catch:
- Catch [expr] — вычисляет expr, пока не встретится Throw [value], затем возвращает value;
- Catch [expr, form] — вычисляет expr, пока не встретится Throw [value, tag], затем возвращает value;
- Catch [expr, form, f] — возвращает f [value, tag] вместо value. Ниже представлены некоторые конструкции циклов с оператором Catch:
Реализация рекурсивных и рекуррентных алгоритмов
Рассмотрим несколько простых примеров, выявляющих суть функционального программирования. Вначале это будет пример, в котором задана функция sen [х, n], вычисляющая сумму синуса в степени n и косинуса в степени n:
В этом простейшем примере результат вычислений есть возвращаемое функцией sen значение — численное или символьное. В свою очередь, функция sen в своем теле имеет встроенные функции синуса и косинуса.
Важное место в решении многих математических задач занимают реализации рекурсивных и рекуррентных алгоритмов. Напомним, что рекурсия означает обращение функции к самой себе внутри ее тела, а рекуррентность — получение результата на данном шаге по результатам вычислений на предшествующих шагах.
Рассмотрим, как это делается, с помощью описанных выше функций. Классический пример реализации рекурсивного алгоритма — вычисление факториала путем задания функции, в теле которой есть обращение к ней же самой:
Полезно, однако, обратить внимание на возможность явного задания результата для конкретных значений аргумента: f [ 0 ] =1 и f [ 1 ] =1. Так что рекурсия реализуется, начиная с n=2 и выше, в соответствии с классическим определением факториала.
Для реализации рекуррентных алгоритмов в Mathematica имеется ряд функций, таких как Nest или FixedPoint. В следующих примерах показано вычисление
квадратного корня из числа 5 по известному алгоритму Ньютона, записанному в виде функции newtonS:
newtonS [x_] := N[ 1/2 ( х + 5/х )]
Nest[newton5, 1.0, 5]
2.23607
NestList [newtonS, 1.0, 5]
FixedPoint [newtonS, 1.0]
2.23607
FixedPointList [newtonS, 1.0]
FixedPointList [newtonS, 1.0, SameTest -> (Abs[#l- #2] < 10.A-4 &)]
Обратите внимание на то, что функции Nest и FixedPoint дают единственный конечный результат, тогда как функции NestList и FixedPointList возвращают еще и все промежуточные результаты итераций. Последний пример иллюстрирует остановку вычислений по заданной погрешности, равной 10 -4 .
Далее зададим функцию, реализующую алгоритм Ньютона для нахождения корня произвольного выражения f(x) при начальном значении х 0 = а, по следующим формулам:
Эту функцию можно записать следующим образом:
Тогда вычисления корня из выражения е^x — 2 с начальным приближением х 0 = 0.5 при числе итераций n можно организовать с помощью функций Nest и NestList:
newtoniter [Function [ , Ехр[х] — 2.0], 0.5, 5]
0.693147
newtoniter [Function [ , Ехр[х] — 2.0], 0.5, #] & /@ Range [5]
newtoniterl[f_,x0_,n_] := NestList[ (#-f [#] /f ‘ [#] ) &,N[x0] , n]
newtoniterl [Function [ , Exp[x] — 2.0], 0.5, 5]
В первом случае возвращается только окончательный результат, а в других — еще и все промежуточные. Функция FixedPoint позволяет осуществлять итерации
до тех пор, пока результат не перестанет изменяться (с машинной точностью). Это иллюстрирует следующий пример:
newtonfp[f_, х0_] := FixedPoint[ (# — f [#]/f'[#]) &, N[xO]]
newtonfp[Function[ , Exp[x] — 2.0], 0.5]
0.693147
Более сложные примеры функционального программирования мы рассмотрим позже, при описании создания пакетов расширения систем Mathematica.
Суперпозиция функций
Суперпозицией функций f1, …, fm называется функция f, полученная с помощью подстановок этих функций друг в друга и переименования переменных.
Пусть имеются два отображения и , причем непустое множество. Тогда супер позицией или композицией функций и называется функция , определенная равенством для всякого .
Областью определения суперпозиции является множество .
Функция называется внешней, а -внутренней функцией для суперпозиции .
Функции, представленные в виде композиции «более простых», называются сложными функциями.
Примерами использования суперпозиции являются: решение системы уравнений методом подстановки; нахождение производной от функции; нахождение значения алгебраического выражения с помощью подстановки в него значения заданных переменных.
Рекурсивные функции
Рекурсией называется такой способ задания функции, при котором значения определяемой функции для произвольных значений аргументов выражаются известным образом через значения определяемой функции для меньших значений аргументов.
Примитивно рекурсивная функция
Определение понятия примитивно рекурсивной функции является индуктивным. Оно состоит из указания класса базовых примитивно рекурсивных функций и двух операторов (суперпозиции и примитивной рекурсии), позволяющих строить новые примитивно рекурсивные функции на основе уже имеющихся.
К числу базовых примитивно рекурсивных функций относятся функции следующих трёх видов:
Нулевая функция— функция без аргументов, всегда возвращающая0.
Функция следованияодного переменного, сопоставляющая любому натуральному числунепосредственно следующее за ним натуральное число .
Функции , где , от n переменных, сопоставляющие любому упорядоченному набору натуральных чисел число из этого набора.
Операторы подстановки и примитивной рекурсии определяются следующим образом:
Оператор суперпозиции (иногда—оператор подстановки). Пусть — функция от m переменных, а — упорядоченный набор функций отпеременных каждая. Тогда результатом суперпозиции функцийв функцию называется функцияотпеременных, сопоставляющая любому упорядоченному набору натуральных чисел число .
Оператор примитивной рекурсии. Пусть — функция от n переменных, а — функция от переменных. Тогда результатом применения оператора примитивной рекурсии к паре функций и называется функция от переменной вида ;
В данном определении переменнуюможно понимать как счётчик итераций, — как исходную функцию в начале итерационного процесса, выдающего некую последовательность функцийпеременных, начинающуюся с , и — как оператор, принимающий на входпеременных , номер шага итерации , функцию на данном шаге итерации, и возвращающий функцию на следующем шаге итерации.
Множество примитивно рекурсивных функций — это минимальное множество, содержащее все базовые функции и замкнутое относительно указанных операторов подстановки и примитивной рекурсии.
В терминах императивного программирования — примитивно рекурсивные функции соответствуют программным блокам, в которых используется только арифметические операции, а также условный оператор и оператор арифметического цикла (оператор цикла, в котором число итераций известно на момент начала цикла). Если же программист начинает использовать оператор цикла while, в котором число итераций заранее неизвестно и, в принципе, может быть бесконечным, то он переходит в класс частично рекурсивных функций.
Укажем на ряд широко известных арифметических функций, являющихся примитивно рекурсивными.
Функция сложения двух натуральных чисел () может быть рассмотрена в качестве примитивно рекурсивной функции двух переменных, получаемой в результате применения оператора примитивной рекурсии к функциям и , вторая из которых получается подстановкой основной функции в основную функцию :
Умножение двух натуральных чисел может быть рассмотрено в качестве примитивно рекурсивной функции двух переменных, получаемой в результате применения оператора примитивной рекурсии к функциям и , вторая из которых получается подстановкой основных функций и в функцию сложения:
Симметрическая разность(абсолютная величина разности) двух натуральных чисел () может быть рассмотрена в качестве примитивно рекурсивной функции двух переменных, получаемой в результате применения следующих подстановок и примитивных рекурсий:
3 Композиция и суперпозиция функций в функциональном программировани кратко
Привет, Вы узнаете о том , что такое 3 Композиция и суперпозиция функций в функциональном программировани, Разберем основные из виды и особенности использования. Еще будет много подробных примеров и описаний. Для того чтобы лучше понимать что такое 3 Композиция и суперпозиция функций в функциональном программировани , настоятельно рекомендую прочитать все из категории Функциональное программирование.
Композиция и суперпозиция функций
Как все нормальные программисты, мы — ленивые. Мы не хотим постоянно собирать, тестировать и деплоить один и тот же код, который переписываем снова, и снова, и снова. Мы всегда пытаемся найти пути, чтобы, решив какую-нибудь задачу однажды, использовать это решение в других случаях. Повторное использование кода — хорошая затея, но в реальности этого тяжело добиться. Попробуйте сделать код слишком специализированным и у вас не получится использовать его снова. Попробуйте сделать его слишком общим и вам будет сложно использовать его даже в вашей первоочередной задаче. То, что нам нужно — баланс между этими двумя положениями, споcоб создавать элементы поменьше с возможностью их многократного использования, которые мы будем применять как строительные блоки для конструирования более сложного функционала. В функциональном программировании функции — наши строительные блоки. Мы пишем их для решения определенных задач, а потом складываем вместе, как блоки в Lego™. Результат такого сложения называется композицией функций. Так как же это работает? Давайте начнем с двух JavaScript-функций:
var add10 = function(value) < return value + 10; >; var mult5 = function(value) < return value * 5; >;
Код получился слишком пространный, так что давайте перепишем его, используя стрелочные функции:
var add10 = value => value + 10; var mult5 = value => value * 5;
Так-то лучше. Теперь давайте представим, что нам нужна функция, принимающая значение и добавляющая к нему 10, после чего умножающая результат на 5. Мы могли бы написать:
var mult5AfterAdd10 = value => 5 * (value + 10)
Даже несмотря на такой простой пример, нам бы не хотелось писать целую функцию с нуля. Во-первых, мы могли бы допустить ошибку и, например, забыть поставить круглые скобки. Во-вторых, у нас есть одна функция, прибавляющая к значению 10, и другая, умножающая его на 5. Получается, мы пишем код, который уже написали. Так что вместо этого давайте используем add10 и mult5 и соберем новую функцию:
var mult5AfterAdd10 = value => mult5(add10(value));
Мы просто использовали существующие функции, чтобы получить mult5AfterAdd10, но есть и способ получше. В математике f ∘ g — композиция функций (прим. Об этом говорит сайт https://intellect.icu . пер., или суперпозиция функций) и читается она как «применение функции f к результату функции g» или более просто «выполнение f после g». Получается, что (f ∘ g)(x) — эквивалент вызова функции f после функции g со значением x или еще проще: f(g(x)). В нашем примере у нас mult5 ∘ add10 или «mult5 после add10», отсюда и название нашей функции mult5AfterAdd10. И это объясняет то, что мы сделали. Мы вызвали mult5 после вызова add10 с value или просто: mult5(add10(value)). Поскольку JavaScript нативно не реализует возможность композиции функций, давайте взглянем на Elm:
add10 value = value + 10mult5 value = value * 5mult5AfterAdd10 value = (mult5В Elm функции компонуются с помощью инфиксального оператора
f x = (gВ этом случае x передается в t, чей результат передается в r, чей результат, в свою очередь, — в s и так далее. Если вы захотите сделать что-то подобное в JavaScript, это будет выглядеть примерно так: g(h(s(r(t(x))))) — просто какой-то ад из круглых скобок.
Бесточечная нотация функций
Бесточечная нотация — стиль описания функций без предварительного указания входных параметров. По началу такой стиль будет казаться необычным, но по мере продолжения, когда вы достаточно разберетесь, вы оцените лаконичность такого подхода. Вы заметите, что в mult5AfterAdd10 значение value определяется дважды. Один раз в списке параметров и один раз в момент использования.
-- Эта функция ожидает 1 входной параметрmult5AfterAdd10 value = (mult5Но этот параметр несущественен, так как add10, самая правая функция в композиции, ожидает тот же параметр. Следующая бесточечная версия — эквивалент предыдущей:
-- Эта функция тоже ожидает 1 входной параметрmult5AfterAdd10 = (mult5В использовании такого бесточечного подхода существует множество преимуществ. Во-первых, нам не нужно определять лишние параметры. И поскольку мы их не определяем, нам также не нужно придумывать им имена. Во-вторых, код становится легче читать и анализировать, так как он более лаконичный. Это простой пример, но представьте функцию, принимающую больше параметров.
Особенности безточесных функций
До сих пор мы разбирались, как работает композиция функций, и как следует определять функции при бесточечной нотации для лаконичности, чистоты и гибкости кода. Теперь давайте попробуем использовать эти идеи при слегка ином сценарии и посмотрим, насколько они ему соответствуют. Представьте, что мы заменяем add10 на add:
add x y = x + ymult5 value = value * 5Как нам создать mult5AfterAdd10, используя эти две функции? Ладно, если вы действительно потратите время, раздумывая над этим вопросом, то вернетесь примерно с таким решением:
-- Это неверно . mult5AfterAdd10 = (mult5Но такой код не будет работать. Потому что add принимает два параметра. Если это не так очевидно в Elm, попробуйте написать то же самое в JavaScript:
var mult5AfterAdd10 = mult5(add(10)); // не работаетЭтот код неверен, но почему? Потому что в нем функция add принимает лишь один из своих двух параметров, после чего передает ошибочные результаты в mult5. Это будет приводить к неверным решениям. По факту, в Elm компилятор не позволит вам даже написать такой нецелесообразный код (что является одним из больших плюсов языка Elm). Давайте попробуем еще раз:
var mult5AfterAdd10 = y => mult5(add(10, y)); // не бесточечный стильДа, это не бесточечный стиль, но я тем не менее могу жить с таким решением. В то же время, теперь я уже не просто комбинирую функции. Я пишу новую функцию. Также, если задача станет гораздо сложнее, к примеру, если я захочу скомпоновать mult5AfterAdd10 с какой-то другой функцией, я столкнусь с серьезной проблемой. Пока мы не можем «обвенчать» эти две функции, будет казаться, что идея композиции функций не обладает такой уж большой практической ценностью. И это очень плохо, потому что на самом деле это не так. Что ж, что было бы действительно хорошо, так это если бы у нас была идея, как предварительно передать нашей функции add один из ее входных параметров и уже позже — второй параметр, когда будет вызвана mult5AfterAdd10. Выходом из этого затруднительного положения является концепция каррирования.
Исследование, описанное в статье про 3 Композиция и суперпозиция функций в функциональном программировани, подчеркивает ее значимость в современном мире. Надеюсь, что теперь ты понял что такое 3 Композиция и суперпозиция функций в функциональном программировани и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Функциональное программирование Из статьи мы узнали кратко, но содержательно про