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.
Algorithme récursifUn algorithme récursif est un algorithme qui résout un problème en calculant des solutions d'instances plus petites du même problème. L'approche récursive est un des concepts de base en informatique. Les premiers langages de programmation qui ont autorisé l'emploi de la récursivité sont LISP et Algol 60. Depuis, tous les langages de programmation généraux réalisent une implémentation de la récursivité. Pour répéter des opérations, typiquement, un algorithme récursif s'appelle lui-même.
Initial algebraIn mathematics, an initial algebra is an initial object in the of F-algebras for a given endofunctor F. This initiality provides a general framework for induction and recursion. Consider the endofunctor F : Set → Set sending X to 1 + X, where 1 is the one-point (singleton) set, the terminal object in the category. An algebra for this endofunctor is a set X (called the carrier of the algebra) together with a function f : (1 + X) → X. Defining such a function amounts to defining a point and a function X → X.
AnamorphismeL'anamorphisme (du Grec: = vers le haut; morphisme = forme) est un concept de la programmation fonctionnelle fondé sur la théorie des catégories. En programmation fonctionnelle, un anamorphisme est une généralisation des fonctions de type unfold permettant la création générique de liste au cadre des types de données arbitraires qui peuvent être décrites par des coalgèbres finales (ou « algèbres initiales »). Les anamorphismes, qui sont , sont la forme duale des catamorphismes récursifs, tout comme les unfolds sont une forme duale des folds.
F-coalgèbreEn mathématiques, et plus particulièrement en théorie des catégories, une -coalgèbre est une structure définie par rapport à un foncteur . La notion de -coalgèbre possède des applications en informatique, notamment pour l'évaluation paresseuse, pour les structures de données infinies comme les flux ou pour les systèmes transitionnels. Les -coalgèbres sont une forme duale des . On appelle -coalgèbre sur un endofoncteur tout objet de muni d'un -morphisme Les homomorphismes des -coalgèbres sont les morphismes dans tel que : Une -coalgèbre associée à un foncteur constitue une catégorie.
CatamorphismeDans la théorie des catégories, le concept de catamorphisme (du Grec: = vers le bas; morphisme = forme) dénote l'unique homomorphisme pour une algèbre initiale. Le concept a été appliqué dans la programmation fonctionnelle. Le concept dual est celui d'anamorphisme. En programmation fonctionnelle, un catamorphisme est une généralisation de la fonction fold sur les listes au cadre de types algébriques de données quelconques pouvant être décrit comme des algèbres initiales.
