Функциональная композиция (информатика) - Function composition (computer science)

Не путать с композицией объекта .

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

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

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

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

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

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

   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

В Haskell приведенный выше пример выглядит следующим образом: 

foo = f . g

с помощью встроенного оператора композиции (.), который можно читать как f после g или g, составленного с помощью f .

Сам оператор композиции может быть определен в Haskell с помощью лямбда-выражения : 

(.) :: (b -> c) -> (a -> b) -> a -> c
f . g = \x -> 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->symbol add-a-bang symbol->string))

(givebang 'set) ; ===> set!

; anonymous composition
((compose sqrt negate square) 5) ; ===> 0+5i

APL

Многие диалекты 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 &foo = &f ∘ &g;

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

# the implementation has a slightly different line here because it cheats
proto sub infix:<∘> (&?, &?) is equiv(&[~]) is assoc<left> {*}

multi sub infix:<∘> () { *.self } # allows `[∘] @array` to work when `@array` is empty
multi sub infix:<∘> (&f) { &f }   # allows `[∘] @array` to work when `@array` has one element
multi sub infix:<∘> (&f, &g --> Block) {
    (&f).count > 1
    ?? -> |args { f |g |args }
    !! -> |args { f g |args }
}

# alias it to the "Texas" spelling ( everything is bigger, and ASCII in Texas )
my &infix:<o> := &infix:<∘>;

Python

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

# Available since Python v2.6
from functools import reduce

def compose(*funcs) -> 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

В 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) => (x) => fs.reduceRight((acc, f) => f(acc), x)

C #

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

// Call example:
//   var c = Compose(f, g);
//
//   Func<int, bool> g = _ =>  ...
//   Func<bool, string> f = _ => ...

Func<TIn, TOut> Compose<TIn, TMid, TOut>(Func<TMid, TOut> f, Func<TIn, TMid> g) => _ => f(g(_));

Рубин

Такие языки, как 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).call(12) # => 13824

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

f = proc{|x| x + 2}
g = proc{|x| x * 3}
(f << g).call(3) # -> 11; identical to f(g(3))
(f >> g).call(3) # -> 15; identical to g(f(3))

Исследовательский опрос

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

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

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

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

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

Заметки

Рекомендации