Apprendre la programmation fonctionnelle avec le MOOC OCaml

Posté par  . Édité par Benoît Sibaud, palm123, jcr83 et dourouc05. Modéré par bubar🦥. Licence CC By‑SA.
26
15
sept.
2016
Éducation

Pour la deuxième année consécutive, l'université Paris Diderot, en partenariat avec la Sorbonne, INRIA, IRILL et OCamlPro, organise un MOOC d'initiation à la programmation fonctionnelle avec le langage OCaml. Les leçons débuteront le 26 septembre 2016 et se termineront le 12 décembre. Les cours seront donnés en anglais mais des sous-titres sont disponibles aussi bien en anglais qu'en français. Il est toutefois possible de s'inscrire jusqu'au 25 novembre pour les retardataires.

Sommaire

Note préliminaire de l'auteur de la dépêche

Je ne suis nullement affilié ou lié en quelque façon aux personnes et à l'équipe pédagogique qui sont à l'origine de la formation. Les parties sur la description et le contenu de celle-ci, ainsi que celle sur la présentation de l'équipe, sont mes traductions de matériaux que l'on trouve dans leur courrier d'annonce sur la liste de diffusion ou sur la page d'inscription.

En revanche, les exemples de code en OCaml à la fin de la dépêche sont de moi et relèvent d'un choix personnel pour illustrer le langage. Au cas où ceux-ci seraient jugés confus ou peu pédagogiques, il ne faudrait pas que ces défauts soient considérés comme relevant de l'équipe pédagogique de la formation, mais devrait plutôt être mis au compte de ma seule responsabilité. Au demeurant, je suis conscient de n'être ni fin pédagogue, ni bon didacticien.

La formation

La programmation fonctionnelle attire l'intérêt d'un large spectre de développeurs, car elle permet d'écrire des programmes expressifs, concis et élégants.

La formation « Introduction à la programmation fonctionnelle avec le langage OCaml » introduit progressivement les notions centrales de la programmation fonctionnelle, à travers une série de vidéos pédagogiques complétées par un riche ensemble d'exercices que vous pouvez effectuer entièrement dans votre navigateur… Oui, cela signifie que vous pouvez commencer à apprendre la programmation fonctionnelle sans prise de tête : rien à installer, rien à configurer, l'environnement de programmation est à une portée de clic !

Au cours de la formation, vous découvrirez des mécanismes puissants pour construire et manipuler des structures de données de manière claire et efficace. Et vous verrez comment les fonctions jouent un rôle central, en tant que citoyens de première classe qui peuvent être librement utilisés à chaque endroit où un terme du langage peut apparaître (une fonction peut retourner une fonction, ou prendre une autre fonction parmi ses paramètres).

Les inscriptions sont déjà ouvertes sur la plateforme fun-mooc à l'adresse suivante : s'inscrire à la formation « Introduction à la programmation fonctionnelle avec le langage OCaml ». La formation débutera le 26 septembre 2016 et durera six semaines, et la date de clôture des inscriptions est fixée au 25 novembre : vous pouvez prendre le train en marche ! :-)

Le temps de travail attendu est compris entre 2 et 6 heures par semaine — en fonction de votre niveau initial — ce qui comprend le temps passé à visionner les courtes séquences vidéos des leçons, dont la durée est approximativement d'une heure par semaine.

Cela peut sembler un effort significatif, mais à la fin de la formation vous aurez appris de nombreuses choses : le projet final confirmera votre bonne maîtrise de la programmation fonctionnelle et votre capacité à développer des programmes de taille moyenne avec aisance.

Des milliers d'étudiants ont suivi la première session de cette formation qui s'est terminée en janvier 2016, et la majorité d'entre eux en ont été extrêmement satisfaits.

Afin d'introduire la programmation fonctionnelle, nous avons choisi d'utiliser le langage OCaml. OCaml est un langage riche, élégant et efficace qui réconcilie la concision et la flexibilité des langages sans annotations de types (comme Python, par exemple) avec la sécurité des langages fortement et statiquement typés (comme Java, C ou C++ par exemple). Ce qui signifie que si votre programme compile alors vous n'aurez pas d'erreur de typage à l'exécution, sans avoir pour autant à annoter votre code pour cela. Le langage dispose de plus d'une communauté d'utilisateurs dynamique.

Facebook, Microsoft, JaneStreet, Bloomberg font partie des grands noms de l'industrie qui ont adopté OCaml pour développer des applications de pointe. La communauté de la recherche utilise OCaml pour écrire des outils comme l'assistant de preuve Coq, le convertisseur de programme Coccinelle, l'analyseur de code Frama-C, ou l'analyseur statique Astree. De nombreuses start-up utilisent OCaml pour décupler leur productivité et la stabilité de leur base de code.

Une fois que vous commencerez à maîtriser la programmation fonctionnelle en OCaml, nous sommes certains que vous ne regarderez plus les autres langages de la même façon.

La formation se déroulera en anglais, mais des sous-titres sont déjà disponibles en anglais et en français. Nous remercions à ce titre les nombreux bénévoles, avec une mention spéciale pour Jean-François Monin qui s'est occupé seul de la version française.

Pour bénéficier pleinement de cette formation il est préférable que vous ayez déjà des connaissances de base en programmation, en particulier vous devriez savoir écrire de simples programmes dans un autre langage. Par exemple, vous devriez connaître des notions comme les variables (ou identifiants), les fonctions (ou procédures, méthodes), les structures conditionnelles, et les boucles.

Le contenu des cours

Les leçons se dérouleront sur six semaines avec une courte introduction en préambule. Chaque semaine abordera un nouveau trait du langage, et elle se conclura par une série d'exercices pour contrôler la bonne assimilation des nouvelles notions introduites. À la fin de celles-ci, chaque étudiant devra réaliser un petit projet afin d'obtenir son certificat de validation.

  1. Introduction et vue d'ensemble
  2. Types de base, définitions et fonctions
  3. Structures de données de base
  4. Structures de données plus avancées
  5. Fonctions d'ordre supérieur
  6. Exceptions, entrées/sorties et construction impérative
  7. Modules et abstraction de données

Les vidéos pédagogiques sont diffusées sous licence CC BY-NC-ND et tout le code servant à la formation (environnement de travail, moteur de correction…) sous licence LGPLv2 ou GPLv2 (celui de la première session est disponible à cette adresse)

L'équipe pédagogique

L'équipe pédagogique est constituée de trois enseignants chercheurs de l'université Paris Diderot qui s'occupent des cours en vidéos, et de deux ingénieurs en recherche et développement chez OcamlPro qui se sont occupés des exercices et de l'environnement de développement.

Roberto Di Cosmo

Roberto Di Cosmo est professeur d'informatique à l'Université Paris Diderot, directeur de l'IRILL (Initiative de Recherche et Innovation sur le Logiciel Libre), et actuellement détaché à l'INRIA. Ses thèmes de recherche incluent la programmation fonctionnelle et parallèle, les systèmes de types, la logique, la réécriture et l'analyse statique d'une large collection de logiciels. Dans le milieu du logiciel libre, il est entre autre connu pour être à l'origine du projet Mancoosi et du projet Software Heritage présenté dans le journal Bibliothèque d'Alexandrie du logiciel libre.

Yann Regis-Gianas

Yann Régis-Gianas enseigne la science informatique à l'Université Paris Diderot. Ses recherches au laboratoire PPS (Preuves, Programmes et Systèmes) se concentrent sur la théorie et la conception des langages. Il a effectué son doctorat dans l'équipe INRIA qui développe OCaml et est maintenant dans l'équipe de développement de l'assistant de preuves Coq.

Ralf Treinen

Ralf Treinen est professeur d'informatique à l'Université Paris Diderot. La résolution par contrainte symbolique, la vérification et l'application des méthodes formelles pour l'assurance qualité des logiciels sont parmi ses thèmes de recherches actuels. Il est également membre de l'IRILL.

Benjamin Canou

Benjamin Canou est ingénieur R&D chez OCamlPro. Il a travaillé sur l'environnement des exercices, conçu l'évaluateur automatique, et écrit la plupart des exercices. Il a une solide expérience de l'enseignement d'OCaml à l'université, ainsi que des formations à OCaml pour les professionnels.

Grégoire Henry

Grégoire Henry est ingénieur R&D chez OCamlPro. Il a travaillé sur l'environnement des exercices, en particulier l'éditeur de texte avec coloration syntaxique et indentation automatique, et sur le toplevel (la boucle d'interaction). Il a également de l'expérience dans l'enseignement d'OCaml à l'Université Paris Diderot, et la formation professionnelle pour OCamlPro.

Quelques exemples de code

Pour terminer cette dépêche, rien de tel que de montrer quelques exemples de code fonctionnel en OCaml. Je montrerai la plupart du temps les résultats suite à l'utilisation de la boucle interactive (REPL).

Le traditionnel "Hello World !"

Bon, là on fait dans le classique.

(* pour appeler une fonction on écrit son nom puis
 * ses arguments séparés par des espaces *)
print_endline "Hello World !";;
Hello World !
- : unit = ()

Visitor pattern sur un arbre binaire

Cette fois on aborde une structure de données assez élémentaire : les arbres binaires dont les feuilles sont toutes de type int. Puis on définira une fonction générique de parcours de l'arbre (analogue au visitor pattern de la POO) pour effectuer différentes opérations sur celui-ci.

(* on définit le type de nos arbres binaires :
 *  soit on a une feuille avec un int
 *  soit on a un nœud avec deux sous arbres *)
type tree = 
  | Leaf of int
  | Node of tree * tree

(* ici on définit une fonction de parcours de l'arbre
 * traditionnellement appelée fold : elle prend deux 
 * fonctions f et g comme paramètres et remplace les
 * constructeurs du type par l'application d'une de ces
 * deux fonctions en parcourant récursivement l'arbre
 * de la racine jusqu'aux feuilles *)
let rec fold f g = function
  (* si on a une feuille, on applique la fonction f *)
  | Leaf n -> f n
  (* si on a un nœud, on applique recursivement fold sur
   * chaque sous-arbre, puis la fonction g aux résultats *)
  | Node (left, right) -> g (fold f g left) (fold f g right)

(* maintenant on va appliquer cette fonction générique
 * de parcours pour obtenir différentes interprétations *)

(* interprétation en tant qu'addition 
 * chaque feuille renvoie sa valeur et sur
 * un nœud on additionne les deux sous-arbres*)
let plus = fold (fun i -> i) ( + )

(* interprétation en tant que soustraction *)
let moins = fold (fun i -> i) ( - )

(* ici on calcule la profondeur de l'arbre 
 * une feuille est de profondeur nulle et par définition
 * la profondeur d'un arbre vaut la plus grande des profondeurs
 * de ses sous-arbres augmentée d'une unité *)
let depth = fold (fun i -> 0) (fun d d' -> 1 + max d d')

(* ici on définit différentes fonctions de pretty printing pour nos arbres *)
let show = fold string_of_int (fun s s' -> Printf.sprintf "(op %s %s)" s s')
let show_p = fold string_of_int (fun s s' -> Printf.sprintf "(%s + %s)" s s')
let show_m = fold string_of_int (fun s s' -> Printf.sprintf "(%s - %s)" s s');;

(* le compilateur détermine automatiquement le type de tous
 * les termes bien que l'on n'ait rien précisé *)
type tree = Leaf of int | Node of tree * tree
val fold : (int -> 'a) -> ('a -> 'a -> 'a) -> tree -> 'a = <fun>
val plus : tree -> int = <fun>
val moins : tree -> int = <fun>
val depth : tree -> int = <fun>
val show : tree -> string = <fun>
val show_p : tree -> string = <fun>
val show_m : tree -> string = <fun>

(* exemple d'utilisation *)
(* on définit un arbre *)
let x = Node (Leaf 1, Node (Leaf 2, Leaf 3));;
val x : tree = Node (Leaf 1, Node (Leaf 2, Leaf 3)) 

(* on l'affiche plus joliment *)
show x;;
- : string = "(op 1 (op 2 3))"

(* on voit l'opérateur op comme une addition *)
show_p x, plus x;;
- : string * int = ("(1 + (2 + 3))", 6)

(* la même avec la soustraction *)
show_m x, moins x;;
- : string * int = ("(1 - (2 - 3))", 2)

(* on calcule enfin sa profondeur *)
depth x;;
- : int = 2

Pour mieux se rendre compte de la concision du code, regardons ce que cela donne si l'on ne garde que l'essentiel en retirant les commentaires :

type tree = Leaf of int | Node of tree * tree

let rec fold f g = function
  | Leaf n -> f n
  | Node (left, right) -> g (fold f g left) (fold f g right)

let plus = fold (fun i -> i) ( + )
let moins = fold (fun i -> i) ( - )
let depth = fold (fun i -> 0) (fun d d' -> 1 + max d d')
let show = fold string_of_int (fun s s' -> Printf.sprintf "(op %s %s)" s s')
let show_p = fold string_of_int (fun s s' -> Printf.sprintf "(%s + %s)" s s')
let show_m = fold string_of_int (fun s s' -> Printf.sprintf "(%s - %s)" s s')

Et voilà ! :-)

Un adverbe, c'est quoi au fait ?

Sur ce dernier exemple, je vais essayer d'illustrer ce propos : « une fois que vous commencerez à maîtriser la programmation fonctionnelle en OCaml, nous sommes certains que vous ne regarderez plus les autres langages de la même façon »; mais en ne l'illustrant pas vis-à-vis d'un autre langage de programmation, mais par rapport à une langue vernaculaire : le français. :-)

Ce dernier exemple est un peu plus évolué que les précédents, et s'il ne vous paraît pas clair dès aujourd'hui, cela devrait l'être à l'issue de la formation.

Pour ce faire, je vais partir d'un motif fréquent en programmation impérative : la boucle for, afin d'implémenter un code qui doit effectuer cette tâche : « écrire 5 fois "coin< coin<" » et arriver au code OCaml suivant ecrire (5 |> fois) "coin< coin<".

(* la solution standard à la mode impératif *)
for i = 1 to 5 do print_endline "coin< coin<" done;;
coin< coin<
coin< coin<
coin< coin<
coin< coin<
coin< coin<
- : unit = ()

Mais on pourrait vouloir un code plus général au cas où l'on veuille effectuer la boucle plus de 5 fois. Dans ce cas, on crée une fonction qui prend en paramètre un entier qui déterminera le nombre de fois où l'on fait la boucle.

let repete_coin_coin n =
  for i = 1 to n do print_endline "coin< coin<" done;;
(* le compilateur infère toujours seul le type de la fonction *)
val repete_coin_coin : int -> unit = <fun>

repete_coin_coin 5;;
coin< coin<
coin< coin<
coin< coin<
coin< coin<
coin< coin<
- : unit = ()

Voilà qui est bien, mais on peut encore essayer de généraliser ce bout de code. Ici l'action à effectuer dans la boucle est constante dans le corps de la fonction, on pourrait en faire un paramètre. La forme générale du corps de la boucle c'est : une fonction (dans notre cas print_endline) appliquée à son paramètre (ici "coin< coin<"). Ce qui donne :

let fois n f x =
  for i = 1 to n do f x done;;
(* inférence du type général de la fonction par le compilateur *)
val fois : int -> ('a -> 'b) -> 'a -> unit = <fun>

fois 5 print_endline "coin< coin<";;
coin< coin<
coin< coin<
coin< coin<
coin< coin<
coin< coin<

Revenons un instant à notre énoncé de départ en français : « écrire 5 fois "coin< coin<" ». Ici ce que l'on doit réitérer 5 fois, c'est « écrire "coin< coin<" ». En grammaire française, un verbe comme « écrire » qui attend un complément pour signifier son action est appelé un verbe transitif. Dans notre code c'est la fonction f qui joue le rôle du verbe, et le compilateur nous dit que son type général est 'a -> 'b, autrement dit une fonction qui attend un paramètre de type quelconque 'a (son complément) pour retourner un objet d'un type quelconque 'b (le produit de l'action). Qu'à cela ne tienne, écrivons tout cela en OCaml !

(* on définit le type général d'un verbe transitif *)
type ('a, 'b) verbe = 'a -> 'b

(* ici je vais rajouter des annotations de types sur les
 * paramètres pour bien montrer l'analogie avec le français *)
let fois n (verbe:('a, 'b) verbe) (cod:'a) =
  for i = 1 to n do verbe cod done;;
val fois : int -> ('a, 'b) verbe -> 'a -> unit = <fun>

(* l'usage reste le même qu'avant *)
fois 5 print_endline "coin< coin<";;
coin< coin<
coin< coin<
coin< coin<
coin< coin<
coin< coin<

Maintenant dans la phrase en français les mots « 5 fois » correspondent à ce que l'on appelle un groupe adverbial. Et si l'on regarde le type général de la fonction fois (que l'on a écrit pour reproduire ce groupe adverbial du français) tel qu'inféré par le compilateur on a : int -> ('a, 'b) verbe -> 'a -> unit. Or si l'on regarde la fin de ce type : 'a -> unit on retrouve la forme d'un verbe transitif dont le COD est de type 'a et dont le produit de l'action est de type unit (c'est l'équivalent du type void dans des langages comme le C). Ainsi, au fond notre fonction fois prend un entier int, un verbe ('a, 'b) verbe et renvoie un autre verbe 'a -> unit = ('a, unit) verbe. Autrement dit le groupe adverbial « 5 fois » (ou fois 5 en OCaml) prend un verbe et renvoie un verbe (en changeant éventuellement le type du produit de l'action). Essayons d'exprimer cela en OCaml :

(* le type des verbes transitifs *)
('a, 'b) verbe = 'a -> 'b 

(* celui des adverbes qui peuvent changer le type du résultat de l'action *)
type ('a, 'b, 'c) adverbe = ('a, 'b) verbe -> ('a, 'c) verbe

(* on réécrit toujours le même code avec quelques annotations
 * pour mettre en avant le lien avec la grammaire du français *)
let fois n:('a,'b,unit) adverbe =
  fun (verbe:('a, 'b) verbe) (cod:'a) -> 
    for i = 1 to n do verbe cod done;;
val fois : int -> ('a, 'b, unit) adverbe = <fun>

(* et maintenant on définit une fonction écrire qui prendra comme
 * paramètres un adverbe et un texte à afficher sur la sortie standard *)
let ecrire (adv:('a,'b,'c) adverbe):('string, 'c) verbe =
  fun texte -> adv print_endline texte;;
val ecrire : (string, unit, 'c) adverbe -> (string, 'c) verbe = <fun>

(* on retrouve presque la morphologie du français *)
ecrire (fois 5) "coin< coin<";;
coin< coin<
coin< coin<
coin< coin<
coin< coin<
coin< coin<

(* pour coller encore plus au français on peut utiliser 
 * l'opérateur infixe |> qui est l'équivalent du pipe du
 * shell pour placer le paramètre avant la fonction *)
ecrire (5 |> fois) "coin< coin<";;
coin< coin<
coin< coin<
coin< coin<
coin< coin<
coin< coin<

Pour ceux qui m'ont suivi jusqu'au bout, afin de montrer toujours la concision du code OCaml, le résumé de tout ce qui précède tient en quelques lignes :

let fois n verbe cod =
  for i = 1 to n do verbe cod done

let ecrire adv texte = adv print_endline texte

ecrire (5 |> fois) "coin< coin<";;
coin< coin<
coin< coin<
coin< coin<
coin< coin<
coin< coin<

Qui dit mieux ? \o/

Conclusion

La programmation fonctionnelle a la mauvaise réputation d'être un paradigme de programmation pour « intello ». J'espère avoir réussi à montrer à travers ces exemples qu'il n'en est rien. Au fond, la grammaire d'une langue c'est son système de typage, et quelque que soit la langue l'on ne précise jamais la nature grammaticale (le type) des mots que l'on écrit : pourquoi devrait-il en être autrement en programmation ? En OCaml, c'est pareil grâce au mécanisme d'inférence de types et cela sans sacrifier la sécurité du typage statique.

Lors de la dépêche sur l'espéranto, les locuteurs de cette langue l'ont défendue en arguant que sa grammaire était plus simple, plus facile à assimiler et que des expériences essayaient de montrer qu'elle facilitait l'apprentissage des autres langues étrangères ainsi que des mathématiques; et tout cela bien que ce soit une langue inventée par une seule personne. Je dirais que cela ne m'étonne guère, et il en est de même avec OCaml : sa grammaire est incomparablement plus simple que n'importe quelle grammaire d'un langage impératif ou orienté objet. Et, à n'en pas douter, lorsque l'on commence à la comprendre, celles des autres langages nous apparaissent sous un autre jour.

Pour ceux qui voudraient tenter l'aventure, que ce soit pour découvrir un nouveau paradigme ou un nouveau langage, il vous suffit de vous inscrire : c'est en grande partie libre, gratuit et dispensé par des enseignants de qualité. Et pour ceux qui veulent avoir un avant-goût du contenu et de l'environnement de travail, il existe une démonstration dans laquelle on peut effectuer quelques exercices issus de la première session de la formation.

Aller plus loin

  • # Correction

    Posté par  . Évalué à 3.

    Je voudrais apporter une petite modification si un modérateur veux bien la faire.

    Dans la partie sur le contenu des cours, il vaudrait mieux remplacer la phrase « Le matériel pédagogique est diffusé sous licence CC-BY-NC-ND » par « Les vidéos pédagogiques sont diffusées sous licence CC BY-NC-ND et tout le code servant à la formation (environnement de travail, moteur de correction…) sous licence LGPLv2 ou GPLv2 (celui de la première session est disponible à cette adresse) ».

    De même dans le tout dernier paragraphe de la conclusion, il faudrait remplacer « c'est libre, gratuit et dispenser par des enseignants de qualité » par « c'est en grande partie libre, gratuit et dispenser par des enseignants de qualité ».

    Ceci afin d'être plus clair vis à vis de ceux qui pourraient avoir des réticences sur le choix de la licence pour les vidéos.

    Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.

    • [^] # Re: Correction

      Posté par  (site web personnel) . Évalué à 3.

      dispenser -> dispensé

      « IRAFURORBREVISESTANIMUMREGEQUINISIPARETIMPERAT » — Odes — Horace

    • [^] # Re: Correction

      Posté par  . Évalué à 2. Dernière modification le 16 septembre 2016 à 08:56.

      À la lecture du commentaire de benja et de sa note actuelle (+3), je me rends compte que j'aurais du ajouter une note d'avertissement en préambule du corps de la dépêche. Je ne suis lié en aucune façon à l'équipe pédagogique qui est à l'origine de la formation et si dans sa description revient souvent le pronom « nous » c'est parce que j'ai traduit la notice de présentation que l'équipe avait proposée dans son mail d'annonce sur la mailing list. En revanche les exemples de code à la fin son mon œuvre propre et s'ils sont jugés défectueux, mal adaptés ou peu pédagogiques, je ne souhaiterais pas que cela puisse nuire en quelconque façon à la formation, ou soit pris comme représentant la qualité pédagogique des formateurs. En conséquence, il pourrait être bon de rajouter cette notice entre le sommaire et la première partie :

      Note de l'auteur :

      Je ne suis nullement affilié ou lié en quelque façon aux personnes et à l'équipe pédagogique qui sont à l'origine de la formation. Les parties sur la description et le contenu de celle-ci, ainsi que celle sur la présentation de l'équipe, sont mes traductions de matériaux que l'on trouve dans leur courrier d'annonce sur la mailing list ou sur la page d'inscription.

      En revanche, les exemples de code en OCaml à la fin de la dépêche sont de moi et relèvent d'un choix personnel pour illustrer le langage. Au cas où ceux-ci seraient jugés confus ou peu pédagogiques, il ne faudrait pas que ces défauts soient considérés comme relevant de l'équipe pédagogique de la formation, mais devrait plutôt être mis au compte de ma seule responsabilité. Au demeurant, je suis conscient de n'être ni fin pédagogue, ni bon didacticien.

      Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.

  • # Exemple judicieux ?

    Posté par  . Évalué à 4. Dernière modification le 15 septembre 2016 à 22:16.

    J'approuve totalement la volonté de vouloir faire connaître ce merveilleux langage qu'est Ocaml, cependant laissez moi poser quelques réserves quant à la pertinence pédagogique de vos exemples, qui sont tirés, si je me souviens bien, d'une discussion à propos des fonctionnalités syntaxiques de c++ (ce qui, convenons-en n'est certainement pas un excellent prémisse ;-) ).

    Premièrement il me semble qu'il aurait été judicieux d'aborder la notion de curry-ing et d'application partielle. L'application partielle est ce qui fait que la fonction f : a -> b -> c (le : veut dire "a pour type", _ -> _ "est une fonction de _ vers _" et a,b,c sont des types), lorsqu'elle est appliqué à un l'argument x : a est une fonction qui a le type b -> c. Soit une fonction a n argument lorsqu'elle est appliqué à m < n arguments est une fonction à n-m arguments. NB: l'évaluation de l'expression finale a lieu lorsque l'application est complète.

    En ocaml on écrit let f : a -> b -> c = fun a b -> (expr : c) in let f' : b -> c = f (a_expr : a) ou bien sans les annotations de types, qui sont généralement pas nécessaires, let f a b = c_expr in let f' = f a_exp ou a_expr et c_expr sont des expressions de type a ou c. Et ça c'est ce qu'on appelle le currying, c'est à dire de pouvoir associer à une variable une fonction partiellement appliquée. Un exercice pédagogique serait pour un lecteur curieux de copier coller vos exemples de manière partielle afin d'essayer de déduire à priori le type de l'expression résultante.

    Deuxièmement, j'en avais déjà fait la remarque précédemment, mais selon moi ce genre de code a peu de sens:

    let ecrire (adv:('a,'b,'c) adverbe):('string, 'c) verbe =
      fun texte -> adv print_endline texte;;
    

    Dans votre exemple, et contrairement au normes du français que vous tentez de singer, écrire n'est ni un verbe (selon votre définition un verbe est une fonction a un argument), ni un adverbe, mais une fonction qui lorsqu'elle est appliqué à un adverbe et à un verbe donne un autre verbe. Ce qui est, vous en conviendrez je l'espère, un peu déroutant. Votre "écrire" est une sorte de méta-verbe qui se conjugue lui-même pour donner un autre verbe à l'infinitif. Je trouve que pour un document à vocation pédagogique c'est un peu tordu.

    Déjà je suggère de substituer vos alias de type adv et verbe afin de retrouver le type "non-obfusqué".
    En subsituant adv par sa définition ('a, 'b) verbe -> ('a, 'c) verbe, on obtient

    ecrire : (('a, 'b) verbe) -> ('a, 'c) verbe) -> (string, 'c) verbe

    Puis on substitue verbe ('a, 'b) verbe = 'a -> 'b:

    ecrire: (('a -> b) -> ('a -> 'c)) -> string -> 'c

    On obtient un type qui est inutilement compliqué.

    Selon moi votre verbe c'est "écrire", c'est à dire print_endline (string -> unit), votre adverbe c'est "5 fois" qui a comme signature ('a -> unit) -> int -> ('a -> unit) ou encore int -> (a' -> unit) -> ('a -> unit) pour changer l'ordre des paramètres.

    Cela tient en 3 lignes…

    let verbe = print_endline in
    let rec fois n f x= match n with _ when m <= 0 -> () | n -> f x; fois (n-1) f x
    in (5 |> fois) print_endline "abc"
    • [^] # Re: Exemple judicieux ?

      Posté par  . Évalué à 2. Dernière modification le 15 septembre 2016 à 22:44.

      Cela tient en 3 lignes…

      Le lecteur attentif aura sûrement corrigé, la première ligne est inutile car la variable verbe n'est pas utilisée (et comme print_endline tout seul n'est pas une application, il ne peut y avoir d'effet de bord). Le compilateur émettra probablement un warning. Si on désire vraiment indiquer au relecteur que print_endline est un verbe, dans ce cas effectivement une annotation explicite de type peut-être utilisée; là où un commentaire ferait tout aussi bien l'affaire ;-)

      type ('a,'b) verbe = 'a -> 'b ;;
      let rec fois n f x= match n with _ when n <= 0 -> () | n -> f x; fois (n-1) f x
      in (5 |> fois) (print_endline : _ verbe) "abc"
    • [^] # Re: Exemple judicieux ?

      Posté par  . Évalué à 0.

      Bon je vais encore passer pour un gricheux en disant que le fold de votre exemple est un peu bizard car il n'a rien d'un fold (aka reduce dans d'autre parlances). Il devrait avoir comme signature ; 'a coll -> 'b -> ('b -> 'a -> 'b) -> 'b. 'b est le type de la valeur initiale (qui devrait être la chaîne vide dans votre cas) et est aussi le type du résultat (une chaîne). Bref Je suis d'avis que lorsque l'on réutilise des noms de concepts qui ont une définition bien établie, autant utiliser le concept ou adopter une autre terminologie. Et ce d'autant plus pour un document pédagogique !

      Autre détail: il me semble que vos définitons des fonctions show_xx souffrent d'un "do not repeat yourself". C'est un peu dommage de présenter un language fonctionnel (i.e. ou le calcul in fine est basé sur la composition de fonction) et de rater une si belle occasion de montrer un code qui pourrait être encore plus élégant. 'fin bon, les couleuvres toussa

      • [^] # Re: Exemple judicieux ?

        Posté par  . Évalué à 2.

        'a coll -> 'b -> ('b -> 'a -> 'b) -> 'b

        C'est la signature pour une collection séquentielle, cela veut dire que les opérations sont faites de proche en proche en suivant un parcours particulier de la structure (par exemple un parcours en profondeur dans un arbre). Ce n'est généralement pas la chose la plus intuitive pour une structure d'arbre.

        La fonction fold qui est définie dans le journal est bel et bien ce que l'on désire, c'est à dire un catamorphisme.

        • [^] # Re: Exemple judicieux ?

          Posté par  . Évalué à 1.

          Alors il suffirait de l'appeler "catamorphism" si c'est ce que l'on veut, non ? Que ce soit librairie standard d'Ocaml, ocamlgraph ou clojure, tous utilisent la même convention pour la fonction fold, qui est celle que j'ai montrée. Je ne comprends pas ce que vous voulez dire en parlant de l'ordre de parcourt.

          • [^] # Re: Exemple judicieux ?

            Posté par  . Évalué à 1.

            edit: en parlant de clojure, et après vérification, son fold serait un combine+reduce, il n'est pas clair que celà soit un catamorphism au sens dont vous l'entendez (dans certaines conditions, j'imagine que cela pourrait-être). Par contre son reduce a bien la même signature que le fold d'ocaml usuel (ce que j'avais par ailleurs déjà mentionné dans mon commentaire initial). Alors peut-être que le fold d'ocaml est mal nommé, néanmoins il me semble logique de garder la même nomenclature lorsqu'on travaille au sein d'un même langage.

          • [^] # Re: Exemple judicieux ?

            Posté par  . Évalué à 1.

            Dans toutes la littérature que j'ai pu lire, j'ai toujours rencontré l'usage de l'appellation générique fold. Alors je l'ai reprise.

            Déjà, dans la bibliothèque standard OCaml, dans le module List on en trouve au moins deux exemplaires :

            List.fold_left;;
            - : ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a = <fun>
            
            List.fold_right;;
            - : ('a -> 'b -> 'b) -> 'a list -> 'b -> 'b = <fun>

            Peut être que cela te donnera une idée de ce que l'on entend par ordre de parcours : de gauche à droite, ou de droite à gauche dans le cas des listes avec les fonctions au-dessus.

            Pour les arbres binaires, la fonction que j'ai codé est un parcours en profondeur qui commence par explorer le sous-arbre gauche.

            Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.

            • [^] # Re: Exemple judicieux ?

              Posté par  . Évalué à -1. Dernière modification le 16 septembre 2016 à 20:58.

              Ce que je veux dire c'est votre "fold" n'utilise pas d'initialisateur/accumulateur, ce n'est pas un fold/reduce à proprement parlé comme on est habitué avec Ocaml. (Peu importe si le concept mathématique que vous utilisez s'appelle fold ou pas ça n'est pas mon propos). Donc je suggère simplement d'utiliser un autre nom pour ne pas dérouter le novice.

              (NB: la signature exacte (i.e. l'odre des arguments) a peu d'importance pour illustre mon propos, ce n'est qu'un détail d'implémentation c'est pourquoi il ne faut pas trop s'attacher à la signature que j'ai donné, les deux version List.fold_left/righ ou encore celle de ocamlgraph qui sont toutes différence mais néanmoins "équivalentes" en ce sens qu'elle demandent toutes un initialisateur ce qui permet éventuellement d'enchaîner plusieurs folds à la suite sans trop de difficulté).

              Quant à l'ordre de visite je ne comprends toujours pas le rapport que ça a avec cette discussion de savoir s'il est pertinent d'appeller quelque chose fold alors que ça n'en est pas vraiment un au sens ocaml (oulla je prends des pincettes cette fois :p). Désolé d'avoir été peu clair, je comprends bien l'importance de connaître l'odre d'évaluation et c'est effectivement mieux de le spécifier dans le nom de la fonction directement. Mais bon je ne sais pas lire dans les pensées d'Aluminium95 donc bon je crois que l'on va en rester là ;-)

              • [^] # Re: Exemple judicieux ?

                Posté par  . Évalué à 0. Dernière modification le 16 septembre 2016 à 21:05.

                NB du NB: Aussi on ne peut pas inférer l'ordre de parcourt de par la signature… C'est pourquoi je n'ai vraiment rien compris au commentaire d'Aluminum95.

                • [^] # Re: Exemple judicieux ?

                  Posté par  . Évalué à 2.

                  En effet je n'ai pas été très clair.

                  Pour revenir sur le sujet du fold (avant de parler de ce que j'ai voulu dire en parlant d'ordre) voilà pourquoi il est naturel de dire que la fonction proposée dans le journal est un fold. Alors, pour cela il faut savoir ce qu'on entend par fold. C'est là que la divergence d'opinion provient : tu veux que ce soit une fonction qui ait une signature plus ou moins proche de celle sur des collections de même nature que les listes (tableaux, etc …), tandis qu'on peut interpréter cette signature comme une spécification d'un concept plus général.

                  Très rapidement, je vais expliquer d'où provient cette spécialisation. Passer ce paragraphe si c'est déjà connu.
                  Je vais généraliser d'une manière grossière (on peut faire mieux) mais les types en ocaml (somme et produits) permettent de construire une algèbre de termes. La construction est très simple, c'est construire le type des arbres avec pour noeuds les constructeurs (et le nombre de fils correspondants à constructeur). Cette construction généralise clairement celle des listes.
                  Si on se demande maintenant d'où vient le fold, on comprend que c'est une fonction d'évaluation sur les listes, qui part d'une graine et qui accumule un résultat. Une manière totalement générale de faire ceci sur des termes arbitraires c'est de mettre des graines sur les feuilles, et faire remonter les valeurs en les combinant en fonction des noeuds.
                  Comme pour la liste les noeuds sont toujours de type concaténation, il suffit de donner une unique fonction de combinaison de valeurs, et comme il y a une seule fin de liste (la liste vide) il suffit de donner une valeur comme graine.

                  Il y a donc de très bonnes raisons pour dire que ces deux choses sont similaires, au point qu'on puisse les nommer de manière identique (comme une grosse fonction fold polymorphique qui déciderait en fonction de la structure comment agir).

                  Pour revenir sur la notion d'ordre, c'était simplement pour dire que si tu veux utiliser la « vraie » fonction fold, elle ne peut faire des combinaisons que locales, et accumuler un résultat. Pour un arbre, il est possible d'écrire les noeuds dans une liste (par exemple avec un parcours), mais appliquer un fold séquentiel dessus semble très étrange (vu qu'il ne respectera presque aucune propriété) sauf si on sait que l'opérateur vérifie des hypothèses très fortes. Je voulais simplement dire que pour un arbre, l'opération « importante » c'est de faire des branchements, et donc proposer une fonction « linéaire » de réduction c'est très souvent impossible.

            • [^] # Re: Exemple judicieux ?

              Posté par  . Évalué à -1.

              Alors je l'ai reprise.

              Version courte: votre "fold" ne fait pas la même chose. C'est comme si un itérateur s'appelait map, ou encore un Queue.pop s'appellant Queue.empty, etc.

              • [^] # Re: Exemple judicieux ?

                Posté par  . Évalué à 2.

                Version courte: votre "fold" ne fait pas la même chose

                C'est là qu'est l'erreur, cette fonction fait exactement la même chose !

                Que fait un fold sur une liste ?

                1. Il commence avec une graine : le paramètre f dans le code du journal
                2. Il accumule des valeurs : le paramètre g dans le code du journal

                Une preuve possible que c'est bien la même chose, nous allons montrer que si f et e sont respectivement une fonction d'accumulation et une graine, alors on peut trouver f' et g' deux fonctions (arguments du fold du journal) telles que quelque soit la liste l :

                fold f e l = fold f' g' (encode_en_arbre l) 
                

                J'ai commencé une preuve sur la structure du journal, mais celle-ci possède de nombreux défauts

                1. Les arbres ne contiennent que des entiers
                2. Il n'y a pas d'arbre vide

                Le deuxième point ne permet pas d'encoder la liste vide, le premier est plus embêtant parce qu'il ne permet pas de retrouver où commence la liste dans l'encodage (tous les noeuds sont identiques).

                • [^] # Re: Exemple judicieux ?

                  Posté par  . Évalué à 1. Dernière modification le 16 septembre 2016 à 23:38.

                  Vous montrez que fold avec une fonction d'accumulation et une graine et le fold avec fonctions f et g sont équivalent car il existe une fonction f et g pour n'importe quelle paire d'une fonction d'accumulation avec une graine. Et réciproquement. OK soit je peux convevoir que vous ayez raison. Mais mon propos n'est pas là.

                  Mon propos est qu'il est d'usage d'appeler la première version fold. Si j'avais l'habitude de sommer les feuilles de mon arbres avec fold (+) zero tree vous me demandez maintenant de l'écrire zero + (fold (+) (fun x -> x) tree). Alors ok ça fait la même chose mais en l'utilisant différemment. Je dis simplement que je trouves cela perturbant…

                  • [^] # Re: Exemple judicieux ?

                    Posté par  . Évalué à 1. Dernière modification le 16 septembre 2016 à 23:58.

                    Mon propos est qu'il est d'usage d'appeler la première version fold. Si j'avais l'habitude de sommer les feuilles de mon arbres avec fold (+) zero tree vous me demandez maintenant de l'écrire zero + (fold (+) (fun x -> x) tree). Alors ok ça fait la même chose mais en l'utilisant différemment. Je dis simplement que je trouves cela perturbant…

                    Non, tu n'a toujours pas compris. Il n'y a pas de zero dans le cas des arbres ! C'est la fonction f qui joue le rôle de cette constante que l'on fournit dans le cas des fold sur les listes : c'est bien plus fonctionnel que ce à quoi tu veux réduire le fold. Tu cherches à le réduire au cas où la graine est une constante, et on te dit que comme on est dans un langage fonctionnel cela peut aussi être une fonction. C'est pour cela que c'est une généralisation du cas sur les listes.

                    Une liste à pour type : type 'a list = Nil | Cons of 'a * 'a list, ce sont des listes chaînées. Quand on parcourt une liste on termine toujours sur Nil et c'est la qu'on utilise la graine. Dans un langage impératif ce serait la gestion du cas où l'on tombe sur un pointeur null. Dans le cas des arbres, en bout de parcours on tombe sur une feuille qui contient un int et alors on applique une fonction. Le principe est identique mais généralisé.

                    Comme te l'as dit Aluminium95 :

                    Que fait un fold sur une liste ?

                    • Il commence avec une graine : le paramètre f dans le code du journal
                    • Il accumule des valeurs : le paramètre g dans le code du journal

                    Il n'y a que toi que cela perturbe, tu es la première personne que je rencontre qui voit là un problème.

                    Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.

                    • [^] # Re: Exemple judicieux ?

                      Posté par  . Évalué à 1.

                      Il n'y a pas de zero dans le cas des arbres !

                      Avec votre version je suis obligé de l'écrire "valeur_de_depart + (fold f g t)" ou "fold f g (Tree(Node(valeur_de_depart),t)", je trouve ça vachement mois agréable à utiliser pour cet usage.

                      C'est la fonction f qui joue le rôle de cette constante

                      J'attends toujours la démonstration, qq chose me dit que ça n'est pas si trivial…

                      a graine est une constante

                      La graine s'appelle préférablement variable d'accumulation, et elle n'est évidemment pas constante pendant la traversée. là ou avec votre "fold", f et g sont fixes… Qui peut le plus, peut le moins ;-)

                      En étant pédant, j'ajouterais que toute valeur dans un langage fonctionnelle pur est constante.

                      et on te dit que comme on est dans un langage fonctionnel cela peut aussi être une fonction.

                      heu… je ne pensais pas donner l'impression d'avoir besoin de cette explication

                      Il n'y a que toi que cela perturbe, tu es la première personne que je rencontre qui voit là un problème.

                      Je suis désolé, appeler par le même nom deux fonctions avec des sémantiques différentes, je trouve cela perturbant. Surtout lorsqu'une des sémantiques est dans la librairie standard et reprise par d'autres librairies populaires.

                      Quand on parcourt une liste on termine toujours sur Nil

                      Faux, avec fold_right, on commence avec Nil.

                      et c'est la qu'on utilise la graine.

                      Encore faux. Cf. fold_left.

                      Désolé, mais je faisais juste une remarque pour essayer de rendre votre prochain exposé plus pédagogique. Je n'ai pas besoin que l'on m'explique ce que j'aurais mal compris alors que j'exprime juste un fait: l'usage en ocaml est de nommer le reduce "fold", et pas votre catamorphisme.

                      • [^] # Re: Exemple judicieux ?

                        Posté par  . Évalué à 1. Dernière modification le 17 septembre 2016 à 01:09.

                        Faux, avec fold_right, on commence avec Nil.

                        Correction: techniquement ce que vous dites est correct, simplement on commence l'évaluation une fois que l'on a atteint Nil.

                      • [^] # Re: Exemple judicieux ?

                        Posté par  . Évalué à 1.

                        l'usage en ocaml est de nommer le reduce "fold", et pas votre catamorphisme

                        Et c'est ce que fait notre fonction fold : un reduce via la fonction g. Ce qu'il y a c'est que dans une liste, ou une collection séquentielle ou linéarisée, on peut attaquer la structure par deux bouts : le début ou la fin, d'où le fold_left et le fold_right.

                        Dans le cas des arbres binaires, on attaque nécessaire par la racine puis on descend dans les branches pour finir sur les bouts de la structure que sont les feuilles où l'on applique la fonction f, puis l'on réduit la structure via la fonction g. C'est bien une généralisation du cas sur les listes dont le nom technique général est catamorphisme. Voilà une série d'articles en F# sur le sujet, le premier commence par les listes :

                        La différence est seulement dans le fait que l'on ne réduit pas une liste et un arbre de la même façon.

                        P.S : tu as raison pour le code du fold_list : si elle est vide on renvoie une exception (ou None si on veut renvoyer un type 'a option) ou alors on passe par des listes qui ne peuvent être vides comme type 'a coll = End of 'a | Cons of 'a * 'a coll — les arbres étant garantis d'être non vides par construction.

                        Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.

                      • [^] # Re: Exemple judicieux ?

                        Posté par  . Évalué à 3.

                        Pour le voir encore autrement, je vais représenter les arbres d'évaluations des fold sur une liste.

                        let l = [1; 2; 3]
                        
                        List.fold_left (+) 0 l;;
                        - : int = 6 (* ((0 + 1) + 2) + 3 *)
                        
                        List.fold_right (+) l 0;;
                        - : int = 6 (* 1 + (2 + (3 + 0))) *)

                        Dans le premier cas, on évalue ainsi :

                              +
                             / \
                            +   3
                           / \
                          +   2
                         / \
                        0   1
                        

                        Dans le second, on évalue comme ceci :

                          +
                         / \
                        1   +
                           / \
                          2   +
                             / \
                            3   0
                        

                        À comparer aux arbres que j'ai dessiné en réponse à Pierre-Matthieu Anglade.

                        Avec des listes on construit toujours des arbres en peigne soit vers la gauche, soit vers la droite. Mais un arbre pourrait avoir une toute autre structure comme celui-là :

                           / \ 
                          /   \
                         /\   /\
                        1  2 3  0
                        

                        Et si tu fais un fold (fun i -> i) (+) sur lui, c'est évaluer l'expression (1 + 2) + (3 + 0)

                        Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.

                  • [^] # Re: Exemple judicieux ?

                    Posté par  . Évalué à 2.

                    Pour que ce soit peut être plus clair, je mets le code dans le cas de listes et dans celui des arbres binaires. Essayes de voir en quoi il se ressemble dans la forme.

                    type 'a list = Nil | Cons of 'a * 'a list
                    type 'a tree = Leaf of 'a | Node of 'a tree * 'a tree
                    
                    let rec fold_list f g = function
                      | Nil -> f
                      | Cons (x, xs) -> g x (fold_list f g xs);;
                    val fold_list : 'a -> ('b -> 'a -> 'a) -> 'b list -> 'a = <fun>
                    
                    let rec fold_tree f g = function
                      | Leaf i -> f i
                      | Node (l, r) -> g (fold_tree f g l) (fold_tree f g r);;
                    val fold_tree : ('a -> 'b) -> ('b -> 'b -> 'b) -> 'a tree -> 'b = <fun>

                    Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.

                    • [^] # Re: Exemple judicieux ?

                      Posté par  . Évalué à 1. Dernière modification le 17 septembre 2016 à 01:03.

                      Moi j'aurais écrit votre version list comme ceci… Enfin peu importe je crois que je n'apporterai plus rien à cette discussion qui tourne en queue de boudin.

                      let rec je_ne_suis_pas_fold f g = function
                      | Nil -> raise (Invalid_argument "pas de graine...")
                      | Cons (x, Nil) -> (f x)
                      | Cons (hd, tl) -> g (f hd) (je_ne_suis_pas_fold f g tl)
                      • [^] # Re: Exemple judicieux ?

                        Posté par  . Évalué à 1. Dernière modification le 17 septembre 2016 à 01:20.

                        (Mieux serait d'avoir type 'a liste_non_vide = End of 'a | Cons of 'a * 'a liste_non_vide)

                      • [^] # Re: Exemple judicieux ?

                        Posté par  . Évalué à 1.

                        Il est vrai que j'ai mal présenté la chose. Disons que par rapport à une liste, il n'y a pas besoin de valeur initiale car l'arbre contient déjà tout ce qui lui faut pour faire un reduce via la fonction g. Et le fold que j'ai écrit est une généralisation d'un map+reduce.

                        let fold_map f g init = function
                          | [] -> failwith "empty list"
                          | x::xs -> 
                             let rec loop acc = function
                              | [] -> acc
                              | hd::tl -> loop (g acc (f hd)) tl
                             in loop (g init (f x)) xs
                        ;;
                        val fold_map : ('a -> 'b) -> ('c -> 'b -> 'c) -> 'c -> 'a list -> 'c = <fun>
                        
                        fold_map (string_of_int) (fun s s' -> Printf.sprintf "(%s + %s)" s s') "1" [2; 3];;
                        - : string = "((1 + 2) + 3)"
                        
                        (* à comparer avec cette version sur les arbres *)
                        
                        let t = Node (Node (Leaf 1, Leaf 2), Leaf 3) in show_p t;;
                        - : string = "((1 + 2) + 3)"

                        Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.

    • [^] # Re: Exemple judicieux ?

      Posté par  (site web personnel) . Évalué à 3.

      Personnellement, c'est l'exemple de l'arbre qui me chagrine. Contrairement aux spécialistes qui vous titilleront sur des subtilités, en tant que néophyte, j'ai du mal à suivre les tenants et aboutissants de cet exemple. Et du coup, impossible (ou délicat) de le comprendre et d'en tirer quoi que ce soit ; contrairement aux deux autres exemples, eux très simples et bien expliqués qui permettent de s'intéresser au cœur du sujet.

      « IRAFURORBREVISESTANIMUMREGEQUINISIPARETIMPERAT » — Odes — Horace

      • [^] # Re: Exemple judicieux ?

        Posté par  (site web personnel) . Évalué à 2.

        Le parcours d'arbre semble inutilement complexe, mais dans n'importe quel logiciel, tu as une structure de donnée centrale qui peut être vu comme un arbre. Ce genre de parcours d'arbre est bien plus puissant, souple et sécurisé que n'importe qu'elle autre façon de faire (typiquement un graph d'objet).

        "La première sécurité est la liberté"

      • [^] # Re: Exemple judicieux ?

        Posté par  . Évalué à 1.

        Qu'est-ce que tu ne comprends pas dans cet exemple ?

        Je vais essayer de l'expliquer avec un dessin sur l'exemple de l'arbre binaire que j'ai utilisé. Si on le représente graphiquement l'arbre ressemble à cela :

          /\
         /  \
        1   /\
           2  3
        

        L'idée de la fonction fold est d'appliquer une fonction f sur les feuilles et une fonction g sur les nœuds. Dans le cas de l'addtion, la fonction plus, cela donnerait cet arbre :

           +
          / \
         /   \
        1     +
             / \
            2   3
        

        Ce qui est une façon de représenter sous forme d'arbre le calcul 1 + ( 2 + 3 ).

        Dans le cas général, la fonction fold, cela pourrait se représenter ainsi :

            g
           / \
          /   \
        f 1    g
              / \
           f 2   f 3
        

        Le principe te semble-t-il plus clair ainsi ?

        Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.

  • # Puisqu'on parle de grammaire ...

    Posté par  . Évalué à 3. Dernière modification le 15 septembre 2016 à 22:53.

    Je note un petit relâchement dans le dernier paragraphe:

    cette langue l'ont défendu*e* en arguant que sa grammaire ét~~é~~ait plus simple,

    (que l'on a écrit pour reproduire ce groupe adverbial du français) tel qu'infér~~er~~é par le compilateur on

    c'est libre, gratuit et dispens~~er~~é par des enseignants de qualité.

    Sinon, très alléchant programme (à double titre) !!!

    • [^] # Re: Puisqu'on parle de grammaire ...

      Posté par  . Évalué à 2. Dernière modification le 16 septembre 2016 à 09:11.

      Merci pour avoir relevé ces erreurs, c'était la fin de la dépêche mon attention s'est relâchée.

      J'avais contrôlé avec grammalecte mais il n'avait pas remarqué les erreurs. Je ne sais si le dernier exemple t'a plu, ou si tu le trouves judicieux, mais c'est un choix qui relève d'un intérêt personnel sur la question depuis bien longtemps. Le premier commentaire que j'ai posté sur linuxfr, et la raison pour laquelle je me suis inscrit ici, portait déjà là-dessus. C'était justement sur la dépêche de présentation de grammalecte dans le cadre de sa campagne de financement participatif, et déjà à l'époque, alors que d'autres commentaires soulignés la ressemblance avec le fonctionnement d'un compilateur, j'avais essayé d'expliquer à l'auteur que le problème algorithmique auquel il était confronté était de la vérification et de l'inférence de type.

      Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.

    • [^] # Re: Puisqu'on parle de grammaire ...

      Posté par  (site web personnel) . Évalué à 4.

      Corrigé, merci.

      • [^] # Re: Puisqu'on parle de grammaire ...

        Posté par  . Évalué à 1.

        Merci Benoît.

        Serait-il également possible d'effectuer les modifications que j'ai proposées dans le premier fil de commentaires, à moins que l'équipe de modération ne considère que la présence de ces informations en commentaires est suffisante ?

        Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.

  • # Retour d'expérience sur la première session

    Posté par  . Évalué à 5.

    J'ai participé à la première session du MOOC et ça a vraiment été un moment d'apprentissage intense. Pour les anciens qui n'ont connu que le paradigme objet, la marche peut être assez haute et le choc intellectuel assez déstabilisant. Les temps annoncés pour le suivi sont très en dessous de ce que j'ai du y passer, mais quand on aime, on ne compte pas… Je pense même rempiler (est-ce que le contenu de cette deuxième session est totalement identique à celui de la première ?).

    Le point un peu ennuyeux reste que le cours est dispensé en anglais par des non anglophones, ce qui a tendance à le rendre plus difficile à comprendre. Mais le code parle de lui-même ;-).

    Dans tous les cas, je le conseillerais sans aucune retenue à toute personne ayant déjà un peu tâté du développement logiciel, que ce soit dans des langages impératifs conventionnels ou des langages de script dynamiques non typés.

    À la fin du MOOC, il était question de faire un second opus plus orienté sur la programmation asynchrone. A-t-on des nouvelles ?

    • [^] # Re: Retour d'expérience sur la première session

      Posté par  . Évalué à -2.

      Le point un peu ennuyeux reste que le cours est dispensé en anglais par des non anglophones, ce qui a tendance à le rendre plus difficile à comprendre. Mais le code parle de lui-même ;-).

      Quel est l'intérêt de l'anglais dans ce cas?

    • [^] # Re: Retour d'expérience sur la première session

      Posté par  . Évalué à 1. Dernière modification le 16 septembre 2016 à 14:21.

      est-ce que le contenu de cette deuxième session est totalement identique à celui de la première ?

      Je ne sais pas. J'ai relayé une information que j'ai vu passer sur le Planet OCaml, j'ai cherché un peu, mais je n'ai pas trouvé d'informations pour savoir si le contenu avait évolué par rapport à la première session. Comme tu as participé à la première et que le contenu du programme de celle-ci est connu, y vois-tu une différence ?

      Le point un peu ennuyeux reste que le cours est dispensé en anglais par des non anglophones

      Cette fois-ci les cours semblent disposer d'un sous-titrage en français. Ce n'était pas le cas à la première session ?

      En regardant la vidéo de présentation sur la page d'inscription, j'ai eu également du mal à comprendre l'anglais de Ralf Treinen avec son accent allemand.

      A-t-on des nouvelles ?

      Je n'ai rien vu passer de tel sur le Planet.

      Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.

      • [^] # Re: Retour d'expérience sur la première session

        Posté par  . Évalué à 2.

        Je ne vois aucune différence avec la première session au niveau programme.

        C'est surtout au niveau exercices que je serais intéressé, parce que c'est plutôt là que la répétition manquera d'intérêt, même si je ne me fais pas d'illusion.

        Une chose particulièrement frappante concernant les exercices, c'est qu'on utilise l'interpréteur compilé en javascript vers javascript directement dans notre navigateur web. Pas besoin d'installation (tout au moins au début) pour faire exercices, les faire tourner et les envoyer au test ! Enfin, à un moment, on préfère quand même éditer son code dans un vrai éditeur, surtout pour le projet final.

        Les sous-titrages français ont été réalisés en parallèle de leur publication, par les élèves. Rien de répréhensible. Je préfère la version originale, surtout si la présentation contient déjà beaucoup de texte qu'il faut lire aussi.

        Pour la suite, j'imagine qu'il ne doit pas être simple de monter MOOC.

        Di Cosmo annonce dans sa lettre qu'il y a déjà 1600 inscrits. Pas mal !

        • [^] # Re: Retour d'expérience sur la première session

          Posté par  . Évalué à 2.

          Enfin, à un moment, on préfère quand même éditer son code dans un vrai éditeur, surtout pour le projet final.

          Justement à ce sujet, pourrais-tu nous dire en quoi consiste précisément ce projet final ?

          Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.

          • [^] # Re: Retour d'expérience sur la première session

            Posté par  . Évalué à 2.

            Tu veux prendre de l'avance :-p ?

            Je ne pense pas dévoiler beaucoup en disant que l'un tourne autour des chaînes de Markov et que l'autre propose de chercher la solution à un jeu de combinaisons.

            Ce sont des problèmes suffisamment généraux et contenus pour que le développement de la solution ne nécessite pas d'apprentissage d'API.

            • [^] # Re: Retour d'expérience sur la première session

              Posté par  . Évalué à 2.

              Tu veux prendre de l'avance :-p ?

              Oh non, je ne pense pas m'inscrire à la formation, je n'ai pas besoin d'être initié à la programmation fonctionnelle. ;-)

              Mon premier projet en OCaml (et mon seul d'ailleurs, je ne suis pas développeur) consistait à implémenter un EDSL d'arithmétique transfinie, et ma machine était sous Windows 98. Même si je ne programme plus, ou peu, cela m'a permis de comprendre véritablement le problème de l'arrêt et pourquoi l'hypothèse du continu de Cantor était indécidable.

              Je suis dans une position inverse de la tienne, en tant que mathématicien c'est plutôt les paradigmes impératif et orienté objet qui me semble difficile à comprendre par moment. Quand je lis du code dans ces paradigmes, j'ai souvent l'impression de tomber sur la comptine des neufs divisions

              Division par 1 :

              • Pas besoin de diviser. (1 étant le nombre élémentaire, la division n’est pas nécessaire). La méthode n’est pas définie.

              Division par 2 :

              • 2, 1, augmente-le pour obtenir 5.
              • Si tu rencontres 2, avance 10.

              Division par 3 :

              • 3, 1, 31.
              • 3, 2, 62.
              • Si tu rencontres 3, avance 10.

              Division par 4 :

              • 4, 1, 22.
              • 4, 2, augmente-le pour obtenir 5.
              • 4, 3, 72.
              • Si tu rencontres 4, avance 10.

              Division par 5 :

              • 5, 1, double-le pour obtenir 2.
              • 5, 2, double-le pour obtenir 4.
              • 5, 3, double-le pour obtenir 6.
              • 5, 4, double-le pour obtenir 8.
              • Si tu rencontres 5, avance 10.

              Division par 6 :

              • 6, 1, ajoute 4 en dessous.
              • 6, 2, 32.
              • 6, 3, augmente-le pour obtenir 5.
              • 6, 4, 64.
              • 6, 5, 82.
              • Si tu rencontres 6, avance 10.

              Division par 7 :

              • 7, 1, ajoute 3 en dessous.
              • 7, 2, ajoute 6 en dessous.
              • 7, 3, 42.
              • 7, 4, 55.
              • 7, 5, 71.
              • 7, 6, 84.
              • Si tu rencontres 7, avance 10.

              Division par 8 :

              • 8, 1, ajoute 2 en dessous.
              • 8, 2, ajoute 4 en dessous.
              • 8, 3, ajoute 6 en dessous.
              • 8, 4, augmente-le pour obtenir 5.
              • 8, 5, 62.
              • 8, 6, 74.
              • 8, 7, 86.
              • Si tu rencontres 8, avance 10.

              Division par 9 :

              • Pour diviser par 9, suis la tige actuelle en dessous.
              • Si tu rencontres 9, avance 10.

              Celui qui comprend cela à la première lecture, et en quoi cet algorithme implémente la division en arithmétique et est correct… je lui tire mon chapeau. ;-)

              Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.

    • [^] # Re: Retour d'expérience sur la première session

      Posté par  . Évalué à 2.

      Hello, je fais partie de l'équipe pédago.

      Le contenu est quasi inchangé, il s'agit d'une deuxième session, pas d'une suite. Ceux qui ont fait l'un des deux projets au choix l'année dernière et qui veulent se réinscrire pour maintenir leurs connaissances auront cependant la possibilité de choisir l'autre cette année.

      Malheureusement, il est impossible de donner une quelconque date pour une suite. C'est effectivement beaucoup de travail que de préparer un tel MOOC !

      • [^] # Re: Retour d'expérience sur la première session

        Posté par  . Évalué à 0.

        Je m'étais déjà attaqué aux deux problèmes…

        Enfin, cette deuxième session bénéficie déjà de toutes les corrections apportées aux problèmes soulevés lors de la première.

  • # Retour d'expérience

    Posté par  (site web personnel, Mastodon) . Évalué à 3.

    Suite à ce billet, je me suis inscrit à ce MOOC OCaml 2016 qui touche à sa fin en ce qui me concerne.

    J'ai trouvé cela très intéressant (sachant que je fais de la programmation comme loisir, je ne suis pas très averti et j'ignorais tout de la programmation fonctionnelle). Donc je ne regrette pas cet effort (qui pour moi a représenté entre trois et huit heures suivant les semaines).

    Par contre, j'ai été assez frustré par le manque de retours de l'équipe pédagogique dans les forums associés. J'ai suivi d'autres MOOC sur edX ou Coursera où les échanges étaient bien plus nombreux et instructifs.

    Ils ont fait le choix de laisser les inscriptions ouvertes jusqu'à la fin de la session (ce qui est louable) et il n'y a donc pas de date limite hebdomadaire pour les exercices. La contrepartie, c'est qu'il n'y a donc pas de corrigés officiels publiés au fur et à mesure de l'avancement. Même si j'ai obtenu des scores honorables, j'aurais vraiment apprécié de voir ensuite une approche éventuellement différente et plus fonctionnnelle. En plus, ça paralyse un peu les échanges entre étudiants tant la crainte est grande de spoiler les exercices.

Suivre le flux des commentaires

Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.