stringtranslate.com

Композиция функций (информатика)

В информатике композиция функций — это действие или механизм объединения простых функций для построения более сложных. Как и в обычной композиции функций в математике , результат каждой функции передается как аргумент следующей , а результат последней является результатом целого.

Программисты часто применяют функции к результатам других функций, и почти все языки программирования это допускают. В некоторых случаях композиция функций интересна как функция сама по себе, чтобы использовать ее позже. Такую функцию всегда можно определить, но языки с функциями первого класса делают это проще.

Возможность легкого составления функций поощряет факторизацию (разбиение) функций для удобства обслуживания и повторного использования кода . В более общем плане, большие системы могут быть построены путем составления целых программ.

В узком смысле, композиция функций применяется к функциям, которые работают с конечным объемом данных, каждый шаг последовательно обрабатывает их перед передачей следующему. Функции, которые работают с потенциально бесконечными данными ( поток или другие кодированные данные ), известны как фильтры и вместо этого связаны в конвейер , который аналогичен композиции функций и может выполняться одновременно .

Составление вызовов функций

Например, предположим, что у нас есть две функции 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 ));

Несмотря на разницу в длине, эти две реализации вычисляют один и тот же результат. Вторая реализация требует только одной строки кода и в разговорной речи называется «высокосоставной» формой. Читабельность и, следовательно, поддерживаемость являются одним из преимуществ высокосоставных форм, поскольку они требуют меньше строк кода, минимизируя «поверхностную площадь» программы. [1] Демарко и Листер эмпирически проверяют обратную зависимость между поверхностной площадью и поддерживаемостью. [2] С другой стороны, может быть возможным чрезмерное использование высокосоставных форм. Вложение слишком большого количества функций может иметь противоположный эффект, делая код менее поддерживаемым.

В стековом языке функциональная композиция еще более естественна: она выполняется путем конкатенации и обычно является основным методом проектирования программ. Приведенный выше пример на языке Forth :

гф

Который возьмет то, что было в стеке до этого, применит g, затем f и оставит результат в стеке. Смотрите постфиксную нотацию композиции для соответствующей математической нотации.

Наименование состава функций

Теперь предположим, что комбинация вызова f() с результатом g() часто бывает полезной, и мы хотим назвать ее foo(), чтобы использовать как отдельную функцию.

В большинстве языков мы можем определить новую функцию, реализованную с помощью композиции. Пример на языке C :

float foo ( float x ) { return f ( g ( x )); }

(длинная форма с промежуточными формами тоже подойдет.) Пример на языке Forth :

  : фу гф ;

В таких языках, как C , единственный способ создать новую функцию — определить ее в исходном коде программы, что означает, что функции не могут быть составлены во время выполнения . Однако возможна оценка произвольной композиции предопределенных функций:

#include <stdio.h> 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 ; i < size ; i ++ ) x = ( * fs [ i ])( 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 с помощью лямбда-выражения :

( . ) :: ( б -> в ) -> ( а -> б ) -> а -> в ж . г = \ х -> ж ( г х )

Первая строка описывает тип (.) — он принимает пару функций f ,   g и возвращает функцию (лямбда-выражение во второй строке). Обратите внимание, что Haskell не требует спецификации точных входных и выходных типов f и g; a, b, c и x являются заполнителями; имеет значение только отношение между f ,   g (f должен принимать то, что возвращает g). Это делает (.) полиморфным оператором.

Лисп

Варианты Lisp , особенно Scheme , взаимозаменяемость кода и данных вместе с обработкой функций прекрасно подходят для рекурсивного определения вариативного композиционного оператора.

( define ( compose . fs ) ( if ( null? fs ) ( lambda ( x ) x ) ; если аргумент не указан, вычисляется функция тождественности ( lambda ( x ) (( car fs ) (( apply compose ( cdr fs )) x )))))                   ; примеры ( define ( add-a-bang str ) ( string-append str "!" ))     ( определить givebang ( составить строку->символ добавить-a-bang символ->строка ))     ( givebang 'set ) ; ===> set!  ; анонимная композиция (( compose sqrt negate square ) 5 ) ; ===> 0+5i

АПЛ

Многие диалекты APL имеют встроенную композицию функций с использованием символа ∘. Эта функция более высокого порядка расширяет композицию функций до диадического применения функции левой стороны, так A f∘g Bчто A f g B.

фу ← ф ∘ г

Кроме того, вы можете определить композицию функций:

о ← { ⍺⍺ ⍵⍵ ⍵ }

В диалекте, который не поддерживает встроенное определение с использованием фигурных скобок, доступно традиционное определение:

∇ r ← ( f o g ) x r ← f g x ∇

Раку

В Raku , как и в Haskell, есть встроенный оператор композиции функций, главное отличие в том, что он пишется как ∘или o.

мой & foo = & f ∘ & g ;

Также, как и в Haskell, вы можете определить оператор самостоятельно. Фактически, ниже приведен код Raku, используемый для его определения в реализации Rakudo .

# реализация имеет здесь немного другую строку, потому что она обманывает proto sub infix :<∘> (&?, &?) is equiv(&[~]) is assoc<left> { * }  multi sub infix :<∘> () { *. self } # позволяет `[∘] @array` работать, когда `@array` пуст multi sub infix :<∘> (&f) { & f } # позволяет `[∘] @array` работать, когда `@array` имеет один элемент multi sub infix :<∘> (&f, &g --> Block) { ( & f ) . count > 1 ?? -> | args { f | g | args } !! -> | args { f g | args } }                               # псевдоним к написанию "Texas" (все больше и ASCII в Texas) my & infix: <o> : = & infix: <∘> ;

Ним

Nim поддерживает единый синтаксис вызова функций , что позволяет создавать произвольные композиции функций с помощью оператора синтаксиса метода .. [3]

func foo ( a : int ): string = $ a func bar ( a : string , count : int ): seq [ string ] = for i in 0 .. < count : result . add ( a ) func baz ( a : seq [ string ] ) = for i in a : echo i                           # эквивалент! echo foo ( 5 ). bar ( 6 ). baz () echo baz ( bar ( 6 , foo ( 5 )))

Питон

В Python для определения композиции любой группы функций используется функция reduce (используйте functools.reduce в Python 3):

# Доступно начиная с Python v2.6 из  functools  import  reduce из  typing  import  Callabledef  compose ( * funcs )  ->  Callable [[ int ],  int ]: """Объединить группу функций (f(g(h(...)))) в одну составную функцию.""" return reduce ( lambda f , g : lambda x : f ( g ( x )), funcs )         # Пример f  =  лямбда  x :  x  +  1 g  =  лямбда  x :  x  *  2 h  =  лямбда  x :  x  -  3# Вызываем функцию x=10 : ((x-3)*2)+1 = 15 print ( compose ( f ,  g ,  h )( 10 ))

JavaScript

В JavaScript мы можем определить его как функцию, которая принимает две функции f и g и создает функцию:

функция o ( f , g ) { return function ( x ) { return f ( g ( x )); } }         // В качестве альтернативы можно использовать оператор rest и лямбда-выражения в ES2015 const compose = (... fs ) => ( x ) => fs . reduceRight (( acc , f ) => f ( acc ), x )

С#

В C# мы можем определить его как метод расширения, который принимает Func f и g и создает новый Func:

// Пример вызова: // var c = f.ComposeWith(g); // // Func<int, bool> g = _ => ... // Func<bool, string> f = _ => ...public static Func < T1 , T3 > ComposeWith < T1 , T2 , T3 > ( this Func < T2 , T3 > f , Func < T1 , T2 > g ) => x => f ( g ( x ));

Рубин

Такие языки, как Ruby, позволяют вам самостоятельно создать бинарный оператор:

class Proc def compose ( other_fn ) -> ( * as ) { other_fn . call ( call ( * as )) } end alias_method :+ , :compose end           f = -> ( x ) { x * 2 } g = -> ( x ) { x ** 3 } ( f + g ) . вызов ( 12 ) # => 13824

Однако в Ruby 2.6 был введен собственный оператор композиции функций: [4]

f = proc { | x | x + 2 } g = proc { | x | x * 3 } ( f << g ) . call ( 3 ) # -> 11; идентично f(g(3)) ( f >> g ) . call ( 3 ) # -> 15; идентично g(f(3))

Исследование опроса

Понятия композиции, включая принцип композиционности и композируемости , настолько вездесущи, что многочисленные направления исследований развивались отдельно. Ниже приведен пример исследований, в которых понятие композиции является центральным.

Масштабная композиция

Целые программы или системы можно рассматривать как функции, которые можно легко составить, если их входы и выходы четко определены. [5] Конвейеры, позволяющие легко составлять фильтры, оказались настолько успешными, что стали шаблоном проектирования операционных систем.

Императивные процедуры с побочными эффектами нарушают ссылочную прозрачность и, следовательно, не являются чисто компонуемыми. Однако, если рассматривать «состояние мира» до и после запуска кода как его вход и выход, то получается чистая функция. Композиция таких функций соответствует запуску процедур одна за другой. Монадный формализм использует эту идею для включения побочных эффектов и ввода/вывода (I/O) в функциональные языки.

Смотрите также

Примечания

  1. ^ Кокс (1986), стр. 15–17.
  2. ^ ДеМарко и Листер (1995), стр. 133–135.
  3. ^ "Руководство по Nim: Синтаксис вызова метода". nim-lang.org . Получено 17 августа 2023 г. .
  4. ^ "Ruby 2.6.0 Released". www.ruby-lang.org . Получено 2019-01-04 .
  5. ^ Рэймонд (2003)

Ссылки