**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.

Concept# Function composition

Summary

In mathematics, function composition is an operation ∘ that takes two functions f and g, and produces a function h = g ∘ f such that h(x) = g(f(x)). In this operation, the function g is applied to the result of applying the function f to x. That is, the functions f : X → Y and g : Y → Z are composed to yield a function that maps x in domain X to g(f(x)) in codomain Z.
Intuitively, if z is a function of y, and y is a function of x, then z is a function of x. The resulting composite function is denoted g ∘ f : X → Z, defined by (g ∘ f )(x) = g(f(x)) for all x in X.
The notation g ∘ f is read as "g of f ", "g after f ", "g circle f ", "g round f ", "g about f ", "g composed with f ", "g following f ", "f then g", or "g on f ", or "the composition of g and f ". Intuitively, composing functions is a chaining process in which the output of function f feeds the input of function g.
The composition of functions is a special case of the composition of relations, sometimes also denoted by . As a result, all properties of composition of relations are true of composition of functions, such as the property of associativity.
Composition of functions is different from multiplication of functions (if defined at all), and has some quite different properties; in particular, composition of functions is not commutative.
Composition of functions on a finite set: If f = {(1, 1), (2, 3), (3, 1), (4, 2)} , and g = {(1, 2), (2, 3), (3, 1), (4, 2)} , then g ∘ f = {(1, 2), (2, 1), (3, 2), (4, 3)} , as shown in the figure.
Composition of functions on an infinite set: If f: R → R (where R is the set of all real numbers) is given by f(x) = 2x + 4 and g: R → R is given by g(x) = x3, then:
If an airplane's altitude at time t is a(t), and the air pressure at altitude x is p(x), then (p ∘ a)(t) is the pressure around the plane at time t.
The composition of functions is always associative—a property inherited from the composition of relations. That is, if f, g, and h are composable, then f ∘ (g ∘ h) = (f ∘ g) ∘ h.

Official source

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related publications (4)

Related concepts (154)

In mathematics, function composition is an operation ∘ that takes two functions f and g, and produces a function h = g ∘ f such that h(x) = g(f(x)). In this operation, the function g is applied to the result of applying the function f to x. That is, the functions f : X → Y and g : Y → Z are composed to yield a function that maps x in domain X to g(f(x)) in codomain Z. Intuitively, if z is a function of y, and y is a function of x, then z is a function of x.

In group theory, Cayley's theorem, named in honour of Arthur Cayley, states that every group G is isomorphic to a subgroup of a symmetric group. More specifically, G is isomorphic to a subgroup of the symmetric group whose elements are the permutations of the underlying set of G. Explicitly, for each , the left-multiplication-by-g map sending each element x to gx is a permutation of G, and the map sending each element g to is an injective homomorphism, so it defines an isomorphism from G onto a subgroup of .

In mathematics, particularly in , a morphism is a structure-preserving map from one mathematical structure to another one of the same type. The notion of morphism recurs in much of contemporary mathematics. In set theory, morphisms are functions; in linear algebra, linear transformations; in group theory, group homomorphisms; in analysis and topology, continuous functions, and so on.

Related courses (14)

Étudier les concepts fondamentaux d'analyse et le calcul différentiel et intégral des fonctions réelles d'une variable.

Après une introduction à la théorie des catégories, nous appliquerons la théorie générale au cas particulier des groupes, ce qui nous permettra de bien mettre en perspective des notions telles que quo

Ce cours entend exposer les fondements de la géométrie à un triple titre :
1/ de technique mathématique essentielle au processus de conception du projet,
2/ d'objet privilégié des logiciels de concept

Related lectures (278)

Derivability and Chain RuleMATH-101(d): Analysis I

Covers the demonstration of the chain rule and the theorem of Rolle.

Function CompositionMATH-101(de): Analysis I (German)

Covers the concept of function composition and the properties of bijections when composing functions.

Model Extension and Composition of FunctionsMATH-101(f): Analysis I

Explores model extension, function composition, graph uniqueness, and mathematical induction principles.

Non-malleable codes are a generalization of classical error-correcting codes where the act of "corrupting" a codeword is replaced by a "tampering" adversary. Non-malleable codes guarantee that the message contained in the tampered codeword is either the original message m, or a completely unrelated one. In the common split-state model, the codeword consists of multiple blocks (or states) and each block is tampered with independently. The central goal in the split-state model is to construct high rate non-malleable codes against all functions with only two states (which are necessary). Following a series of long and impressive line of work, constant rate, two-state, non-malleable codes against all functions were recently achieved by Aggarwal et al. [2]. Though constant, the rate of all known constructions in the split state model is very far from optimal (even with more than two states). In this work, we consider the question of improving the rate of splitstate non-malleable codes. In the "information theoretic" setting, it is not possible to go beyond rate 1/2. We therefore focus on the standard computational setting. In this setting, each tampering function is required to be efficiently computable, and the message in the tampered codeword is required to be either the original message m or a "computationally" independent one. In this setting, assuming only the existence of one-way functions, we present a compiler which converts any poor rate, two-state, (sufficiently strong) non-malleable code into a rate-1, two-state, computational non-malleable code. These parameters are asymptotically optimal. Furthermore, for the qualitative optimality of our result, we generalize the result of Cheraghchi and Guruswami [10] to show that the existence of one-way functions is necessary to achieve rate > 1/2 for such codes. Our compiler requires a stronger form of non-malleability, called augmented non-malleability. This notion requires a stronger simulation guarantee for non-malleable codes and simplifies their modular usage in cryptographic settings where composition occurs. Unfortunately, this form of non-malleability is neither straightforward nor generally guaranteed by known results. Nevertheless, we prove this stronger form of non-malleability for the two-state construction of Aggarwal et al. [3]. This result is of independent interest.

We define twisted composition products of symmetric sequences via classifying morphisms rather than twisting cochains. Our approach allows us to establish an adjunction that simultaneously generalizes a classic one for algebras and coalgebras, and the bar-cobar adjunction for quadratic operads. The comonad associated to this adjunction turns out to be, in several cases, a standard Koszul construction. The associated Kleisli categories are the "strong homotopy" morphism categories. In an appendix, we study the co-ring associated to the canonical morphism of cooperads , which is exactly the two-sided Koszul resolution of the associative operad , also known as the Alexander-Whitney co-ring.

2019Many software systems consist of data processing components that analyse large datasets to gather information and learn from these. Often, only part of the data is relevant for analysis. Data processing systems contain an initial preprocessing step that filters out the unwanted information. While efficient data analysis techniques and methodologies are accessible to non-expert programmers, data preprocessing seems to be forgotten, or worse, ignored. This despite real performance gains being possible by efficiently preprocessing data. Implementations of the data preprocessing step traditionally have to trade modularity for performance: to achieve the former, one separates the parsing of raw data and filtering it, and leads to slow programs because of the creation of intermediate objects during execution. The efficient version is a low-level implementation that interleaves parsing and querying. In this dissertation we demonstrate a principled and practical technique to convert the modular, maintainable program into its interleaved efficient counterpart. Key to achieving this objective is the removal, or deforestation, of intermediate objects in a program execution. We first show that by encoding data types using Böhm-Berarducci encodings (often referred to as Church encodings), and combining these with partial evaluation for function composition we achieve deforestation. This allows us to implement optimisations themselves as libraries, with minimal dependence on an underlying optimising compiler. Next we illustrate the applicability of this approach to parsing and preprocessing queries. The approach is general enough to cover top-down and bottom-up parsing techniques, and deforestation of pipelines of operations on lists and streams. We finally present a set of transformation rules that for a parser on a nested data format and a query on the structure, produces a parser specialised for the query. As a result we preserve the modularity of writing parsers and queries separately while also minimising resource usage. These transformation rules combine deforested implementations of both libraries to yield an efficient, interleaved result.