Les fonctions

Après les catégories, les fonctions. 

Les fonctions

Une fonction c'est... 

1) Un être potentiel, défini par sa capacité à transformer n'importe quel élément issu d'un tas d'objets. 

Un tas d'objet, c'est un "type" d'objet, et une fonction transforme tout élément d'un tas en un élément d'un autre tas.

f: A -> B         après le ":" , la "signature" de la fonction, qui associe deux types identifiés. 

Un point important: une fonction "marche" pour TOUS les éléments du type de départ. Elle est "totale". 

2) La définition de la fonction, c'est autre chose, elle s'exprime en général avec une "chose" supposée être mise à la place d'un élément quelconque de A lors de l'application de la fonction. 

f = lambda a  EXPRESSION(a) 

Ici, EXPRESSION (a) désigne une formule avec a en variable libre et qui produit un B (bien sur).

3) Bon on attaque direct, on veut définir des fonctions en fonction d'autres fonctions, avec l'aide d'"opérateurs": 

f then g = lambda x g(f(x)) 

Une fonction, c'est une abstraction pour un "calcul", qui transforme une donnée. C'est un "pas" élémentaire dans une marche globale, mais abstrait: il faut appliquer la fonction pour qu'un travail soit fait. En attendant, c'est juste un plan, un ordre, une recette. 

On notera "id" la fonction identité. 

Au fait,

f then id == f 

id then f == f

Bien sur le "==" est assertif: il dénote l'égalité entre deux expressions définissant des fonctions. 

Le rêve, et fantasme assumé ici, est de ne jamais parler des fonctions à partir de leur définitions, la lambda pue. On veut parler de tout ça de haut, on n'est pas des programmeurs, nous, berk. 

La curryfication. 

Les fonctions de plusieurs arguments sont en fait des fonctions de un argument composées, qui se passent des fonctions. 

f: A , B -> C   se note en fait f: A -> B -> C

Haskell Curry a inventé tout ça. Au fait c'est le Curry de Curry Howard et le Haskell du langage de programmation... 

 

 

Les foncteurs 

Les types d'objets peuvent être transformés. Par des "foncteurs". 

Les foncteurs les plus connus sont les "monades". On va bien sur considérer ici exclusivement les monades... 

En gros, un foncteur c'est une monade qui n'a que l'opérateur "map". Les monades ont des opérateurs supplémentaires.

Par exemple, Option (ou Maybe), OP. 

OP(A) est un nouveau type construit à partir de A, avec un élément en plus, NONE. Cela permet d'exprimer des raisonnements en supposant (indument) que tout type possède une valeur supplémentaire "null", "none", "rien", "zéro pointé", qui exprime l'absence, la non présentabilité, l'impossible. Par exemple, lorsqu'une opération de recherche d'un objet de type "Personne" ne trouve rien, que doit retourner l'opération? Elle pourrait retourner une Personne particulière, la personne vide, mais cela serait paradoxal: s'il n'y a personne, il n'y a pas quelqu'un. On convient donc, trop souvent, de retourner une valeur unique, le fameux, l'infâme "null". C'est pour cela qu'une opération qui retourne soit disant une Personne et qui ose à son gré retourner parfois "null" ne peut prétendre être "typée". Elle est plutôt, et à strictement parler, "vérolée": tremble utilisateur ! On te ment.

C'est ainsi donc, finalement, pour cela que OP, comme type suprême, permet de rétablir l'honnête: tu recevra dans tous les cas un élément du type "OP[Personne]" et parfois, NONE, c'est à ça qu'on le reconnait. Voilà qui est propre. 

Mieux! OP permet d'appliquer à ce qu'il cache toute opération spécifique du scellé objet: avec une fonction.

p: OP[Personne]

p.map( x -> x.désignetoi())  

La fonction "cachée" désignera toujours une personne, à moins qu'on lui donne NONE. Dans ce cas, map retournera DIRECTEMENT NONE, et donc évitera la confrontation de l'absence et de l'opération qui ne la supporterait pas. 

Bon on arrête là. OP, Option, Maybe est le truc du fonctionnel pour en terminer avec les pointeurs nuls. Simple, efficace et qui aurait du être adopté bien plus tôt dans l'histoire, cela nous aurait fait perdre moins de temps... Pour en finir vraiment, il bien comprendre en plus que NONE ne remplace par "null" lui même, ce qui ne changerait pas grand chose, mais bien la honteuse erreur du "pointeur nul" déclenchée immédiatement par toute opération sur la honteuse valeur non typée.  

Plus exactement, la notion de "monade" est entièrement contenue dans l'exemple de OP. Disons de plus, pour adopter un vocabulaire plus "fonctionnel" qu'une expression de calcul, utilisée pour définir une fonction peut décider de considérer OP(X) plutôt que X comme type de destination, et donc décider de produire un "effet" en plus du calcul. Disons que cet "effet" va consister dans certains cas, à produire la fameuse valeur NONE, porteuse d'une signification particulière, qui est précisément l'absence de calcul. 

En fait, tout ce qu'on va dire s'applique ici à X mais en fait à n'importe quel autre "foncteur", dont OP. Imaginer qu'un foncteur est un truc aussi stupide que "Option", qui permet de représenter n'importe quel objet de type X, y compris son absence, qui plus est typée, m'a toujours ravi. Représenter l'absence par un élément supplémentaire est jouissif, désolé. Que la quintessence de la monade soit précisément cette construction est une bénédiction. Profitons en. 

L'opérateur "return"

Considérons la fonction "X.r". Par définition, elle construit un objet de type X(A) à partir d'un objet de A. Elle ne produit jamais "NONE", dans le cas de OP. Un foncteur c'est pas bijectif, et au combien.

X.r: A -> X(A), et cela "pour tout" A. Dans le cas de OP, OP.r est bien sur l'identité. 

En fait, X.r marche pour n'importe quel objet, de n'importe quel type. Une fonction générique, en quelque sorte. 

Il s'agit du constructeur élémentaire, de l'application primale. On l'appelle "return", ou "point".  

Le "map"

Maintenant, prenons X(A), et une fonction de A vers B. Et bien, 

X.m: X(A) -> (A->B) -> X(B) 

X.m la fonction "supérieure" de "mapping", qui va transformer X(A) en X(B). Ce qui caractérise la functoritude. 

On reconnaitra ici la célèbre "commutabilité" de la théorie des catégories: 

A partir d'un a dans A, je peux: 

- appliquer une fonction de type A->B, puis construire un X(B) avec X.r

- construire un X(A) grâce à X.r, puis appliquer X.m à la fonction et obtenir un X(B)

Il va sans dire que les deux X(B) que l'on va obtenir sont égaux, par définition. 

Si f: A->B, 

f then X.r == X.r then X.m(f)  

 Quand je dis "sont" je veux dire "doivent être". Ces choses sont soumises à des lois qui caractérisent leur existence, et c'est (encore) à cela qu'on les reconnait. 

 

Le "flatmap" et la monade 

Il y a un autre "opérateur" de foncteur, "flatmap", "bind" ou ">>="

X.fm : X(A)   -> (   A->X(B)   )  -> X(B)

On commence tout de suite à bétonner en reliant fm et m:

X.fm(f then X.r) == X.m(f) 

C'est assez logique en fait: fm porte sur une fonction qui produit un OP(B), lui même construit par "r". Ce type d'assertions est assez naturel, et typique des catégories: tout ce qui est naturel se manifeste, c'est fait pour, c'est la nature... Il s'agit d'un raisonnement "aux dimensions": les lois de la nature c'est pareil, E = m * v^2, c'est pas dur à trouver. 

Commentons avec la sémantique de Option.

Soit un calcul qui donne une OP(A) et un calcul qui donne une OP(B). On veut séquencer les deux calculs, sachant que le deuxième s'exprime en fonction d'un "A" (bien sur, c'est ça un "chainage"). Le "then" ne marche pas: en effet, le deuxième calcul ne peut avoir lieu si le premier retourne NONE: un pointeur null ça fait planter. Il faut donc, pour séquencer correctement, tester le pointeur null, ici le NONE. Et  bien, imaginons un séquenceur intelligent, dépendant de OP, qui le fasse, bingo, c'est "fm". Et oui.

OP.fm( résultat du calcul1, fonction définissant le calcul2) = résultat du chainage du calcul1 et du calcul2

C'est cette expression qui fait dire que la monade est l'"essence du séquencement" en programmation: la présence du NONE, qui peut survenir dans n'importe quel calcul intermédiaire implique bien sur alors la valeur finale du calcul (NONE, bien sur). 

Mais c'est grâce au fait que OP est une monade, et donc en fait à sa fonction flatmap, qu'on "peut" enchainer des blocs fonctionnels construits indépendamment. 

Pour enfoncer le clou, il faut comprendre que ce qu'on veut composer, ce n'est pas simplement des fonctions, par exemple f: A-> B et g : B->C, cela on sait le faire, mais des fonctions qui ont "de l'effet", c'est à dire f: A ->X(B) et B->X(C). Pour ce faire, il faut un truc qui dépende de X et qui encapsule le transfert de l'effet à travers la deuxième fonction. Ce truc est bien sur "flatmap". 

La notation ">>=" permet d'avoir un "flatMap" exprimé en notation infixe. C'est le nouveau "then", le then avec effet. 

flatMap est une fonction de fonction étrange, qui connait intimement sa monade: elle plonge dedans, trouve l'objet encapsulé, et lui applique une fonction de création d'une autre monade. C'est pour cela que si la fonction de création est le "return", fonction de création de base, on obtient l'identité: 

X.fm(X.r) == id, ce qui est bien sur une "loi".  

La séquence 

On en vient à la séquence "monadique", qui permet de chainer des calculs en se ramenant, cela m'avait perturbé au début, tant je trouvais cela ridicule: quoi ? Tous ces efforts pour se ramener à de l'impératif ? 

En gros, on peut archiver dans un contexte (un "for" scala, typiquement, ou un "do" haskell), plusieurs objets d'un type de monade donné (une seule, pas de mélange), les nommer, appeler des fonctions avec ces noms, puis finalement générer une expression de sortie avec ces noms. Et bien le résultat sera une instance de ce type monadique, construite avec l'expression de sortie. 

La construction fonctionnelle est une suite de flatMap emboités (c'est pour cela qu'on l'appelle "bind") représentant chaque extraction monadique nommée, finalisée par un map.

Toute les utilisations des monades mettent en valeur cette construction. Par exemple, si des "get" dans des hashtables retournent des OP, on peut faire avec profit: 

for

     x<- OP(1)

     y <- OP("foo")

yield x + y.length 

retourne OP(4)

 Cette "reductio at imperativo" (...) est précisément l'objet, intérêt et but de la monade. Au delà de l'identification du monadique au calculatoire, retenons plutôt qu'il s'agit d'une astuce permettant de garder les avantages de l'impératif tout en restant fonctionnel. Ainsi, flatmap, en gardant de coté NONE dans un séquencement où la chose apparait, permet d'éviter la bébête exception ou les méchants return emboités que nécessiterait la prise en compte du NONE. La gestion de l'"effet" est fournie par le type de donnée et son flatmap, qui en assure le transfert dans un chainage fonctionnel.   

Le Kleisli 

Un autre opérateur c'est K: 

f K g = f then OP.fm(g) 

K est une manière de faire des flatmaps dans l'ordre, et donc permet d'exprimer "naturellement" (au fur et à mesure qu'on le fait) des calculs. 

Ici, la notation fait que "K" trouve tout seul le bon fm à appliquer suivant les types des valeurs de retour des fonctions. 

K est l'opérateur "fish" noté ">=>"

f : A -> OP(B) 

g: B -> OP(C) 

et donc f >=> g : A -> OP(C)

 

Le Kleisli a bien sur de super bonnes propriétés, par exemple: 

f K OP.r == f      (bien sur ici,  la deuxième fonction a pour domaine le type d'option...

OP.r K f == f

f K g K h == (f K g) K h == f K (g K h)

 

La monade STATE

On va se permettre (après coup) un petit ride sur la monade STATE. Là l'idée est que l'effet du calcul emboité va consister à chaque appel à modifier une valeur, et donc à mettre à jour un "état" qu'on va transmettre à l'appel suivant. C'est ça l'"effet". Pour éviter de 

Pour commencer, le type de la monade STATE est un type FONCTIONNEL, un type de fonction. Perturbant, mais une fonction est une valeur comme un autre. Pour en rajouter à l'abstraction perturbante, il faut considérer un type en plus, celui de la donnée stockée, ici S. A est le type monadisé, mais pour pouvoir le lier à l'état, il faut une fonction... 

STATE(S,A) = S =>(S, A) 

A partir de là, on va pouvoir élaborer... S est le type de stockage du "state", et A son expression. Le type de A peut être quelconque pour un STATE donné, et c'est là une première source d'obscurité, ou de compréhension profonde. Disons que A est le type normal résultat du calcul, et que S est le type de la donnée qu'on veut modifier par effet de bord. 

 

Prenons un "state" qui serait une pile (par exemple). Une liste d'entiers. 

STATE n'exprime pas une structure de données, mais ce qu'on peut faire avec, en fait TOUTES les opérations possibles sur le type de stockage qu'il/elle encapsule. 

pop = s == Nil => (Nil, None) , s == h::t => (h, t) 

push a =  s => (a::s, Unit) 

Les deux opérations expriment des opérations possibles et retournent des STATES (des objets de type STATE, c'est à dire des fonctions). Ainsi, pop() (  List(1,2) )  retournera  (List(2), 1)  comme de bien entendu.

 

On a donc bien ici un principe de construction de programme, et non pas de la simple programmation... 

Mieux que ça, 

SI on convient de noter que

a) dans le tuple t = (S, A), S s'obtient en écrivant "t.S" et A en écrivant "t.A"; 

b) 

map  state: STATE ,  f: A => B               =         s => (         state(s).S       ,        f ( state(s).A )                ) 

flatMap state: STATE  ,  f: A => STATE(S,B)    =         s =>   (        state(s).S     ,      f (     state(s).A    ).B      ) 

 

On va utiliser Kleisli et donc construire un programme, complètement abstrait: 

pop() >=> x => if (x.isempty) push(1) else push(2) ) >=> x => push(33) 

Dans ces chaines d'instructions, le "state" est passé magiquement de manière invisible, chaque fonction

intermédiaire prenant en paramètre la valeur calculée précédemment. 

Une autre notation

Toujours à la recherche d'une bonne notation, et après coup, en voilà une autre. 

D'abord on va éviter au maximum d'utiliser des variables et de préférer les combinateurs, à tout prix. 

f= Int -> Int ; inc  // inc est la fonction qui ajoute 1  à son argument

f= Int -> Int ; x + 2   // x est le premier argument, y le deuxième s'il y a lieu. 

On cherchera également à noter de la même façon les fonctions et les types paramétrés: 

Option =  *->*; None, T   // T est le premier paramètre de type. 

Option T est le type produit par l'application du constructeur Option au type T... 

 

Si on veut réutiliser un argument dans l'expression de definition d'une fonction, on peut "forker": 

f= Int -> Int ; (id, id) (inc, x + 3) *  

Qu'on peut noter aussi, * étant naturellement "à deux places" et donc "infixe":  f = (id, id) (inc * (x+3) )

Ou bien:  f = inc * ( x+3)

 

La monade State nouvelle notation

A partir de là , on définir la monade State comme:

State S = *->*; S -> (S,T)  // T est le type paramètre, et State S est le constructeur

State.map = State S T , T -> T' ;       x  then (id , y )  

State.flatMap  State S T , T -> State S T' ;       x  then (id, y then ((x,y) then y)   )   

 

La monade Reader nouvelle notation 

Reader C = C -> T 

Reader.map  =  (Reader C T') (x then y)

Reader.flatMap Reader C T,  T -> (Reader C T') =   ((x, id)  then ((x , z ) ( (y x)    z) )   

def flatMap(  r: Reader[C,T], f: T => Reader[C,T']) = Reader[C,T']( c => f(r.read(c)).read(c) )

 

La monade Reader est typique  d'une monade "terminale": elle se résoud par le calcul à la fin de tous les appels qu'on lui fait: 

r = for (  a<- Reader (inc) ;  b <- Reader( (inc inc) ) )  ( a + b ) 

r est un reader, c'est à dire une fonction, qui est NON APPLIQUEE.

On lui applique la "racine" de la configuration, pour obtenir le résultat final. Chaque fonction de chaque reader est un "shift" par rapport à la racine. 

r: C -> T,  r(1000) == 1001 + 1002 = 2003

 

Types algébriques

Il nous faut parler des types dits "algébriques" car défini suivant les cas... Il faut bien pouvoir aussi définir les types en les composant, et ici on exprime qu'un élément est d'une type donné quand il est "ça" ou (|) "ça". "ça" cela peut être une suite fini de cas. 

L'arbre "ou/et" de définition fait ainsi toute l'algèbre de la définition des types. Ah que c'est bon que de calculer sur autre chose que des nombres...

List(A) = NIL | A  List (A)

en gros une liste de "A" (on a bien un foncteur pour commencer) et bien c'est soit NIL , soit  la concaténation d'un objet de type A et d'une liste de A... La définition est "récursive", y a pas que les fonctions. 

Un point: y a pas non plus que Haskell dans la vie et ma syntaxe c'est celle qu'est à moi.

De plus, deux listes se concatènent avec l'opérateur (de liste) "++". 

Il faut comprendre que List est un "foncteur", et que le type algébrique est un constructeur de type paramétré par un type. Nous voilà avec un langage de programmation qu'est déjà bien puissant... 

Folding

Les fonctions récursives, c'est bien et les schémas de récursion encore mieux. Ce sont des fonctionnelles, des fonctions de fonctions et l'incontournable "foldr" (ou "reduce") se doit d'être décrit. 

Soit une fonction à deux arguments, qui donne un résultat, par exemple l'addition des entiers: 

f: A -> A -> B

"foldr" se définit sur une liste comme donnant ce résultat, à partir d'une fonction comme ça, et d'une valeur initiale du résultat. Il s'agit de se déplacer sur la liste, et d'accumuler.  

foldr : fonction  valeur_initiale_de_type_B    List A  -> B 

foldr f b NIL = b   // b est bien une valeur initiale, fin de récursion, la valeur initiale est le résultat. 

fold f b (h:t) =   f   h     (foldr f b t )    // on extrait la tête de liste et on récurse... 

On a bien le "schéma" général de calcul qui consiste à prendre le premier élément de liste, et l'additionner au "reste", qui une application récursive sur le reste de la liste...

Grâce à foldr, on a bien des expression purement fonctionnelle de calculs récursifs variés: 

sum = foldr + 0 

filter g = foldr ((lambda x if (g x) (List x ) else NIL )  then ++ )  NIL 

En effet,

    filter (lambda x x == 1) NIL == NIL 

    filter (lambda x x == 1) List(1) == 1  (...)  foldr (...) NIL NIL == List 1 ++ NIL 

Bien évidemment, ces schémas de récursion, sortes de méta programme, se trouvent à faire pour tous les types qu'on peut définir. Faut abstraire dans la vie.

 

LES folds

Il y a en fait plusieurs folds... 

La définition de "sum" faite ici avec foldr est consommatrice de "pile": 

sum (1 2) = 1 + (foldr '+  0 (2)) = 1 + 2 + (foldr '+ 0 ()) = 1 + 2 + 0

Il faut attendre la toute fin de l'exploration récursive pour enfin pouvoir additionner quelquechose...

C'est pour ça qu'on a fait foldl (fold left):

foldl f b nil = b        // comme pour foldr

foldl f b (h:t) =  foldl f ( f b h) t        // on calcule DABORD  une operation binaire) 

Ainsi donc   foldl + 0 (1,2) = foldl f (0 + 1=1) (2) = foldl  f  3 () = 3

Pas de mémorisation inutile en apparence, pourtant, la fonction est bien récursive et consomme de la pile aussi...

Folding généralisé

On peut folder n'importe quoi. Par exemple des arbres. 

On reprend. 

Tree(A) = NIL         |           Tree(A)     A      Tree(A)

tfold : B -> f -> Tree(A) -> B       (avec f : B -> A -> B -> B)

tfold b _ NIL = b ; tfold b f  (l x r) = f ( tfold b f l ) x (tfold b f r) 

Alors, on peut lister les valeurs des noeuds d'un arbre: 

flatten (NIL) = NIL ; flatten l x r = flatten (l) ++ List(x) ++ flatten (r)

Autrement dit: 

flatten = tfold NIL (lambda ( l x r )  l ++ List(x) ++ r)

 

Au fait, on peut folder Option.... 

 

 

Les schémas de récursion sont importants, tu parles. Revenons sur le plus simple d'entre eux

Super Types

Un type a un type, on dit une "sorte" (kind). Integer a pour sorte "*", et OP, "* -> *". 

Un Functor, c'est donc un "* -> *", mais avec une methode, dite "fmap" en fait ici "m".

F.m : (A -> B) -> F(A)  ->  F(B) presque comme on avait dit... 

Les "classifications"

List est bien sur une monade. List(A) un type intéressant, vraiment pas en bijection avec A puisqu'exprimant n'importe quelle multiplicité de A... On avait parlé de "++". Il vient d'autre chose qu'un type algébrique, qui n'a pas d'opérateurs à priori. Et bien pour introduire des opérateurs, on va appliquer des foncteurs, les différents types de foncteurs portant des opérateurs particuliers. 

On a vu les opérateurs m et fm, spécialisés selon les foncteurs et notés comme tels plus haut, par exemple "OP.m".

Avant de nous lancer dans l'apprentissage des syntaxes diverses de Haskell ou Scala (ce qu'on ne veut pas faire), disons qu'on peut regrouper les opérateurs et les "projeter" sur un type algébrique avec un foncteur.

Par exemple, il existe un foncteur super utile qui s'appelle le "monoïde", noté ici MON. Il a pour opérateurs 0 et + avec bien sur les signatures suivantes: 

MON(m) = 0 : m      ,    + : m -> m -> m

C'est un foncteur avec ses lois, et donc sa fonction MON.m ou fmap... 

La "freeness" ou "libertitude"

Prenons la liste, est bien on peut lui appiquer le foncteur Monoïde sur les types, et cette application est dite "libre" ("free") dans la mesure où elle est triviale, évidente. La liste est le "free monoïd" sur les types... Le "plus" monoïdal est bien sur le "++" des listes. Le Monoïde engendre la multiplicité. Notons ici que le free monoïde a pour caractéristique de NEPAS modifier ce qu'il transforme: les listes concaténées restent là. Cette interprétation de l'addition est distinguée (c'est ça la libertitude) de l'addition arithmétique, qui elle "détruit" ses entrées... 

Cette notion de libertitude (freeness) est la source d'un concept de haute volée en fonctionnel: la "free monad", parangon de la modernité en programmation.

En gros, la monade libre, c'est la libertitude que donne un foncteur spécial, nommé Free, et appliqué, c'est ça le truc, à un foncteur particulier.  Le résultat est une monade spéciale, tout comme la liste est un ensemble spécial... Etant "free" la transformation ne va pas perdre ou détruire les données d'entrée. Celles ci étant des instructions, on ne va pas "exécuter" le programme, mais en garder la représentation intacte.  

Il faut bien comprendre que Free est la concaténation d'un foncteur et d'un type. C'est sur ce type là que l'on a une monade... 

Free F A = A |   F (   Free F A   ) 

charmant emboitement, quasiment naturel, on dirait (tu parles comme c'est un hasard) une expression du point fixe (comme en (3), pardon de me citer moi même). On a une structure récursive d'application du foncteur, se terminant sur un type donné. 

Pour illustrer les propriétés de la bête, prenons OP.m définie sur OP(A). Trivialement: 

OP(A) = NONE | OP(a)  // on le rappelle

Voyons voir une expression de la fonction m dans mon langage à moi, on distingue les cas plus haut: 

OP.m f NONE  = NONE   |   OP.m f OP(a)  = OP (  f( a))      // f est bien sur une fonction de A vers B

 

Pour List c'est pareil: 

List(A) = NIL  | A List(A) 

List.m NIL f = NIL

List.m f (A LIST (A))   = List.m f ( List(a) ++ s )  = List(f(a))  ++  List.m f s   

 

Pour Free, c'est pareil:

Free F A = A | F ( Free F A )

Free.m  f  A =  Free.m  f  a = f(a)  ;    Free.m  f  F(x)   =  F ( F.m ( Free.m f) F(x)  )  

  

On continue avec les opérateurs de monade: 

Free.r  Free F(a) = a 

Free.fm  f  a = f(a)

Free.fm f Free F(X) = Free( F(X).m (Free.fm f) F(X) ) 

On a donc bien une monade, avec la flatmap définie de manière récursive... 

Pour finir, on a un operateur spécial supplémentaire pour Free, dit "lift", pour "pousser vers le haut" un bête foncteur et le transformer en monade. 

Free.lift: F(A) -> Free F A

 

Definir un DSL à partir d'un type algébrique

On en vient alors à ce qu'on fait de tout ça. 

Soit le type "Move" paramétré par "Position". On a: 

Move [Position] = Forward [Position] | Backward [Position]

L'idée est de travailler dans le monde "Free", qui va nous faire une monade de tout cela (c'est l'intérêt). 

Les fonctions forward et backward prenant Position en paramètre, au lieu de bêtement changer de position, vont retourner une monade libre en liftant l'instruction correspondante paramétrée par leur paramètre: 

def forward: Position -> Free Move Position = p -> Free.lift ( Forward (p) ) 

A partir de là, on peut appliquer le langage des monades, et enchainer les opérations: 

forward (p1) >=> backward(p2) ...

Le résultat sera l'accumulation non destructive de toutes les opérations faites, c'est à dire le programme prêt à être exécuté, complètement représenté. Le langage de programmation est donc ici utilisé d'une manière spéciale avec un "cran en plus": les structure de données sont utilisées pour représenter non pas le monde qu'on souhaite modifier, mais la machinerie qui sera utilisée pour changer le monde... Et bien ce type de programmation là, il est "post von neumann" (je me lance), quasiment gödelien, auto codé. 

Programmer avec les monades libres.

La programmation avec les monades libres se fait donc en deux temps. Typiquement en codant d'abord avec l'image par Free des types algébriques qu'on pourrait définir, et qui sont, comme de juste des foncteurs. Le résultat sera une structure de données qu'on pourra introspecter en la matchant avec les transformés par Free des différents types, laissés intacts. On peut alors soit les afficher au mur, soit les exécuter, avec l'efficacité que l'on veut... 

Une telle programmation est dite "interprétative": on code la sémantique de son programme, charge ensuite à un exécuteur d'en faire ce qu'il veut. Cette disjonction coordonnée entre les deux phases du plus beau métier du monde a peut être un avenir, mais reste suspendue à la qualité des exécuteurs. Ah la belle sémantique qui rendrait évidente les parallélismes vrais, ceux qui seraient quantisables... L'histoire n'est donc pas finie, tiens tiens... 

Le pattern "interpréteur"

Tout ça est en fait une manière convoluée et un peu prétentieuse d'appliquer le patter "interpréteur", comme expliqué avec enthousiasme au paragraphe précédent. Un autre exemple est la monade "Reader". Elle prend en paramètre une fonction dite "run" (tiens, tiens) qui à un objet configuration indéterminé associe une donnée à lire...

Reader.m (f) = run then f   // mapper c'est transformer

Reader.fm (f)  = lambda c (run then f)(c).run (c)    

2 choses ici.

- Un Reader "calculé", comme par exemple ici '(run then f)(c)'    (f ayant pour domaine un Reader), contient une fonction. On l'obtient conventionnellement ici en appliquant la méthode "run", qui retourne une fonction. Fonction que l'on peut appliquer.

On peut alors utiliser les Reader pour configurer un programme, celui n'étant exécuté QUE quand la configuration sera disponible, typiquement en appelant la méthode "run" et en lui passant en paramètre, (on dit aussi "injecter") une configuration particulière...

On commence par construire une abstraction du programme.

monprogramme = for ( x<- Reader(c-> c.get) ) yield program(x)

Cela utilise le "for" monadique, qui permet de chainer tout ce qu'on veut, le résultat est une monade Reader, qu'il n'y a plus qu'à exécuter dans le contexte de son choix. 

Par exemple

maconfig = anykindofconfig

puis

monprogramme.run(maconfig)

 

C'est pas fini !  

En fait, tout ça est loin d'être fini, et ça généralise à fond la caisse. Histoire d'avoir une vision un peu stratosphérique de tout ça, voir (5): le langage de programmation SCALA pourrait bien être champion du monde... 

Mieux que Free, mais avec le principe de la programmation "interprétative", on a le maintenant fameux "tagless final"... Uberalles.

 

Allez Encore ! 

Le concept de fonction abordé ici est cependant honteusement sous défini. Il néglige ce qui caractérise le fonctionnel c'est à dire les vraies propriétés de ce qu'on appelle les "fonctions" en programmation dite fonctionnelle à cause de cela. Une fonction DOIT :

- être totale entre ses deux types d'origine et de destination. Un type c'est un type et comme null n'a pas de type, il est donc interdit de l'utiliser. Ca tombe bien, les notions exposées ci dessus permettent de s'en passer.  

- être déterministe et donner toujours le même résultat pour la même entrée. Cela a un gros inconvénient et qui est qu'une fonction fonctionnelle ne peut pas lire son environnement et procéder à ce qu'on appelle des "entrées", par exemple lire un fichier, dont le contenu est variable. 

- être sans effets de bord, c'est à dire ne produire aucune donnée qui ne soit contenue dans la sortie. Cela a un gros inconvénient et qui est qu'une fonction fonctionnelle ne peut pas modifier son environnement et procéder à ce qu'on appelle des "sorties", par exemple imprimer sur la console, ou écrire dans un fichier. 

La conséquence des deux dernières  définitions est simple: une fonction fonctionnelle n'a pas droit aux entrées sorties... Du tout. 

Vexés par la contrainte, les hackeurs de l'avenir décidèrent alors que la programmation fonctionnelle serait châtrée de toute expression extérieure et condamnée donc pour toujours à l'abstraite noirceur de l'intériorité absolue capable exclusivement de retourner à la fin UN SEUL objet: un programme. Ce programme impur et impropre au bien, serait la seule chose laissée au monde ignoble du réel, construit par application du pattern "interpréteur", et en charge de faire toutes les saletés nécessaires à ce monde. 

Le fonctionnel pur a donc pour rôle de construire l'impur programmatique, en charge de dévider, d'un coup à la fin, toutes les communications avec toutes les entités extérieures. On remarquera que c'est là et seulement là que se situe l'effectif, et l'action véritable. Le "calcul" fonctionnel, exclusivement pur, reste un calcul soumis au temps, mais à un temps qui n'est que préparation, mise en ordre d'une structure, optimisée et optimisable pour mieux se dévider "à la fin".  

(1) https://wiki.haskell.org/Monad

(2) http://www.cis.upenn.edu/~cis194/spring13/lectures.html

(3) http://francoiscarmignola.hautetfort.com/archive/2017/08/26/les-types-5974046.html

(4) https://markkarpov.com/post/free-monad-considered-harmful.html

(5) https://infoscience.epfl.ch/record/229878/files/simplicitly_1.pdf

(6) Un "pense bête" similaire avec toutes les vraies expressions: https://www.slideshare.net/pjschwarz/kleisli-composition-flatmap-join-map-unit-implementation-and-interrelation