Modèles fonctionnels : interfaces et foncteurs

Ceci est la troisième partie d'une série d'articles intitulée Modèles fonctionnels.

Assurez-vous de consulter le reste des articles !

1. Le Monoïde
2. Compositions et implicitement

Génériques et classes de types

Pour être correcte, une fonction doit vérifier le type et est donc prouvable. Mais dans le cas de fonctions généralisées, destinées à traiter différents types, cela apparaît immédiatement comme un problème. Pour qu'une double fonction fonctionne sur plusieurs types, nous devrions les définir séparément !

doubleInt :: Int -> Int
doubleChar :: Char -> Char
doubleFloat :: Float -> Float
-- ...

Et pour tout programmeur qui se respecte, vous devriez déjà vous sentir absolument consterné par cela. Nous venions de découvrir un modèle pour créer une gestion de cas à l'aide d'une application partielle mais nous ne pouvons pas vraiment l'appliquer ici car nos signatures de type ne le permettent pas, et notre fonction a pour vérifier la saisie.

Heureusement, c'est déjà une fonctionnalité dans la plupart des langages de programmation modernes. Nous sommes autorisés à définir un type générique. Un type hypothétique qui doit uniquement vérifier les positions correspondantes dans la signature de fonction ou les déclarations de variables.

// c++
template <typename T>
T double(T x) {
    return x*2;
}

// rust
fn double<T>(x: T) -> T {
    return x*2;
}

-- haskell
double :: a -> a
double = (*2)       -- partially applied multiplication

Et ça devrait résoudre notre problème ! Tant que le compilateur reçoit ces génériques, il peut déterminer quels types il doit utiliser au moment de l'exécution (Rust fait toujours cette inférence au moment de la compilation !).

Cependant, même si cette implémentation présente des avantages, il existe toujours un défaut flagrant, qui est en fait signalé par le compilateur Haskell, car le code Haskell ci-dessus génère en fait une erreur.

Aucune instance pour 'Num a' résultant de l'utilisation de '*'...

Nous avons défini un type, mais nous n'allons pas toujours être sûrs que ce type a la capacité d'être doublée. Bien sûr, cela fonctionne immédiatement sur les nombres, mais qu'est-ce qui empêche l'utilisateur d'appeler double sur une chaîne ? Une liste ? Sans une méthode prédéfinie pour doubler ces types, ils ne devraient pas être autorisés comme arguments, en premier lieu.

Donc contrairement au nom de génériques, il va falloir être un peu plus spécifique, mais toujours général.

C'est là qu'interviennent les classes de types, ou également connues plus communément dans le monde impératif sous le nom d'interfaces. Encore une fois, si vous utilisez un langage créé après C++, vous devriez avoir accès à une certaine implémentation d'interfaces.

Les interfaces, par rapport aux génériques, spécifient une sorte de capacité de types qui peuvent être catégorisés en dessous.

Voici une version corrigée de notre code précédent.

double :: (Num a) => a -> a     -- a has to be of typeclass Num
double = (*2)

ou en Go :

// We first create an interface that is the union of floats and integers.
type Num interface {
    ~int | ~float64
    // ... plus all other num types
}

func double[T Num](a T) T {
    return a * 2
}

Par souci de brièveté, nous dirons qu'Haskell ne s'occupe pas vraiment de l'état intégré dans ses interfaces, telles que les interfaces Typescript et Go (une contrainte provoquée par des règles fonctionnelles pures). Ainsi, même si vous pouvez définir des attributs requis d'un type à placer sous une interface, sachez que les interfaces pures n'ont qu'à définir des fonctions ou capacités du type.

Et par capacités dans ce contexte, nous parlons de savoir si le type a une dépendance sous la forme d'une fonction de doublement - le compilateur apprend comment le doubler ?

import Control.Monad (join)

class CanDouble a where
  double :: a -> a

instance CanDouble Int where
  double = (* 2)

instance CanDouble Float where
  double = (* 2)

-- we tell the compiler that doubling a string is concatenating it to itself.
instance CanDouble String where 
  double = join (++)    -- W-combinator, f x = f(x)(x)

Et maintenant, nous sommes quasiment revenus à là où nous en étions au début en matière de répétition de code, n'est-ce pas drôle ?

Mais ce contrôle précis de la mise en œuvre est en fait là où la puissance de ceci entre en jeu. Si vous avez déjà entendu parler du modèle Stratégie auparavant, c'est à peu près cela, au sens fonctionnel.

quadruple :: (CanDouble a) => a -> a
quadruple = double . double

leftShift :: (CanDouble a) => Int -> a -> a
leftShift n e
  | e <= 0 = n
  | otherwise = leftShift (double n) $ e - 1

Ces fonctions vérifient le type maintenant, tout cela parce que nous enseigné au compilateur comment doubler les types sous la classe de types CanDouble.

Nous pouvons réaliser quelque chose de similaire dans Go, une grosse mise en garde étant que nous ne pouvons définir des méthodes d'interface que sur des types non primitifs. Cela signifie que nous devons définir des structures wrapper pour des types primitifs.

type CanDouble interface {
    double() CanDouble
}

type String string
type Number interface {
    ~int | ~float64
    // ... plus all other num types
}

type Num[T Number] struct {
    v T
}

func (s String) double() String {
    return s + s
}

func (n Num[T]) double() Num[T] {
    return Num[T]{n.v * 2}
}

func quadruple(n CanDouble) CanDouble {
    return n.double().double()
}

func leftShift(n CanDouble, e uint) CanDouble {
    for i := uint(0); i < e; i++ {
        n = n.double()
    }

    return n
}

Honnêtement, c'est un peu décevant, mais ne vous inquiétez pas, car la plupart du temps, vous aurez affaire à des interfaces avec des types et des structures personnalisés.

Catégories

La théorie des catégories est une théorie générale des structures mathématiques et de leurs relations.

Nous avons brièvement abordé la théorie des catégories dans The Monoid, et nous aimerions que cela reste ainsi, uniquement des rencontres rapprochées. J'y ferai référence ici et là, mais rassurez-vous : vous n'aurez pas besoin d'avoir une formation en la matière pour comprendre ce qui suit.

Cependant, il ne fait aucun doute que nous avons déjà rencontré des ensembles.

En bref récapitulatif, les ensembles peuvent être considérés comme une collection d'éléments. Ces éléments peuvent être absolument n'importe quoi.

{ 0, 1, 2, 3, ... }             -- the set of natural numbers
{ a, b, c, ..., z}              -- the set of lowercase letters
{ abs, min, max, ... }          -- the set of `Math` functions in Javascript
{ {0, 1}, {a, b}, {abs, min} }  -- the set of sets containing the first 2 elements of the above sets

Adding on to that, we have these things called morphisms, which we can think of a mapping between elements.

Very big omission here on the definitions of morphisms, in that they are relations between elements, and not strictly functions/mappings,
you can look it up if you are curious.

We can say a function like toUpper() is a morphism between lowercase letters to uppercase letters, just like how we can say double = (*2) is a morphism from numbers to numbers (specifically even numbers).

And if we group these together, the set of elements and their morphisms, we end up with a category.

Again, omission, categories have more constraints such as a Composition partial morphism and identities. But these properties are not that relevant here.

If you have a keen eye for patterns you'd see that there is a parallel to be drawn between categories and our interfaces! The objects (formal name for a category's set of elements) of our category are our instances, and our implementations are our morphisms!

class CanDouble a where
    double :: a -> a

-- `Int` is our set of elements { ... -1, 0, 1, ... }
-- `(* 2)` is a morphism we defined
-- ... (other omissions)
-- ...
-- Therefore, `CanDouble Int` is a Category.
instance CanDouble Int where
    double = (* 2)

Functors

Man, that was a lot to take in. Here's a little bit more extra:

A Functor is a type of a function (also known as a mapping) from category to another category (which can include itself, these are called endofunctors).

What this essentially means, is that it is a transformation on some category that maps every element to a corresponding element, and every morphism to a corresponding morphism. An output category based on the input category.

In Haskell, categories that can be transformed by a functor is described by the following typeclass (which also makes it a category in of itself, that's for you to ponder):

class Functor f where
    fmap :: (a -> b) -> f a -> f b
    -- ...

f here is what we call a type constructor. By itself it isn't a concrete type, until it is accompanied by a concrete type. An example of this would be how an array isn't a type, but an array of Int is. The most common form of a type constructor is as a data type (a struct).

From this definition we can surmise that all we need to give to this function fmap is a function (a -> b) (which is our actual functor, don't think about the naming too much), and this would transform a type f a to type f b, a different type in the same category.

Yes, this means Haskell's Functor typeclass is actually a definition for endofunctors, woops!

If all of that word vomit was scary, a very oversimplified version for the requirement of the Functor typeclass is that you are able to map values to other values in the same category.

Arguably the most common Functor we use are arrays:

instance Functor [] where
--  fmap f [] = []
--  fmap f (a:as) = f a : fmap as

    -- simplified
    fmap :: (a -> b) -> [a] -> [b]
    fmap f arr = map f arr

We are able to map an array of [a] to [b] using our function (or functor) f. The typeconstructor of [] serves as our category, and so our functor is a transformation from one type of an array to another.

So, formally: the map function, though commonly encountered nowadays in other languages and declarative frameworks such as React, is simply the application of an endofunctor on the category of arrays.

Wow. That is certainly a description.

Here are more examples of functors in action:

// Go
type Functor[T any] interface {
    fmap(func(T) T) Functor[T]
}

type Pair[T any] struct {
    a T
    b T
}

type List[T any] struct {
    get []T
}

// Applying a functor to a Pair is applying the function
// to both elements
func (p *Pair[T]) fmap(f func(T) T) Pair[T] {
    return Pair[T]{     // apply f to both a and b
        f(p.a),
        f(p.b),
    }
}

func (a *List[T]) fmap(f func(T) T) List[T] {
    res := make([]T, len(a.get))    // create an array of size len(a.get)

    for i, v := range a.get {
        res[i] = f(v)
    }

    return List[T]{res}
}

-- haskell
data Pair t = P (t, t)

instance Functor Pair where
    fmap f (P (x, y)) = P (f x, f y)

So all that it takes to fall under the Functor (again, endofunctor), interface is to have a definition on how to map the contents of the struct to any other type (including its own).

This is another simplifcation, functors also need to have property of identity and composition.

To put simply, whenever you do a map, you're not only transforming the elements of your array (or struct), you're also transforming the functions you are able to apply on this array (or struct). This is what we mean by mapping both objects and morphisms to different matching objects and morphisms in the same category.

This is important to note as even though we end up in the same category (in this context, we map an array, which results in another array), these might have differing functions or implementations available to them (though most of them will be mapped to their relatively equivalent functions, such as a reverse on an array of Int to reverse on an array of Float).

C'est là que la simplifcation à outrance nous dérange un peu, car si on suit uniquement notre définition, on pourrait dire que les fonctions réductrices comme sum et concat sont des foncteurs de la catégorie des tableaux aux atomes, mais ce n'est pas forcément le cas vrai. Comme les foncteurs exigent également que vous préserviez la structure catégorielle, qui ne sera pas abordée dans cette série d'articles car elle est beaucoup trop profondément enracinée dans la théorie des catégories.

---

Désolé si cet article contenait beaucoup plus de mathématiques que d'applications, mais comprendre ces définitions nous aidera grandement à comprendre les modèles les plus difficiles plus tard dans cette série, à savoir les applicatifs et enfin les monades.

Une monade est un monoïde dans la catégorie des endofoncteurs.

On y arrive ! :>

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!