Arbre enracinéEn théorie des graphes, un arbre enraciné ou une arborescence est un graphe acyclique orienté possédant une unique racine, et tel que tous les nœuds sauf la racine ont un unique parent. En informatique, c'est également une structure de données récursive utilisée pour représenter ce type de graphes. Dans un arbre, on distingue deux catégories d'éléments : les feuilles (ou nœuds externes), éléments ne possédant pas de fils dans l'arbre ; les nœuds internes, éléments possédant des fils (sous-branches).
Définition par récurrencevignette|4 étapes de la construction d'un flocon de Koch. Comme beaucoup d'autres fractales, cette courbe est définie par récurrence. En mathématiques, on parle de définition par récurrence pour une suite, c'est-à-dire une fonction définie sur les entiers positifs et à valeurs dans un ensemble donné. Une fonction est définie par récurrence quand, pour définir la valeur de la fonction en un entier donné, on utilise les valeurs de cette même fonction pour des entiers strictement inférieurs.
GénéricitéEn programmation, la généricité (ou programmation générique), consiste à définir des algorithmes identiques opérant sur des données de types différents. On définit de cette façon des procédures ou des types entiers génériques. On pourrait ainsi programmer une pile, ou une procédure qui prend l'élément supérieur de la pile, indépendamment du type de données contenues. C'est donc une forme de polymorphisme, le « polymorphisme de type » dit aussi « paramétrage de type » : en effet, le type de donnée général (abstrait) apparaît comme un paramètre des algorithmes définis, avec la particularité que ce paramètre-là est un type.
Fonction d'ordre supérieurEn mathématiques et en informatique, les fonctions d'ordre supérieur sont des fonctions qui ont au moins une des propriétés suivantes : elles prennent une ou plusieurs fonctions en entrée ; elles renvoient une fonction. En mathématiques, on les appelle des opérateurs ou des fonctionnelles. L'opérateur de dérivation en calcul infinitésimal est un exemple classique, car elle associe une fonction (la dérivée) à une autre fonction (la fonction que l'on dérive). Dans le lambda-calcul non typé, toutes les fonctions sont d'ordre supérieur.
Map (higher-order function)In many programming languages, map is the name of a higher-order function that applies a given function to each element of a collection, e.g. a list or set, returning the results in a collection of the same type. It is often called apply-to-all when considered in functional form. The concept of a map is not limited to lists: it works for sequential containers, tree-like containers, or even abstract containers such as futures and promises. Suppose we have a list of integers [1, 2, 3, 4, 5] and would like to calculate the square of each integer.
Fold (higher-order function)In functional programming, fold (also termed reduce, accumulate, aggregate, compress, or inject) refers to a family of higher-order functions that analyze a recursive data structure and through use of a given combining operation, recombine the results of recursively processing its constituent parts, building up a return value. Typically, a fold is presented with a combining function, a top node of a data structure, and possibly some default values to be used under certain conditions.
Standard MLStandard ML (SML) is a general-purpose, modular, functional programming language with compile-time type checking and type inference. It is popular among compiler writers and programming language researchers, as well as in the development of theorem provers. Standard ML is a modern dialect of ML, the language used in the Logic for Computable Functions (LCF) theorem-proving project. It is distinctive among widely used languages in that it has a formal specification, given as typing rules and operational semantics in The Definition of Standard ML.
Filtrage par motifLe filtrage par motif est la vérification de la présence de constituants d'un motif par un programme informatique, ou parfois par un matériel spécialisé. Par contraste avec la reconnaissance de forme, les motifs sont complètement spécifiés. De tels motifs concernent conventionnellement des séquences ou des arbres. Par exemple "HDpdf" peut signifier : "Toute chaîne contenant HD et se terminant par pdf".
TypeParameterIn computer programming languages, TypeParameter is a generic label used in generic programming to reference an unknown data type, data structure, or class. TypeParameter is most frequently used in C++ templates and Java generics . TypeParameter is similar to a metasyntactic variable (e.g., foo and bar), but distinct. It is not the name of a generic type variable, but the name of a generic type of variable. The capitalisation varies according to programming language and programmer preference.
Zipping (computer science)In computer science, zipping is a function which maps a tuple of sequences into a sequence of tuples. This name zip derives from the action of a zipper in that it interleaves two formerly disjoint sequences. The inverse function is unzip. Given the three words cat, fish and be where |cat| is 3, |fish| is 4 and |be| is 2. Let denote the length of the longest word which is fish; . The zip of cat, fish, be is then 4 tuples of elements: where # is a symbol not in the original alphabet.
