Concept
Coinduction
Concepts associés (5)
F-coalgèbre
En 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.
Bisimulation
En informatique théorique, une bisimulation est une relation binaire entre systèmes de transition d'états, associant les systèmes qui se comportent de la même façon au sens qu'un des systèmes simule l'autre et vice-versa. Intuitivement, deux systèmes sont bisimilaires s'ils sont capables de s'imiter l'un l'autre. Dans cette optique, les systèmes ne peuvent être distingués l'un de l'autre par un observateur.
Initial algebra
In 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.
Algorithme récursif
Un 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.
Évaluation paresseuse
L’évaluation paresseuse (), appelée aussi appel par nécessité ou évaluation retardée est une technique d'implémentation des programmes récursifs pour laquelle l'évaluation d'un paramètre de fonction ne se fait pas avant que les résultats de cette évaluation ne soient réellement nécessaires. Ces résultats, une fois calculés, sont préservés pour des réutilisations ultérieures. Dans un langage comme Haskell, l'évaluation est paresseuse par défaut.