В информатике, композиция функций является акт или механизм комбинировать простые функции для построения более сложных. Подобно обычному составу функций в математике, результат каждой функции передается как аргумент следующей, а результат последней является результатом целого.
Программисты часто применяют функции к результатам других функций, и почти все языки программирования позволяют это. В некоторых случаях композиция функций интересна как самостоятельная функция, которая будет использоваться позже. Такую функцию всегда можно определить, но языки с функциями первого класса упрощают ее.
Возможность легко составлять функции поощряет факторизацию (разделение) функций для удобства обслуживания и повторного использования кода. В более общем смысле, большие системы могут быть построены путем составления целых программ.
Грубо говоря, композиция функций применяется к функциям, которые работают с конечным объемом данных, причем каждый шаг последовательно обрабатывает их, прежде чем передать их следующему. Функции, которые работают с потенциально бесконечными данными ( потоком или другими кодовыми данными ), называются фильтрами, и вместо этого они соединяются в конвейер, который аналогичен композиции функций и может выполняться одновременно.
Например, предположим, что у нас есть две функции f и g, например, z = f ( y ) и y = g ( x ). Их составление означает, что мы сначала вычисляем y = g ( x ), а затем используем y для вычисления z = f ( y ). Вот пример на языке C :
float x, y, z; //... y = g(x); z = f(y);
Шаги можно объединить, если мы не дадим название промежуточному результату:
z = f(g(x));
Несмотря на различия в длине, эти две реализации вычисляют один и тот же результат. Вторая реализация требует только одной строки кода и в просторечии называется «хорошо составленной» формой. Читаемость и, следовательно, ремонтопригодность - одно из преимуществ хорошо составленных форм, поскольку для них требуется меньше строк кода, что сводит к минимуму «площадь поверхности» программы. Демарко и Листер эмпирически подтверждают обратную зависимость между площадью поверхности и ремонтопригодностью. С другой стороны, возможно злоупотребление сложными формами. Вложение слишком большого количества функций может иметь противоположный эффект, делая код менее удобным в обслуживании.
В стековом языке функциональная композиция еще более естественна: она выполняется путем конкатенации и обычно является основным методом разработки программ. Приведенный выше пример в Forth :
g f
Это возьмет все, что было в стеке раньше, применит g, затем f и оставит результат в стеке. См постфикса состав обозначения для соответствующей математической нотации.
Теперь предположим, что комбинация вызова f () для результата g () часто бывает полезной и которую мы хотим назвать foo (), чтобы использовать ее как самостоятельную функцию.
В большинстве языков мы можем определить новую функцию, реализованную путем композиции. Пример на C :
float foo(float x) { return f(g(x)); }
(длинная форма с промежуточными значениями тоже подойдет.) Пример в Форте :
: foo g f ;
В таких языках, как C, единственный способ создать новую функцию - это определить ее в исходном коде программы, что означает, что функции не могут быть составлены во время выполнения. Однако возможна оценка произвольной композиции предопределенных функций:
#include lt;stdio.hgt; typedef int FXN(int); int f(int x) { return x+1; } int g(int x) { return x*2; } int h(int x) { return x-3; } int eval(FXN *fs[], int size, int x) { for (int i=0; ilt;size; i++) x = (*fs[i])(x); return x; } int main() { // ((6+1)*2)-3 = 11 FXN *arr[] = {f,g,h}; printf("%d\n", eval(arr, 3, 6)); // ((6-3)*2)+1 = 7 arr[2] = f; arr[0] = h; printf("%d\n", eval(arr, 3, 6)); }
В языках функционального программирования композиция функций может быть естественным образом выражена как функция или оператор высшего порядка. На других языках программирования вы можете написать свои собственные механизмы для выполнения композиции функций.
В Haskell приведенный выше пример выглядит следующим образом:
foo = f. g
с помощью встроенного оператора композиции (.), который можно читать как f после g или g, составленного с помощью f.
Сам оператор композиции может быть определен в Haskell с помощью лямбда-выражения :
(.):: (b -gt; c) -gt; (a -gt; b) -gt; a -gt; c f. g = \x -gt; f (g x)
Первые строки описывают тип (.) - он принимает пару функций и возвращает функцию. Обратите внимание, что Haskell не требует указания точных типов ввода и вывода f и g, только отношения между ними (f должен принимать то, что возвращает g). Это делает (.) Полиморфным оператором.
Варианты Lisp, особенно Scheme, взаимозаменяемость кода и данных вместе с обработкой функций очень хорошо подходят для рекурсивного определения вариативного композиционного оператора.
(define (compose. fs) (if (null? fs) (lambda (x) x) ; if no argument is given, evaluates to the identity function (lambda (x) ((car fs) ((apply compose (cdr fs)) x))))) ; examples (define (add-a-bang str) (string-append str "!")) (define givebang (compose string-gt;symbol add-a-bang symbol-gt;string)) (givebang 'set) ; ===gt; set! ; anonymous composition ((compose sqrt negate square) 5) ; ===gt; 0+5i
Многие диалекты APL имеют встроенную функциональную композицию с использованием символа ∘
. Эта функция более высокого порядка расширяет функции композиции диадического применения боковой функции левого таким образом, что A f∘g B
есть A f g B
.
foo←f∘g
Дополнительно вы можете определить состав функций:
o←{⍺⍺ ⍵⍵ ⍵}
На диалекте, который не поддерживает встроенное определение с использованием фигурных скобок, доступно традиционное определение:
∇ r←(f o g)x r←f g x ∇
В Raku, как и в Haskell, есть встроенный оператор композиции функций, главное отличие в том, что он пишется как ∘
или o
.
my amp;foo = amp;f ∘ amp;g;
Также, как и в Haskell, вы можете сами определить оператор. Фактически, следующий код Raku используется для его определения в реализации Rakudo.
# the implementation has a slightly different line here because it cheats proto sub infix:lt;∘gt; (amp;?, amp;?) is equiv(amp;[~]) is assoclt;leftgt; {*} multi sub infix:lt;∘gt; () { *.self } # allows `[∘] @array` to work when `@array` is empty multi sub infix:lt;∘gt; (amp;f) { amp;f } # allows `[∘] @array` to work when `@array` has one element multi sub infix:lt;∘gt; (amp;f, amp;g --gt; Block) { (amp;f).count gt; 1 ?? -gt; |args { f |g |args } !! -gt; |args { f g |args } } # alias it to the "Texas" spelling ( everything is bigger, and ASCII in Texas) my amp;infix:lt;ogt;:= amp;infix:lt;∘gt;;
В Python способ определения композиции для любой группы функций заключается в использовании функции reduce (используйте functools.reduce в Python 3):
# Available since Python v2.6 from functools import reduce def compose(*funcs) -gt; int: """Compose a group of functions (f(g(h(...)))) into a single composite func.""" return reduce(lambda f, g: lambda x: f(g(x)), funcs) # Example f = lambda x: x + 1 g = lambda x: x * 2 h = lambda x: x - 3 # Call the function x=10 : ((x-3)*2)+1 = 15 print(compose(f, g, h)(10))
В JavaScript мы можем определить его как функцию, которая принимает две функции f и g и производит функцию:
function o(f, g) { return function(x) { return f(g(x)); } } // Alternatively, using the rest operator and lambda expressions in ES2015 const compose = (...fs) =gt; (x) =gt; fs.reduceRight((acc, f) =gt; f(acc), x)
В C # мы можем определить его как Func, который принимает две Func f и g и производит Func:
// Call example: // var c = Compose(f, g); // // Funclt;int, boolgt; g = _ =gt;... // Funclt;bool, stringgt; f = _ =gt;... Funclt;TIn, TOutgt; Composelt;TIn, TMid, TOutgt;(Funclt;TMid, TOutgt; f, Funclt;TIn, TMidgt; g) =gt; _ =gt; f(g(_));
Такие языки, как Ruby, позволяют вам самостоятельно создавать бинарные операторы:
class Proc def compose(other_fn) -gt;(*as) { other_fn.call(call(*as)) } end alias_method:+,:compose end f = -gt;(x) { x * 2 } g = -gt;(x) { x ** 3 } (f + g).call(12) # =gt; 13824
Однако в Ruby 2.6 был введен собственный оператор композиции функций:
f = proc{|x| x + 2} g = proc{|x| x * 3} (f lt;lt; g).call(3) # -gt; 11; identical to f(g(3)) (f gt;gt; g).call(3) # -gt; 15; identical to g(f(3))
Понятия композиции, в том числе принципа композиционности и компонуемости, настолько повсеместно, что многочисленные нити исследований были отдельно развивались. Ниже приведены примеры исследований, в которых понятие композиции занимает центральное место.
Целые программы или системы можно рассматривать как функции, которые можно легко составить, если их входные и выходные данные представляют собой четко определенные конвейеры, позволяющие легко компоновать фильтры, которые были настолько успешными, что стали образцом проектирования операционных систем.
Обязательные процедуры с побочными эффектами нарушают ссылочную прозрачность и, следовательно, не могут быть полностью составлены. Однако, если вы рассматриваете «состояние мира» до и после выполнения кода как его ввод и вывод, вы получите чистую функцию. Состав таких функций соответствует последовательному запуску процедур. Монады формализм использует эту идею включить побочные эффекты и I / O в функциональных языках.