✖


Jump to content

Функциональная композиция (информатика)

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

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

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

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

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

Составление вызовов функций [ править ]

Например, предположим, что у нас есть две функции 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] С другой стороны, возможно злоупотребление сложными формами. Вложенность слишком большого количества функций может иметь противоположный эффект, делая код менее удобным в сопровождении.

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

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 пример foo = f ∘ g приведенный выше выглядит следующим образом: 

foo = f . g

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

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

(.) :: (b -> c) -> (a -> b) -> a -> c
f . g = \x -> f (g x)

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

foo←f∘g

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

o←{⍺⍺ ⍵⍵ ⍵}

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

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

Raku [ edit ]

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:<∘>;

Nim [ edit ]

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

# equivalent!
echo foo(5).bar(6).baz()
echo baz(bar(6, foo(5)))

Питон [ править ]

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

# Available since Python v2.6
from functools import reduce
from typing import Callable

def compose(*funcs) -> Callable[[int], 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# мы можем определить его как метод расширения, который принимает Funcs f и g и создает новый Func: 

// Call example:
//   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).call(12) # => 13824

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

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))

Исследование [ править ]

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

Масштабная композиция [ править ]

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

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

См. также [ править ]

Примечания [ править ]

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

Ссылки [ править ]

Retrieved from "https://en.wikipedia.org/w/index.php?title=Function_composition_(computer_science)&oldid=1224096497"
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 588871e463c0b0b90727b3a327984afb__1715830620
URL1:https://arc.ask3.ru/arc/aa/58/fb/588871e463c0b0b90727b3a327984afb.html
Заголовок, (Title) документа по адресу, URL1:
Function composition (computer science) - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)