{"id":108,"date":"2022-01-20T19:22:37","date_gmt":"2022-01-20T19:22:37","guid":{"rendered":"https:\/\/9h15.net\/activ\/?p=108"},"modified":"2023-01-31T11:58:50","modified_gmt":"2023-01-31T11:58:50","slug":"programmation-logique-et-fonctionnelle-partie-b","status":"publish","type":"post","link":"https:\/\/9h15.net\/activ\/programmation-logique-et-fonctionnelle-partie-b\/","title":{"rendered":"Programmation logique et fonctionnelle &#8211; partie B"},"content":{"rendered":"<p><code>Par O. Bailleux, Ma\u00eetre de conf\u00e9rences HDR \u00e0 l'universit\u00e9 de Bourgogne.<\/code><\/p>\n<h1><a id=\"le-langage-caml\" class=\"anchor\" aria-hidden=\"true\"><\/a>Le langage CAML<\/h1>\n<p>Les activit\u00e9s <strong>#.dec<\/strong> (<strong>dec<\/strong> pour D\u00e9couverte) consistent \u00e0 \u00e9tudier des <strong>pr\u00e9sentations explicatives<\/strong> et \u00e0 traiter tous les <strong>exercices de d\u00e9couverte<\/strong> propos\u00e9s. Si vous ne r\u00e9pondez pas correctement \u00e0 un exercice de d\u00e9couverte, revenez en arri\u00e8re pour relire les explications et identifier la cause de votre erreur.<\/p>\n<p>Les activit\u00e9s <strong>#.ent<\/strong> (<strong>ent<\/strong> pour Entrainement) consistent \u00e0 traiter des <strong>exercices d&rsquo;entra\u00eenement<\/strong>. Vous devez d&rsquo;abord tenter de traiter ces exercices sans d\u00e9voiler d&rsquo;indice ni regarder la solution. Vous pouvez remonter dans le document pour relire certaines explications ou consulter les solutions des exercices de d\u00e9couverte ou d&rsquo;entra\u00eenement pr\u00e9c\u00e9demment trait\u00e9s.<\/p>\n<h2>Activit\u00e9 de d\u00e9couverte B.dec<\/h2>\n<h3><a id=\"introduction\" class=\"anchor\" aria-hidden=\"true\"><\/a>Introduction<\/h3>\n<p>CAML est un langage fonctionnel qui trouve ses bases th\u00e9oriques, mais en partie aussi l&rsquo;inspiration de sa syntaxe, dans le &#40;\\lambda&#41;-calcul. Nous allons l&rsquo;aborder avec des exemples que vous \u00eates invit\u00e9s \u00e0 reproduire sur machine.<\/p>\n<p>La version la plus aboutie est OCAML. Elle permet une programmation fonctionnelle et \/ ou imp\u00e9rative et orient\u00e9e objet. Seul l&rsquo;aspect <strong>programmation fonctionnelle pure<\/strong> nous int\u00e9resse dans cet enseignement.<\/p>\n<p>Il existe des compilateurs en ligne, ainsi que des versions Linux, Windows, et MacOS disponibles sur .<\/p>\n<p>La programmation fonctionnelle diff\u00e8re de la programmation imp\u00e9rative sur deux points essentiels :<\/p>\n<ul>\n<li>Une variable repr\u00e9sente une m\u00eame valeur pendant toute sa dur\u00e9e de vie.<\/li>\n<li>En cons\u00e9quence, il n&rsquo;y a pas de boucles telles que <code>for<\/code>, <code>while<\/code>,&#8230;<\/li>\n<\/ul>\n<p>Elle s&rsquo;appuie sur la <strong>r\u00e9cursivit\u00e9<\/strong> pour r\u00e9aliser tous les calculs et traitements qui pourraient \u00eatre r\u00e9alis\u00e9s de mani\u00e8re it\u00e9rative dans les langages imp\u00e9ratifs.<\/p>\n<h3><a id=\"b-dec1-fonctions-non-r%C3%A9cursives%C3%A0-1-param%C3%A8tre\" class=\"anchor\" aria-hidden=\"true\"><\/a>B.dec1 : Fonctions non r\u00e9cursives \u00e0 1 param\u00e8tre<\/h3>\n<p>Voici un premier exemple de fonction, sp\u00e9cifi\u00e9e de deux mani\u00e8res diff\u00e9rentes.<\/p>\n<pre><code class=\"language-ocaml\">(* Version 1 *)\nlet abs = fun x -&gt;\n  if x &lt; 0 then\n    -x\n  else\n    x ;;\n<\/code><\/pre>\n<blockquote><p>Soit <code>abs<\/code> la fonction qui \u00e0 <code>x<\/code> associe <code>-x<\/code> si <code>x &lt; 0<\/code>, sinon <code>x<\/code>.<\/p><\/blockquote>\n<pre><code class=\"language-ocaml\">(* Version 2*)\nlet abs x =\n  if x &lt; 0 then\n    -x\n  else\n    x ;;\n<\/code><\/pre>\n<blockquote><p>Soit <code>abs<\/code> la fonction qui, appliqu\u00e9e \u00e0 <code>x<\/code> retourne <code>-x<\/code> si <code>x &lt; 0<\/code>, sinon <code>x<\/code>.<\/p><\/blockquote>\n<p>La premi\u00e8re formulation est directement inspir\u00e9e du &#40;\\lambda&#41;-calcul.<\/p>\n<pre><code class=\"language-ocaml\">let abs = fun x -&gt; if x &lt; 0 then -x else x ;;\n<\/code><\/pre>\n<p>&#091;\\boxed{\\text{abs}} = \\lambda x . \\boxed{\\text{terme qui sp\u00e9cifie le calcul de }|x|}<br \/>\n&#093;<\/p>\n<p>L&rsquo;utilisation de cette fonction ressemble \u00e0 une application en &#40;\\lambda&#41;-calcul :<\/p>\n<p>\u00c0 la place de&#8230;<\/p>\n<p>&#40;\\boxed{\\text{abs}} \\; \\boxed{3}&#41;<\/p>\n<p>&#8230;o\u00f9 &#40;\\boxed{\\text{abs}}&#41; est l&rsquo;abstraction sp\u00e9cifiant le calcul de la valeur absolue et &#40;\\boxed{3}&#41; le terme de &#40;\\lambda&#41;-calcul repr\u00e9sentant l&rsquo;entier 3, on \u00e9crit :<\/p>\n<pre><code class=\"language-ocaml\">abs 3;;\n<\/code><\/pre>\n<p>Et on obtient l&rsquo;affichage :<\/p>\n<pre><code class=\"language-plain_text\">int = 3\n<\/code><\/pre>\n<p>La deuxi\u00e8me formulation, plus lisible, est celle que nous utiliserons dans la suite du cours.<\/p>\n<p>Lors qu&rsquo;on saisit dans une console CAML en mode interactif :<\/p>\n<pre><code class=\"language-ocaml\">let abs x =\n  if x &lt; 0 then\n    -x\n  else\n    x ;;\n<\/code><\/pre>\n<p>Le compilateur nous r\u00e9pond :<\/p>\n<pre><code class=\"language-ocaml\">abs : int -&gt; int = &lt;fun&gt;\n<\/code><\/pre>\n<p>Cet affichage s&rsquo;interpr\u00e8te de la mani\u00e8re suivante :<\/p>\n<blockquote><p><code>abs<\/code> est une fonction qui \u00e0 tout entier (type <code>int<\/code>) associe un entier.<\/p><\/blockquote>\n<p>Pourtant, nous n&rsquo;avons pas indiqu\u00e9 de type dans la sp\u00e9cification de la fonction. CAML a <strong>inf\u00e9r\u00e9<\/strong> ce type <code>int<\/code>.<\/p>\n<p>Si on compile cette variante&#8230;<\/p>\n<pre><code class=\"language-ocaml\">let absf x =\n  if x &lt; 0. then\n    -.x\n  else\n    x ;;\n<\/code><\/pre>\n<p>&#8230;on obtient l&rsquo;affichage :<\/p>\n<pre><code class=\"language-ocaml\">val absf : float -&gt; float = &lt;fun&gt;\n<\/code><\/pre>\n<p>Les op\u00e9rations et valeurs flottantes utilisent une notation sp\u00e9cifique, comme par exemple <code>-.<\/code> pour la soustraction et la n\u00e9gation.<\/p>\n<p>Mais nous ne sommes pas au bout de nos surprises. Si on saisit&#8230;<\/p>\n<pre><code class=\"language-ocaml\">absf -.67.0;;\n<\/code><\/pre>\n<p>&#8230;on obtient un message d&rsquo;erreur.<\/p>\n<p>CAML interpr\u00e8te <code>absf -. 67.<\/code> comme <code>(absf -.) 67.0<\/code> en vertu de **l&rsquo;associativit\u00e9 \u00e0 gauche des applications **h\u00e9rit\u00e9e du &#40;\\lambda&#41;-calcul.<\/p>\n<p>Pour calculer la valeur absolue de -65.0, on doit \u00e9crire&#8230;<\/p>\n<pre><code class=\"language-ocaml\">absf (-. 67.0);;\n<\/code><\/pre>\n<p>&#8230;avec pour r\u00e9sultat :<\/p>\n<pre><code class=\"language-ocaml\">float = 67.\n<\/code><\/pre>\n<h5><a id=\"exercice-de-d%C3%A9couverte-b-dec-x1\" class=\"anchor\" aria-hidden=\"true\"><\/a>Exercice de d\u00e9couverte B.dec.x1<\/h5>\n<p>La fonction de Syracuse <code>syr<\/code> associe \u00e0 tout entier <code>x<\/code> la valeur :<\/p>\n<ul>\n<li><code>x \/ 2<\/code> si <code>x<\/code> est pair,<\/li>\n<li><code>3 * x + 1<\/code> si <code>x<\/code> est impair.<\/li>\n<\/ul>\n<p>Donnez une sp\u00e9cification de la fonction <code>syr<\/code> en CAML. L&rsquo;op\u00e9rateur modulo s&rsquo;\u00e9crit <code>mod<\/code>.<\/p>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">R\u00e9ponse<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<pre><code class=\"language-ocaml\">let syr x =\n  if x mod 2 = 0 then\n    x \/ 2\n  else\n    (3 * x) + 1;;\n<\/code><\/pre>\n<p><\/div>\n\t\t\t<\/div>\n<p>Donnez la ligne \u00e0 saisir pour appliquer <code>syr<\/code> \u00e0 7 et l&rsquo;appliquer \u00e0 nouveau au r\u00e9sultat obtenu.<\/p>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">R\u00e9ponse<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<pre><code class=\"language-ocaml\">syr (syr 7);;\n<\/code><\/pre>\n<p><\/div>\n\t\t\t<\/div>\n<h3><a id=\"b-dec2-curryfication\" class=\"anchor\" aria-hidden=\"true\"><\/a>B.dec2 : Curryfication<\/h3>\n<p>En CAML, les fonctions \u00e0 plusieurs param\u00e8tres n&rsquo;existent pas, mais on peut les \u00ab\u00a0simuler\u00a0\u00bb par deux proc\u00e9d\u00e9s dont l&rsquo;un est appel\u00e9 curryfication, en m\u00e9moire au math\u00e9maticien Haskell Curry (1900..1982).<\/p>\n<p>Prenons l&rsquo;exemple d&rsquo;une fonction \u00e0 2 param\u00e8tres telle que la fonction somme&#8230;<\/p>\n<pre><code class=\"language-ocaml\">let sum a b = a + b;;\n<\/code><\/pre>\n<p>&#8230;dont la signature est :<\/p>\n<pre><code class=\"language-ocaml\">sum : int -&gt; int -&gt; int = &lt;fun&gt;\n<\/code><\/pre>\n<p>Cette signature, retourn\u00e9e par le compilateur, se lit <code>int -&gt; (int -&gt; int)<\/code> en vertu de <strong>l&rsquo;associativit\u00e9 \u00e0 droite<\/strong> des abstractions h\u00e9rit\u00e9e du &#40;\\lambda&#41;-calcul.<\/p>\n<p>On l&rsquo;interpr\u00e8te de la mani\u00e8re suivante :<\/p>\n<blockquote><p><code>sum<\/code> est une fonction qui \u00e0 tout entier associe (une fonction qui \u00e0 tout entier associe un entier).<\/p><\/blockquote>\n<p>En CAML, une fonction peut accepter une fonction en param\u00e8tre et retourner une fonction.<\/p>\n<p>Quand on \u00e9crit&#8230;<\/p>\n<pre><code class=\"language-ocaml\">sum 10 15;;\n<\/code><\/pre>\n<p>&#8230;qui est \u00e9quivalent, en vertu de l&rsquo;associativit\u00e9 \u00e0 gauche des application, \u00e0&#8230;<\/p>\n<pre><code class=\"language-ocaml\">(sum 10) 15;;\n<\/code><\/pre>\n<p>&#8230;on obtient le r\u00e9sultat :<\/p>\n<pre><code class=\"language-ocaml\">int = 25\n<\/code><\/pre>\n<p>Mais c&rsquo;est le d\u00e9tail de cette \u00e9valuation qui est int\u00e9ressant :<\/p>\n<ul>\n<li><code>sum 10<\/code> est d&rsquo;abord \u00e9valu\u00e9, et le r\u00e9sultat est une fonction qui \u00e0 tout entier <code>b<\/code> associe <code>10 + b<\/code>.<\/li>\n<li>puis cette fonction est appliqu\u00e9e \u00e0 15, avec pour r\u00e9sultat 25.<\/li>\n<\/ul>\n<p>On peut d&rsquo;ailleurs d\u00e9composer les deux \u00e9tapes&#8230;<\/p>\n<pre><code class=\"language-ocaml\">let f = sum 10;;\nf 15;;\n<\/code><\/pre>\n<p>&#8230;avec le m\u00eame r\u00e9sultat.<\/p>\n<p>La signature de <code>f<\/code> est :<\/p>\n<pre><code class=\"language-ocaml\">f : int -&gt; int = &lt;fun&gt;\n<\/code><\/pre>\n<h5><a id=\"exercice-de-d%C3%A9couverte-b-dec-x2\" class=\"anchor\" aria-hidden=\"true\"><\/a>Exercice de d\u00e9couverte B.dec.x2<\/h5>\n<p>Si saisi dans la console CAML&#8230;<\/p>\n<pre><code class=\"language-ocaml\">sum (10 15);;\n<\/code><\/pre>\n<p>&#8230; on obtient un message d&rsquo;erreur. Expliquez pourquoi.<\/p>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">R\u00e9ponse<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p>CAML essaie d&rsquo;appliquer 10 \u00e0 15, or 10 n&rsquo;est pas une fonction.<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<h5><a id=\"exercice-de-d%C3%A9couverte-b-dec-x3\" class=\"anchor\" aria-hidden=\"true\"><\/a>Exercice de d\u00e9couverte B.dec.x3<\/h5>\n<p>Quelle est la signature de la fonction suivante ?<\/p>\n<pre><code class=\"language-ocaml\">let f a b c = a + (b * c );;\n<\/code><\/pre>\n<p>Quel est la signature de la fonction suivante ?<\/p>\n<pre><code class=\"language-ocaml\">f 2 2;;\n<\/code><\/pre>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">R\u00e9ponse<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p>La signature de <code>f<\/code> est :<\/p>\n<pre><code class=\"language-ocaml\">int -&gt; int -&gt; int -&gt; int = &lt;fun&gt;\n<\/code><\/pre>\n<p>L&rsquo;\u00e9valuation <code>f 2 2<\/code> a pour r\u00e9sultat une fonction qui a tout entier <code>c<\/code> associe <code>2 + (2 * c)<\/code>, parce que <code>f 2 2 c<\/code> retourne <code>2 + (2 * c)<\/code>.<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<h5><a id=\"exercice-de-d%C3%A9couverte-b-dec-x4\" class=\"anchor\" aria-hidden=\"true\"><\/a>Exercice de d\u00e9couverte B.dec.x4<\/h5>\n<p>Sp\u00e9cifiez la fonction <code>m<\/code> telle que <code>m a b<\/code> retourne <code>true<\/code> si <code>b<\/code> est un multiple de <code>a<\/code> et <code>false<\/code> sinon.<\/p>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">R\u00e9ponse<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p>Voici une solution :<\/p>\n<pre><code class=\"language-ocaml\">let m a b =\n  if b mod a = 0 then\n    true\n  else\n    false;;\n<\/code><\/pre>\n<p>Et une autre version plus concise :<\/p>\n<pre><code class=\"language-ocaml\">let m a b = (b mod a = 0);;\n<\/code><\/pre>\n<p><\/div>\n\t\t\t<\/div>\n<hr \/>\n<p>Il est aussi possible de d\u00e9finir une fonction ayant pour seul param\u00e8tre un couple de deux entiers. Cette technique se rapproche du style des fonctions en programmation imp\u00e9rative (C, python,&#8230;). Elle est moins dans \u00ab\u00a0l&rsquo;esprit\u00a0\u00bb de CAML, mais il est int\u00e9ressant d&rsquo;en conna\u00eetre la syntaxe.<\/p>\n<pre><code class=\"language-ocaml\">let add (a,b) = a + b;;\n<\/code><\/pre>\n<p>La signature de la fonction est :<\/p>\n<pre><code class=\"language-ocaml\">add : int * int -&gt; int = &lt;fun&gt;\n<\/code><\/pre>\n<p>La fonction s&rsquo;utilise avec la syntaxe suivante :<\/p>\n<pre><code class=\"language-ocaml\">add (10,15);;\n<\/code><\/pre>\n<p>Le r\u00e9sultat est :<\/p>\n<pre><code class=\"language-ocaml\">int = 25\n<\/code><\/pre>\n<p>Attention, avec cette fonction, les syntaxes suivantes sont incorrectes :<\/p>\n<pre><code class=\"language-ocaml\">add 10 15;;\n(add 10) 15\nadd (10 15);;\n<\/code><\/pre>\n<p>Dans la suite, nous n&rsquo;utiliserons <strong>pas<\/strong> cette syntaxe. Nous utiliserons le principe de la curryfication pour sp\u00e9cifier des fonctions \u00e0 plusieurs param\u00e8tres.<\/p>\n<h3><a id=\"b-dec3-listes-et-r%C3%A9cursivit%C3%A9\" class=\"anchor\" aria-hidden=\"true\"><\/a>B.dec3 : Listes et r\u00e9cursivit\u00e9<\/h3>\n<p>Une liste peut \u00eatre construite ou d\u00e9compos\u00e9e avec <code>[]<\/code> et <code>::<\/code>.<\/p>\n<p>Exemple :<\/p>\n<pre><code class=\"language-ocaml\">let m = 3::[];;\nlet p = 7::m;;\n<\/code><\/pre>\n<p>R\u00e9sultat :<\/p>\n<pre><code class=\"language-ocaml\">m : int list = [3]\np : int list = [7;3]\n<\/code><\/pre>\n<p>La <strong>reconnaissance de motifs<\/strong> permet de d\u00e9composer une liste. Voici un exemple. La fonction suivante permet de calculer la longueur d&rsquo;une liste.<\/p>\n<pre><code class=\"language-ocaml\">let rec longueur w =\n  match w with\n  |[] -&gt; 0\n  |x::q -&gt; 1 + longueur q;;\n<\/code><\/pre>\n<p>Le mot cl\u00e9 <code>rec<\/code> est nouveau. Il indique que la fonction d\u00e9finie est <strong>r\u00e9cursive<\/strong>.<\/p>\n<p>L&rsquo;instruction <code>match<\/code> permet de r\u00e9aliser un branchement qui est d\u00e9termin\u00e9 par la structure de la liste <code>w<\/code>. Si cette liste est vide alors la valeur de retour est 0. Si cette liste se d\u00e9compose en une t\u00eate <code>x<\/code> et une queue <code>q<\/code> alors sa longueur vaut 1 plus la longueur de <code>q<\/code>, laquelle est calcul\u00e9e par un appel r\u00e9cursif.<\/p>\n<p>La signature de <code>longueur<\/code> est :<\/p>\n<pre><code class=\"language-ocaml\">longueur : a' list -&gt; int = &lt;fun&gt;\n<\/code><\/pre>\n<p>Elle nous dit que nous avons une fonction qui \u00e0 toute liste d&rsquo;\u00e9l\u00e9ments d&rsquo;un type <code>'a<\/code> quelconque associe un entier.<\/p>\n<p>Voici un exemple d&rsquo;utilisation&#8230;<\/p>\n<pre><code class=\"language-ocaml\">longueur [1;2;7];;\n<\/code><\/pre>\n<p>&#8230;avec pour r\u00e9sultat :<\/p>\n<pre><code class=\"language-ocaml\">int =\u00a03\n<\/code><\/pre>\n<p>Les motifs d&rsquo;un <code>match<\/code> doivent couvrir toutes les possibilit\u00e9s. Voici une sp\u00e9cification <strong>incorrecte<\/strong> d&rsquo;une fonction qui produit le dernier \u00e9l\u00e9ment d&rsquo;une liste.<\/p>\n<pre><code class=\"language-ocaml\">let rec dernier w =\n  match w with\n  |[e] -&gt; e;\n  |x::q -&gt; dernier q;;\n<\/code><\/pre>\n<p>Le probl\u00e8me est qu&rsquo;aucun des motifs de l&rsquo;instruction <code>match<\/code> ne couvre le cas o\u00f9 la liste <code>w<\/code> est vide. On peut corriger en ajoutant ce cas, qui produira un message d&rsquo;erreur \u00e0 l&rsquo;ex\u00e9cution.<\/p>\n<pre><code class=\"language-ocaml\">let rec dernier w =\n  match w with\n  |[] -&gt; failwith \"Liste vide\"\n  |[e] -&gt; e;\n  |x::q -&gt; dernier q;;\n<\/code><\/pre>\n<p>Le principe du calcul est le suivant :<\/p>\n<ul>\n<li>Le dernier \u00e9l\u00e9ment d&rsquo;une liste qui contient un seul \u00e9l\u00e9ment est cet \u00e9l\u00e9ment.<\/li>\n<li>Le dernier \u00e9l\u00e9ment d&rsquo;une liste contenant au moins deux \u00e9l\u00e9ments et le dernier \u00e9l\u00e9ment de la queue de cette liste.<\/li>\n<\/ul>\n<p>La signature de la fonction est&#8230;<\/p>\n<pre><code class=\"language-ocaml\">dernier : 'a list -&gt; 'a = &lt;fun&gt;\n<\/code><\/pre>\n<p>&#8230;i.e., une fonction qui a toute liste d&rsquo;\u00e9l\u00e9ments d&rsquo;un type quelconque <code>'a<\/code> associe un \u00e9l\u00e9ment de type <code>'a<\/code>.<\/p>\n<h5><a id=\"exercice-de-d%C3%A9couverte-b-dec-x5\" class=\"anchor\" aria-hidden=\"true\"><\/a>Exercice de d\u00e9couverte B.dec.x5<\/h5>\n<p>Sp\u00e9cifiez une fonction <code>sum<\/code> telle que si <code>w<\/code> est une liste d&rsquo;entiers alors <code>sum w<\/code> retourne la somme des valeurs de <code>w<\/code>.<\/p>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">R\u00e9ponse<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<pre><code class=\"language-ocaml\">let rec sum w =\n  match w with\n  |[] -&gt; 0\n  |x::q -&gt; x + (sum q);;\n<\/code><\/pre>\n<p><\/div>\n\t\t\t<\/div>\n<hr \/>\n<p>Examinons maintenant une fonction qui construit et retourne une liste. La fonction <code>pVals<\/code> ci-dessous produit la liste des valeurs paires d&rsquo;une liste d&rsquo;entier <code>w<\/code>.<\/p>\n<pre><code class=\"language-ocaml\">let rec pVals w =\n  match w with\n  |[] -&gt; []\n  |x::q -&gt; \n      if x mod 2 = 0 then \n        x::(pVals q)\n      else \n        pVals q;;\n<\/code><\/pre>\n<ul>\n<li>Si la liste d&rsquo;entr\u00e9e est vide, la liste de sortie aussi.<\/li>\n<li>Si la liste d&rsquo;entr\u00e9e est de la forme <code>x::q<\/code> avec <code>x<\/code> pair, la liste de sortie a pour t\u00eate <code>x<\/code> et pour queue les valeurs paires de <code>q<\/code>.<\/li>\n<li>Si la liste d&rsquo;entr\u00e9e est de la forme <code>x::q<\/code> avec <code>x<\/code> impair, la liste de sortie est la liste des valeurs paires de <code>q<\/code>.<\/li>\n<\/ul>\n<h5><a id=\"exercice-de-d%C3%A9couverte-b-dec-x6\" class=\"anchor\" aria-hidden=\"true\"><\/a>Exercice de d\u00e9couverte B.dec.x6<\/h5>\n<p>Compl\u00e9tez la sp\u00e9cification de la fonction <code>gen<\/code> telle que si <code>n<\/code> est un entier positif ou nul et <code>x<\/code> une valeur d&rsquo;un type quelconque, alors <code>gen n x<\/code> retourne une liste contenant <code>n<\/code> occurrences de <code>x<\/code>.<\/p>\n<p>Par exemple&#8230;<\/p>\n<pre><code class=\"language-ocaml\">gen 4 7;;\n<\/code><\/pre>\n<p>&#8230;produit le r\u00e9sultat :<\/p>\n<pre><code class=\"language-ocaml\">[7;7;7;7]\n<\/code><\/pre>\n<p>Voici le code \u00e0 compl\u00e9ter :<\/p>\n<pre><code class=\"language-ocaml\">let rec gen n x =\n  if n = 0 then (*\u00c0 compl\u00e9ter*)\n  else (*\u00c0 compl\u00e9ter*)\n<\/code><\/pre>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">R\u00e9ponse<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<pre><code class=\"language-ocaml\">let rec gen n x =\n  if n = 0 then []\n  else x::(gen (n-1) x);;\n<\/code><\/pre>\n<p><\/div>\n\t\t\t<\/div>\n<h5><a id=\"exercice-de-d%C3%A9couverte-b-dec-x7\" class=\"anchor\" aria-hidden=\"true\"><\/a>Exercice de d\u00e9couverte B.dec.x7<\/h5>\n<p>R\u00e9alisez une fonction <code>d<\/code> telle que <code>d w<\/code> retourne <code>true<\/code> si <code>w<\/code> est une liste qui contient au moins deux valeurs identiques cons\u00e9cutives, et <code>false<\/code> sinon.<\/p>\n<p>Voici quelques exemples :<\/p>\n<pre><code class=\"language-ocaml\">d [2;5;3;3;3;1];; ---&gt; true\nd [2;5;3;3;1];;   ---&gt; true\nd [2;5;3;1];;     ---&gt; false\n<\/code><\/pre>\n<p>Voici le code \u00e0 compl\u00e9ter :<\/p>\n<pre><code class=\"language-ocaml\">let rec d w =\n  match w with\n  |[] -&gt; false\n  |[x] -&gt; false\n  |a::b::q -&gt; \n      (*\u00c0 compl\u00e9ter*)\n<\/code><\/pre>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">R\u00e9ponse<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<pre><code class=\"language-ocaml\">let rec d w =\n  match w with\n  |[] -&gt; false\n  |[x] -&gt; false\n  |a::b::q -&gt; \n      if a = b then true\n      else d (b::q);;\n<\/code><\/pre>\n<p><\/div>\n\t\t\t<\/div>\n<h3><a id=\"b-dec4-fonctions-d-ordre-sup%C3%A9rieur\" class=\"anchor\" aria-hidden=\"true\"><\/a>B.dec4 : Fonctions d&rsquo;ordre sup\u00e9rieur<\/h3>\n<p>On parle de fonction d&rsquo;ordre sup\u00e9rieur lorsqu&rsquo;au moins un des param\u00e8tres d&rsquo;une fonction est une fonction.<\/p>\n<p>Voici un exemple de fonction qui accepte en param\u00e8tre une fonction <code>f<\/code> et une liste <code>w<\/code>, qui retourne la somme des valeurs obtenues en appliquant <code>f<\/code> \u00e0 chaque \u00e9l\u00e9ment de <code>w<\/code>.<\/p>\n<pre><code class=\"language-ocaml\">let rec sigma f w =\n  match w with\n  |[] -&gt; 0\n  |x::q -&gt; f x + sigma f q;;\n<\/code><\/pre>\n<p>Par exemple, si on sp\u00e9cifie une fonction h qui calcule le carr\u00e9 d&rsquo;un entier&#8230;<\/p>\n<pre><code class=\"language-ocaml\">let h x = x * x;;\n<\/code><\/pre>\n<p>&#8230;alors l&rsquo;appel&#8230;<\/p>\n<pre><code class=\"language-ocaml\">sigma h [1;2;3];;\n<\/code><\/pre>\n<p>&#8230;retourne la valeur &#40;14&#41;, c&rsquo;est \u00e0 dire &#40;1^2 + 2^2 + 3^2&#41;.<\/p>\n<p>Le principe suivant est utilis\u00e9 :<\/p>\n<ul>\n<li>Si la liste <code>w<\/code> est vide alors la valeur 0 est retourn\u00e9e.<\/li>\n<li>Si la liste a une t\u00eate <code>x<\/code> et une queue <code>q<\/code>, alors la valeur retourn\u00e9e est (<code>h<\/code> appliqu\u00e9e \u00e0 <code>x<\/code>) plus la somme des valeurs obtenues en appliquant <code>h<\/code> aux \u00e9l\u00e9ments de <code>q<\/code>.<\/li>\n<\/ul>\n<h5><a id=\"exercice-de-d%C3%A9couverte-b-dec-x8\" class=\"anchor\" aria-hidden=\"true\"><\/a>Exercice de d\u00e9couverte B.dec.x8<\/h5>\n<p>On reprend la fonction <code>longueur<\/code>, vue dans une section pr\u00e9c\u00e9dente, qui calcule la longueur d&rsquo;une liste.<\/p>\n<pre><code class=\"language-ocaml\">let rec longueur w =\n  match w with\n  |[] -&gt; 0\n  |x::q -&gt; 1 + longueur q;;\n<\/code><\/pre>\n<p>On d\u00e9finit la liste de liste suivante :<\/p>\n<pre><code class=\"language-ocaml\">let t = [[1;2];[7];[3;5;1]];;\n<\/code><\/pre>\n<p>Utilisez la fonction <code>sigma<\/code> pour calculer la somme des longueurs des listes situ\u00e9es dans la liste <code>t<\/code>.<\/p>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">R\u00e9ponse<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<pre><code class=\"language-ocaml\">sigma longueur t;;\n<\/code><\/pre>\n<p><\/div>\n\t\t\t<\/div>\n<h5><a id=\"exercice-de-d%C3%A9couverte-b-dec-x9\" class=\"anchor\" aria-hidden=\"true\"><\/a>Exercice de d\u00e9couverte B.dec.x9<\/h5>\n<p>Sp\u00e9cifiez une fonction <code>fof<\/code> telle que si <code>h<\/code> est une fonction de signature <code>'a -&gt; 'a<\/code> et <code>x<\/code> une valeur de type <code>'a<\/code>, alors <code>fof h x<\/code> retourne la valeur obtenue en appliquant <code>h<\/code> deux fois de suite \u00e0 <code>x<\/code>.<\/p>\n<p>Par exemple, si <code>h<\/code> est la fonction qui \u00e0 tout entier &#40;x&#41; associe &#40;x^2&#41;&#8230;<\/p>\n<pre><code class=\"language-ocaml\">let h x = x * x;;\n<\/code><\/pre>\n<p>&#8230;alors <code>fof h 2<\/code> retourne 16 (2 au carr\u00e9 au carr\u00e9).<\/p>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">R\u00e9ponse<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<pre><code class=\"language-ocaml\">let fof h x =\n  h (h x);;\n<\/code><\/pre>\n<p><\/div>\n\t\t\t<\/div>\n<h3><a id=\"b-dec5-variantes-et-application-aux-arbres\" class=\"anchor\" aria-hidden=\"true\"><\/a>B.dec5 : Variantes et application aux arbres<\/h3>\n<p>Une <strong>variante<\/strong> est un type d\u00e9finit par compositions, possiblement r\u00e9cursives, de types existants.<\/p>\n<p>Voici un exemple de d\u00e9finition d&rsquo;un type <code>btree<\/code> permettant de repr\u00e9senter des arbres binaires dont les noeuds sont \u00e9tiquet\u00e9s par des entiers.<\/p>\n<pre><code class=\"language-ocaml\">type btree = E | N of int * btree * btree;;\n<\/code><\/pre>\n<p>Un objet de type <code>btree<\/code> est :<\/p>\n<ul>\n<li>Soit <code>E<\/code>, qui repr\u00e9sente une feuille,<\/li>\n<li>Soit <code>N(x,g,d)<\/code>, o\u00f9 <code>x<\/code> est de type <code>int<\/code>, <code>g<\/code> et <code>d<\/code> de type <code>btree<\/code>, qui repr\u00e9sente un noeud \u00e9tiquet\u00e9 par l&rsquo;entier <code>x<\/code> et ayant <code>g<\/code> pour fils gauche et <code>d<\/code> pour fils droit.<\/li>\n<\/ul>\n<p>Voici un exemple de repr\u00e9sentation d&rsquo;un arbre binaire.<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/9h15.net\/activ\/wp-content\/uploads\/2022\/01\/1-4.png\" alt=\"image-20220108211639463\" \/><\/p>\n<pre><code class=\"language-ocaml\">let t = N(5, N(3,E,E), E);;\n<\/code><\/pre>\n<p>Il faut bien comprendre que la syntaxe&#8230;<\/p>\n<pre><code class=\"language-ocaml\">N of int * btree * btree\n<\/code><\/pre>\n<p>&#8230;dans la d\u00e9finition du type correspond \u00e0&#8230;<\/p>\n<pre><code class=\"language-plain_text\">N({valeur de type int}, {valeur de type btree}, {valeur de type btree})\n<\/code><\/pre>\n<p>&#8230;lors de l&rsquo;utilisation.<\/p>\n<p>Voici un exemple de fonction qui v\u00e9rifie si un entier <code>x<\/code> est une des \u00e9tiquettes d&rsquo;un arbre <code>t<\/code>.<\/p>\n<pre><code class=\"language-ocaml\">let rec member x t =\n  match t with\n  |E -&gt; false                          (*Ligne A*) \n  |N(y, left, right) -&gt;\n      if x = y then true               (*Ligne B*) \n      else if member x left then true  (*Ligne C*) \n      else member x right;;            (*Ligne D*) \n<\/code><\/pre>\n<ul>\n<li><strong>Ligne A<\/strong> : si <code>t<\/code> est une feuille, alors <code>x<\/code> n&rsquo;est dans <code>t<\/code>.<\/li>\n<li><strong>Ligne B<\/strong> : si <code>t<\/code> a une racine avec l&rsquo;\u00e9tiquette <code>x<\/code> alors <code>x<\/code> est dans <code>t<\/code>.<\/li>\n<li><strong>Ligne C<\/strong> : si <code>t<\/code> a une racine avec un \u00e9tiquette diff\u00e9rente de <code>x<\/code> et que <code>x<\/code> est dans son fils gauche alors <code>x<\/code> est dans <code>t<\/code>.<\/li>\n<li><strong>Ligne D<\/strong> : sinon <code>x<\/code> est dans <code>t<\/code> si et seulement si il est dans son fils droit.<\/li>\n<\/ul>\n<p>Voici des exemples d&rsquo;utilisation avec l&rsquo;arbre <code>t<\/code> d\u00e9finit pr\u00e9c\u00e9demment :<\/p>\n<pre><code class=\"language-ocaml\">member 4 t;;   ---&gt; false\nmember 3 t;;   ---&gt; true\n<\/code><\/pre>\n<h5><a id=\"exercice-de-d%C3%A9couverte-b-dec-x10\" class=\"anchor\" aria-hidden=\"true\"><\/a>Exercice de d\u00e9couverte B.dec.x10<\/h5>\n<p>D\u00e9finissez un type <code>arbre<\/code> permettant de repr\u00e9senter des arbres binaires dont les noeuds ne sont pas \u00e9tiquet\u00e9s et les feuilles sont \u00e9tiquet\u00e9es avec des entiers. Repr\u00e9sentez avec ce type l&rsquo;arbre suivant :<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/9h15.net\/activ\/wp-content\/uploads\/2022\/01\/2-3.png\" alt=\"image-20220108214914615\" \/><\/p>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">R\u00e9ponse<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<pre><code class=\"language-ocaml\">type arbre = F of int | N of arbre * arbre;;\n\nlet a = N(N(F(3),F(5)),F(8));;\n<\/code><\/pre>\n<p><\/div>\n\t\t\t<\/div>\n<h5><a id=\"exercice-de-d%C3%A9couverte-b-dec-x11\" class=\"anchor\" aria-hidden=\"true\"><\/a>Exercice de d\u00e9couverte B.dec.x11<\/h5>\n<p>Sp\u00e9cifiez une fonction <code>sum<\/code> permettant de calculer la somme des valeurs des feuilles d&rsquo;un arbre du type d\u00e9fini dans l&rsquo;exercice pr\u00e9c\u00e9dent.<\/p>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">R\u00e9ponse<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<pre><code class=\"language-ocaml\">let rec sum t =\n  match t with\n  |F(x) -&gt; x\n  |N(g,d) -&gt; (sum g) + (sum d);;\n\n<\/code><\/pre>\n<p><\/div>\n\t\t\t<\/div>\n<h3><a id=\"b-dec6-compl%C3%A9ments\" class=\"anchor\" aria-hidden=\"true\"><\/a>B.dec6 : Compl\u00e9ments<\/h3>\n<h4><a id=\"instruction-let-in\" class=\"anchor\" aria-hidden=\"true\"><\/a>Instruction let in<\/h4>\n<p>Il peut \u00eatre utile de placer dans une nouvelle variable le r\u00e9sultat d&rsquo;un calcul qui pourra \u00eatre utilis\u00e9 plusieurs fois par la suite.<\/p>\n<p>L&rsquo;instruction <code>let ... in<\/code> permet de le faire, comme dans cet exemple de calcul du minimum d&rsquo;une liste.<\/p>\n<pre><code class=\"language-ocaml\">let rec min w =\n  match w with\n  |[] -&gt; failwith \"Erreur\"\n  |[x] -&gt; x\n  |t::q -&gt; let m = min q in\n      if t &lt; m then t else m;;\n<\/code><\/pre>\n<p>Si la liste comporte plusieurs \u00e9l\u00e9ments, on compare le premier au minimum de tous les \u00e9l\u00e9ments suivant, calcul\u00e9 par un appel r\u00e9cursif.<\/p>\n<p>L&rsquo;utilisation du <code>let ... in<\/code> n&rsquo;a rien d&rsquo;anecdotique. On peut r\u00e9aliser le programme sans, mais au prix d&rsquo;une perte d&rsquo;efficacit\u00e9 \u00e0 l&rsquo;ex\u00e9cution.<\/p>\n<p>La version de <code>min<\/code> pr\u00e9sent\u00e9e ci-dessus s&rsquo;ex\u00e9cute en temps lin\u00e9aire.<\/p>\n<p>Mais la version ci-dessous, sans <code>let ... in<\/code>, s&rsquo;ex\u00e9cute <strong>en temps exponentiel<\/strong> dans le pire des cas !<\/p>\n<pre><code class=\"language-ocaml\">let rec min w = \n  match w with\n  |[] -&gt; failwith \"Erreur\"\n  |[x] -&gt; x\n  |t::q -&gt; \n      if t &lt;  min q then t else min q;;\n<\/code><\/pre>\n<h5><a id=\"exercice-de-d%C3%A9couverte-b-dec-x12\" class=\"anchor\" aria-hidden=\"true\"><\/a>Exercice de d\u00e9couverte B.dec.x12<\/h5>\n<p>Comment faut-il ordonner les valeurs dans la liste pour que le deuxi\u00e8me version de <code>min<\/code> s&rsquo;ex\u00e9cute en temps lin\u00e9aire, et comment faut-il les ordonner pour qu&rsquo;elle s&rsquo;ex\u00e9cute en temps exponentiel ?<\/p>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">R\u00e9ponse<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p>Si la liste est en <strong>ordre croissant<\/strong>, la fonction s&rsquo;ex\u00e9cute en temps <strong>lin\u00e9aire<\/strong> car chaque appel r\u00e9alise un seul appel r\u00e9cursif.<\/p>\n<p>Si la liste est en <strong>ordre d\u00e9croissant<\/strong>, la fonction s&rsquo;ex\u00e9cute en temps <strong>exponentiel<\/strong> car chaque appel r\u00e9alise 2 appels r\u00e9cursifs distincts (pour calculer deux fois la m\u00eame chose).<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<h4><a id=\"variables-modifiables\" class=\"anchor\" aria-hidden=\"true\"><\/a>Variables modifiables<\/h4>\n<p>Ce qui est pr\u00e9sent\u00e9 rapidement ici sort du scope de cet enseignement mais peut avoir une utilit\u00e9, par exemple pour compter le nombre d&rsquo;appel r\u00e9cursifs lors de l&rsquo;ex\u00e9cution d&rsquo;une fonction. Voici un exemple avec la deuxi\u00e8me version de la fonction <code>min<\/code> vue pr\u00e9c\u00e9demment.<\/p>\n<pre><code class=\"language-ocaml\">let count = ref 0;;                         (*Ligne A*)\n\nlet rec min3 w =\n  (                                         (*Ligne B*)\n    count := !count + 1;                    (*Ligne C*)\n    match w with\n    |[] -&gt; failwith \"Erreur\"\n    |[x] -&gt; x\n    |t::q -&gt; \n        if t &lt;  min3 q then t else min3 q\n  );;                                       (*Ligne D*)\n\nmin3 [6;5;4;3;2;1];;                        (*Ligne E*)\n!count;;                                    (*Ligne F*)\n<\/code><\/pre>\n<p><strong>En ligne A<\/strong>, on d\u00e9clare une variable globale <code>count<\/code> de type r\u00e9f\u00e9rence initialis\u00e9e \u00e0 0. Le contenu de cette variable pourra changer au cours du temps.<\/p>\n<p><strong>En ligne B<\/strong>, on d\u00e9finit une s\u00e9quence, qui se termine en ligne D, avec la syntaxe <code>(bloc1; bloc2)<\/code>. Chaque bloc est \u00e9valu\u00e9 successivement. Le r\u00e9sultat de l&rsquo;\u00e9valuation de la s\u00e9quence est celui de l&rsquo;\u00e9valuation de son dernier bloc. On peut avoir plus de deux blocs.<\/p>\n<p><strong>En ligne C<\/strong>, le premier bloc de la s\u00e9quence r\u00e9cup\u00e8re le contenu <code>!count<\/code> de la variable globale, lui ajoute 1 et place le r\u00e9sultat dans la variable. Le but est de compter le nombre d&rsquo;appels de la fonction.<\/p>\n<p>Entre les lignes C et D, on a le code de la fonction <code>min<\/code> pr\u00e9sent\u00e9 pr\u00e9c\u00e9demment.<\/p>\n<p><strong>En ligne E<\/strong>, on appelle la fonction pour calculer le minimum d&rsquo;une liste.<\/p>\n<p><strong>En ligne F<\/strong>, on affiche la valeur du compteur.<\/p>\n<p>Le r\u00e9sultat de l&rsquo;ex\u00e9cution est :<\/p>\n<pre><code class=\"language-ocaml\">int = 1\nint = 63\n<\/code><\/pre>\n<p>La premi\u00e8re valeur est le r\u00e9sultat de l&rsquo;appel \u00e0 <code>min<\/code>, la deuxi\u00e8me est la valeur du compteur. On a r\u00e9alis\u00e9 63 appels \u00e0 la fonction pour calculer le minimum d&rsquo;une liste de 6 valeurs.<\/p>\n<h4><a id=\"concat%C3%A9nation-de-listes\" class=\"anchor\" aria-hidden=\"true\"><\/a>Concat\u00e9nation de listes<\/h4>\n<p>On peut sp\u00e9cifier une fonction r\u00e9cursive qui r\u00e9alise la concat\u00e9nation de deux listes. Cela sera laiss\u00e9 en exercice dans la partie entra\u00eenement.<\/p>\n<p>Mais CAML dispose d&rsquo;un op\u00e9rateur de concat\u00e9nation de liste repr\u00e9sent\u00e9 par le symbole <code>@<\/code>. Cet exemple&#8230;<\/p>\n<pre><code class=\"language-ocaml\">[1;3] @ [5;7];;\n<\/code><\/pre>\n<p>&#8230;produit le r\u00e9sultat :<\/p>\n<pre><code class=\"language-ocaml\">list = [1;3;5;7]\n<\/code><\/pre>\n<h2><a id=\"activit%C3%A9-d-entra%C3%AEnement-b-ent\" class=\"anchor\" aria-hidden=\"true\"><\/a>Activit\u00e9 d&rsquo;entra\u00eenement B.ent<\/h2>\n<p>Cette activit\u00e9 est essentielle. C&rsquo;est gr\u00e2ce \u00e0 elle que vous apprendrez vraiment \u00e0 comprendre et utiliser les notions vues pr\u00e9c\u00e9demment. Elle se d\u00e9compose en deux <strong>it\u00e9rations<\/strong> : <strong>ent1<\/strong>, <strong>ent2<\/strong>. Vous devez r\u00e9aliser au moins une it\u00e9ration et \u00e9valuer votre niveau de r\u00e9ussite.<\/p>\n<p>Si vous avez eu beaucoup de difficult\u00e9 \u00e0 traiter les exercices et fait beaucoup d&rsquo;erreurs, vous devrez traiter \u00e0 nouveau l&rsquo;activit\u00e9 de d\u00e9couverte pr\u00e9c\u00e9dente, en laissant passer au moins une nuit, avant de revenir \u00e0 cette activit\u00e9 d&rsquo;entra\u00eenement en r\u00e9alisant \u00e0 nouveau la premi\u00e8re l&rsquo;it\u00e9ration. Vous devez aussi essayer d&rsquo;identifier les points de blocage et demander \u00e0 votre enseignant de vous aider \u00e0 les surmonter.<\/p>\n<p>Si vous avez r\u00e9ussi certains exercices, mais \u00e9chou\u00e9 \u00e0 d&rsquo;autres, vous devrez d&rsquo;abord comprendre ce qui vous a conduit \u00e0 des erreurs et \/ ou ce qui vous a bloqu\u00e9. Si vous avez des doutes, des difficult\u00e9s, essayez de trouver les r\u00e9ponses dans les pr\u00e9sentations et explications de l&rsquo;activit\u00e9 de d\u00e9couverte et demandez toute l&rsquo;aide n\u00e9cessaire \u00e0 votre enseignant. Ensuite, vous devrez r\u00e9aliser l&rsquo;it\u00e9ration suivante apr\u00e8s au moins une nuit de sommeil et au plus une semaine.<\/p>\n<p>Si vous avez r\u00e9ussi presque tous les exercices et que vos rares erreurs sont dues \u00e0 l&rsquo;inattention, vous devriez revenir traiter l&rsquo;it\u00e9ration suivante apr\u00e8s un d\u00e9lai de plusieurs semaines.<\/p>\n<p>Si besoin, apr\u00e8s avoir trait\u00e9 la deuxi\u00e8me it\u00e9ration, vous pouvez revenir \u00e0 la premi\u00e8re. Vous pouvez aussi traiter des annales d&rsquo;\u00e9valuations de l&rsquo;unit\u00e9 d&rsquo;enseignement.<\/p>\n<h3><a id=\"it%C3%A9ration-b-ent1\" class=\"anchor\" aria-hidden=\"true\"><\/a>It\u00e9ration B.ent1<\/h3>\n<h4><a id=\"exercice-d-entrainement-b-ent1-1\" class=\"anchor\" aria-hidden=\"true\"><\/a>Exercice d&rsquo;entrainement B.ent1.1<\/h4>\n<p>Sp\u00e9cifiez la fonction <code>why<\/code> telle que si <code>x<\/code> est un entier positif alors <code>why x<\/code> retourne la valeur de la somme <code>1 + 2 + 3 + ... + x<\/code>.<\/p>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">Indice<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<pre><code class=\"language-ocaml\">let rec why x =\n  if x &lt;= 1 then 1\n  else (*\u00c0 compl\u00e9ter*)\n;;\n<\/code><\/pre>\n<p><\/div>\n\t\t\t<\/div>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">Solution<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<pre><code class=\"language-ocaml\">let rec why x =\n  if x &lt;= 1 then 1\n  else x + why (x-1)\n;;\n<\/code><\/pre>\n<p><\/div>\n\t\t\t<\/div>\n<h4><a id=\"exercice-d-entrainement-b-ent1-2\" class=\"anchor\" aria-hidden=\"true\"><\/a>Exercice d&rsquo;entrainement B.ent1.2<\/h4>\n<p>Sp\u00e9cifiez une fonction <code>at<\/code> qui, appliqu\u00e9e \u00e0 une liste <code>w<\/code> et un entier <code>i<\/code> positif ou nul, retourne l&rsquo;\u00e9l\u00e9ment situ\u00e9 en position <code>i<\/code> dans <code>w<\/code>. Les positions sont num\u00e9rot\u00e9es \u00e0 partir de 0. On suppose que <code>i<\/code> est compris entre 0 et la longueur de <code>w<\/code> moins 1.<\/p>\n<pre><code class=\"language-ocaml\">let s = [3;5;6;7;7];;\nat s 2;;                ---&gt; 6\n<\/code><\/pre>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">Indice<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<pre><code class=\"language-ocaml\">let rec at w i =\n  match w with\n  |[] -&gt; failwith \"Erreur\"\n  |x::q -&gt;\n      if i = 0 then (*\u00c0 compl\u00e9ter*)\n      else (*\u00c0 compl\u00e9ter*)\n;;\n<\/code><\/pre>\n<p><\/div>\n\t\t\t<\/div>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">R\u00e9ponse<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<pre><code class=\"language-ocaml\">let rec at w i =\n  match w with\n  |[] -&gt; failwith \"Erreur\"\n  |x::q -&gt;\n      if i = 0 then x\n      else at q (i-1)\n;;\n<\/code><\/pre>\n<p><\/div>\n\t\t\t<\/div>\n<h4><a id=\"exercice-d-entrainement-b-ent1-3\" class=\"anchor\" aria-hidden=\"true\"><\/a>Exercice d&rsquo;entrainement B.ent1.3<\/h4>\n<p>Sp\u00e9cifiez la fonction <code>add<\/code> qui, appliqu\u00e9e \u00e0 une liste <code>w<\/code> d&rsquo;\u00e9l\u00e9ments d&rsquo;un type quelconque <code>'a<\/code> et \u00e0 une valeur <code>x<\/code> de type <code>'a<\/code>, retourne la liste obtenue en ajoutant <code>x<\/code> \u00e0 la fin de <code>w<\/code>. Vous ne devez <strong>pas<\/strong> utiliser l&rsquo;op\u00e9rateur de concat\u00e9nation <code>@<\/code>.<\/p>\n<pre><code class=\"language-ocaml\">add [1;2;4] 7;;     ---&gt; [1;2;4;7] \n<\/code><\/pre>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">Indice<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<pre><code class=\"language-ocaml\">let rec add w x =\n  match w with\n  |[] -&gt; [x]\n  |t::q -&gt; (*\u00c0 compl\u00e9ter*)\n;;\n<\/code><\/pre>\n<p><\/div>\n\t\t\t<\/div>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">R\u00e9ponse<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<pre><code class=\"language-ocaml\">let rec add w x =\n  match w with\n  |[] -&gt; [x]\n  |t::q -&gt; t :: (add q x)\n;;\n<\/code><\/pre>\n<p><\/div>\n\t\t\t<\/div>\n<h4><a id=\"exercice-d-entrainement-b-ent1-4\" class=\"anchor\" aria-hidden=\"true\"><\/a>Exercice d&rsquo;entrainement B.ent1.4<\/h4>\n<p>Sp\u00e9cifiez la fonction <code>pref<\/code> qui, appliqu\u00e9e \u00e0 une liste <code>p<\/code> et une liste <code>w<\/code>, retourne <code>true<\/code> si et seulement si la liste p est un <strong>pr\u00e9fixe<\/strong> de la liste w, c&rsquo;est \u00e0 dire si <code>w<\/code> commence par <code>p<\/code> ou si <code>p<\/code> est vide.<\/p>\n<pre><code class=\"language-ocaml\">pref [1;2;3] [1;2;3;4;5];;    ---&gt; true\nperf [1;2;2] [1;2;3;4;5];;    ---&gt; false\n<\/code><\/pre>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">Indice<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<pre><code class=\"language-ocaml\">let rec pref p w =\n  match p  with\n  |[] -&gt; true                  (*Ligne A*)\n  |tp::qp -&gt;                   (*Ligne B*)\n      match w with\n      |[] -&gt; (*\u00c0 compl\u00e9ter*)\n      |tw::qw -&gt;\n             (*\u00c0 compl\u00e9ter*)\n;;\n<\/code><\/pre>\n<p>La liste vide est un pr\u00e9fixe de n&rsquo;importe quelle liste (ligne A).<\/p>\n<p>Si la, liste <code>p<\/code> n&rsquo;est pas vide (ligne B), alors il faut, pour que <code>p<\/code> soit pr\u00e9fixe de <code>w<\/code>, que <code>w<\/code> ne soit pas vide et que <code>w<\/code> commence par le m\u00eame \u00e9l\u00e9ment que <code>p<\/code> et que la queue de <code>p<\/code> soit un pr\u00e9fixe de la queue de <code>w<\/code>.<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">R\u00e9ponse<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<pre><code class=\"language-ocaml\">let rec pref p w =\n  match p  with\n  |[] -&gt; true\n  |tp::qp -&gt;\n      match w with\n      |[] -&gt; false\n      |tw::qw -&gt;\n          if tw = tp then \n            pref qp qw\n          else\n            false\n;;\n<\/code><\/pre>\n<p><\/div>\n\t\t\t<\/div>\n<h4><a id=\"exercice-d-entrainement-b-ent1-5\" class=\"anchor\" aria-hidden=\"true\"><\/a>Exercice d&rsquo;entrainement B.ent1.5<\/h4>\n<p>On utilise le type <code>btree<\/code> d\u00e9finit plus haut.<\/p>\n<pre><code class=\"language-ocaml\">type btree = E | N of int * btree * btree;;\n<\/code><\/pre>\n<p>Sp\u00e9cifiez la fonction <code>sz<\/code> qui, appliqu\u00e9e \u00e0 un arbre <code>t<\/code> de type <code>btree<\/code>, retourne le nombre de noeuds de <code>t<\/code>.<\/p>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">Indice<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<pre><code class=\"language-ocaml\">let rec sz t =\n  match t with\n  |E -&gt; 0\n  |N(x,g,d) -&gt;\n      (*\u00c0 compl\u00e9ter*)\n;;\n<\/code><\/pre>\n<p><\/div>\n\t\t\t<\/div>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">R\u00e9ponse<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<pre><code class=\"language-ocaml\">let rec sz t =\n  match t with\n  |E -&gt; 0\n  |N(x,g,d) -&gt;\n      (sz g) + (sz d) + 1\n;;\n<\/code><\/pre>\n<p><\/div>\n\t\t\t<\/div>\n<h4><a id=\"exercice-d-entrainement-b-ent1-6\" class=\"anchor\" aria-hidden=\"true\"><\/a>Exercice d&rsquo;entrainement B.ent1.6<\/h4>\n<p>On utilise le type <code>btree<\/code> d\u00e9finit plus haut.<\/p>\n<pre><code class=\"language-ocaml\">type btree = E | N of int * btree * btree;;\n<\/code><\/pre>\n<p>On appelle chemin une suite de noeuds qui part de la racine et aboutit \u00e0 une feuille. On d\u00e9finit le poids d&rsquo;un chemin comme la somme des valeurs de ses noeuds.<\/p>\n<p>Voici un exemple d&rsquo;arbre avec les poids de ses chemins.<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/9h15.net\/activ\/wp-content\/uploads\/2022\/01\/3-3.png\" alt=\"image-20220109173222250\" \/><\/p>\n<p>Sp\u00e9cifiez la fonction <code>maxPath<\/code> qui, appliqu\u00e9e \u00e0 un arbre <code>t<\/code>, retourne le poids d&rsquo;un chemin de <code>t<\/code> de poids maximum. Dans le cas de l&rsquo;exemple, la valeur est 20.<\/p>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">Indice<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<pre><code class=\"language-ocaml\">let rec maxPath t =\n  match t with\n  |E -&gt; 0\n  |N(x,g,d) -&gt;\n      let p1 = maxPath g in\n      let p2 = maxPath d in\n      (*\u00c0 compl\u00e9ter*)\n;;\n<\/code><\/pre>\n<p><\/div>\n\t\t\t<\/div>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">R\u00e9ponse<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<pre><code class=\"language-ocaml\">let rec maxPath t =\n  match t with\n  |E -&gt; 0\n  |N(x,g,d) -&gt;\n      let p1 = maxPath g in\n      let p2 = maxPath d in\n      if p1 &gt; p2 then x + p1\n      else x + p2\n;;\n<\/code><\/pre>\n<p><\/div>\n\t\t\t<\/div>\n<h4><a id=\"exercice-d-entrainement-b-ent1-7\" class=\"anchor\" aria-hidden=\"true\"><\/a>Exercice d&rsquo;entrainement B.ent1.7<\/h4>\n<p>On utilise le type <code>tree<\/code> suivant, qui repr\u00e9sente des arbres dont les feuilles sont \u00e9tiquet\u00e9es par des entiers et les noeuds ne sont pas \u00e9tiquet\u00e9s.<\/p>\n<pre><code class=\"language-ocaml\">type tree = F of int | N of tree * tree;;\n<\/code><\/pre>\n<p>Voici un exemple :<\/p>\n<pre><code class=\"language-ocaml\">let a = N(N(F 3, F 5),N(N(F 1, F 2), N(F 2, F 7)));;\n<\/code><\/pre>\n<p><img decoding=\"async\" src=\"https:\/\/9h15.net\/activ\/wp-content\/uploads\/2022\/01\/4-3.png\" alt=\"image-20220109175448506\" \/><\/p>\n<p>Sp\u00e9cifiez la fonction <code>collect<\/code> qui, appliqu\u00e9e \u00e0 un arbre <code>t<\/code>, retourne la liste des valeurs des \u00e9tiquettes des feuilles. Avec l&rsquo;exemple, cela donne la liste <code>[3;5;1;2;2;7]<\/code>. Vous pouvez utiliser l&rsquo;op\u00e9rateur de concat\u00e9nation <code>@<\/code>.<\/p>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">Indice<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<pre><code class=\"language-ocaml\">let rec collect t =\n  match t with\n  |F x -&gt; [x]\n  |N(g,d) -&gt;\n  (*\u00c0 compl\u00e9ter*)    \n;;\n<\/code><\/pre>\n<p><\/div>\n\t\t\t<\/div>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">R\u00e9ponse<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<pre><code class=\"language-ocaml\">let rec collect t =\n  match t with\n  |F x -&gt; [x]\n  |N(g,d) -&gt;\n      (collect g) @ (collect d)\n;;\n<\/code><\/pre>\n<p><\/div>\n\t\t\t<\/div>\n<h4><a id=\"exercice-d-entrainement-b-ent1-8\" class=\"anchor\" aria-hidden=\"true\"><\/a>Exercice d&rsquo;entrainement B.ent1.8<\/h4>\n<p>D\u00e9finissez un type <code>ubtree<\/code> permettant de repr\u00e9senter des arbres ayant des feuilles, des noeuds unaires et des noeuds binaires. Les noeuds et les feuilles ne sont pas \u00e9tiquet\u00e9es.<\/p>\n<p>Voici un exemple d&rsquo;arbre de type <code>ubtree<\/code>&#8230;<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/9h15.net\/activ\/wp-content\/uploads\/2022\/01\/6-3.png\" alt=\"image-20220109190400879\" \/><\/p>\n<p>&#8230;et sa repr\u00e9sentation :<\/p>\n<pre><code class=\"language-ocaml\">let y = U( B( U(F), U(B(F,F)) ) );;\n<\/code><\/pre>\n<p>Vous devez sp\u00e9cifier deux fonctions :<\/p>\n<ol>\n<li><code>countb t<\/code> : retourne le nombre de noeuds binaires de <code>t<\/code>.<\/li>\n<li><code>lmax t<\/code> : retourne la longueur du plus long chemin (entre la racine et une feuille) de t.<\/li>\n<\/ol>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">Indice1<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p>Voici la d\u00e9finition du type :<\/p>\n<pre><code class=\"language-ocaml\">type ubtree = F | U of ubtree | B of ubtree * ubtree;;\n<\/code><\/pre>\n<p><\/div>\n\t\t\t<\/div>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">R\u00e9ponse1<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<pre><code class=\"language-ocaml\">let rec countb t =\n  match t with\n  |F -&gt; 0\n  |U f -&gt; countb f\n  |B(g,d) -&gt; 1 + (countb g) + (countb d)\n;;\n<\/code><\/pre>\n<p><\/div>\n\t\t\t<\/div>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">R\u00e9ponse2<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<pre><code class=\"language-ocaml\">let rec lmax t =\n  match t with\n  |F -&gt; 0\n  |U f -&gt; (lmax f) + 1\n  |B(g,d) -&gt;\n      let m1 = lmax d in\n      let m2 = lmax g in\n      if m1&gt;m2 then m1+1\n      else m2+1\n;;\n<\/code><\/pre>\n<p><\/div>\n\t\t\t<\/div>\n<h3><a id=\"it%C3%A9ration-a-ent2\" class=\"anchor\" aria-hidden=\"true\"><\/a>It\u00e9ration A.ent2<\/h3>\n<h4><a id=\"exercice-d-entrainement-b-ent2-1\" class=\"anchor\" aria-hidden=\"true\"><\/a>Exercice d&rsquo;entrainement B.ent2.1<\/h4>\n<p>Sp\u00e9cifiez la fonction <code>divdiv2<\/code> qui \u00e0 tout entier <code>x<\/code> positif associe l&rsquo;entier obtenu en divisant <code>x<\/code> par 2 autant de fois que n\u00e9cessaire pour obtenir une valeur impaire.<\/p>\n<pre><code class=\"language-ocaml\">divdiv 2 7;;      ---&gt; 7\ndivdiv 2 10;;     ---&gt; 5\ndivdiv 2 320;;    ---&gt; 7\n<\/code><\/pre>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">Indice<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<pre><code class=\"language-ocaml\">let rec divdiv2 x =\n  if(x mod 2 != 0) then x\n  else (*\u00c0 compl\u00e9ter*)\n;;\n<\/code><\/pre>\n<p><\/div>\n\t\t\t<\/div>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">R\u00e9ponse<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<pre><code class=\"language-ocaml\">let rec divdiv2 x =\n  if(x mod 2 != 0) then x\n  else divdiv2 (x\/2)\n;;\n<\/code><\/pre>\n<p><\/div>\n\t\t\t<\/div>\n<h4><a id=\"exercice-d-entrainement-b-ent2-2\" class=\"anchor\" aria-hidden=\"true\"><\/a>Exercice d&rsquo;entrainement B.ent2.2<\/h4>\n<p>Sp\u00e9cifiez une fonction <code>gen<\/code> qui, appliqu\u00e9e \u00e0 un entier positif <code>a<\/code> et une entier <code>b<\/code> sup\u00e9rieur ou \u00e9gal \u00e0 a, retourne la liste des entiers compris entre <code>a<\/code> et <code>b<\/code>.<\/p>\n<pre><code class=\"language-ocaml\">gen 1 4;;        ---&gt; [1;2;3;4]\n<\/code><\/pre>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">Indice<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<pre><code class=\"language-ocaml\">let rec gen a b =\n  if a = b then [a]\n  else (*\u00c0 compl\u00e9ter*)\n;;\n<\/code><\/pre>\n<p><\/div>\n\t\t\t<\/div>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">R\u00e9ponse<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<pre><code class=\"language-ocaml\">let rec gen a b =\n  if a = b then [a]\n  else a :: gen (a+1) b\n;;\n<\/code><\/pre>\n<p><\/div>\n\t\t\t<\/div>\n<h4><a id=\"exercice-d-entrainement-b-ent2-3\" class=\"anchor\" aria-hidden=\"true\"><\/a>Exercice d&rsquo;entrainement B.ent2.3<\/h4>\n<p>Sp\u00e9cifiez une fonction <code>miroir<\/code> qui, appliqu\u00e9e \u00e0 une liste <code>w<\/code>, retourne la liste miroir de <code>w<\/code>, c&rsquo;est \u00e0 dire comportant les m\u00eames \u00e9l\u00e9ments dans l&rsquo;ordre inverse.<\/p>\n<pre><code class=\"language-ocaml\">miroir [1;2;3;4];;     ---&gt; [4;3;2;1]\n<\/code><\/pre>\n<p>Vous pouvez utiliser l&rsquo;op\u00e9rateur de concat\u00e9nation <code>@<\/code>.<\/p>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">Indice<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<pre><code class=\"language-ocaml\">let rec miroir w =\n  match w with\n  |[] -&gt; []\n  |x::q -&gt; (*\u00c0 compl\u00e9ter*)\n;;\n<\/code><\/pre>\n<p><\/div>\n\t\t\t<\/div>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">R\u00e9ponse<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<pre><code class=\"language-ocaml\">let rec miroir w =\n  match w with\n  |[] -&gt; []\n  |x::q -&gt; (miroir q) @ [x]\n;;\n<\/code><\/pre>\n<p><\/div>\n\t\t\t<\/div>\n<h4><a id=\"exercice-d-entrainement-b-ent2-4\" class=\"anchor\" aria-hidden=\"true\"><\/a>Exercice d&rsquo;entrainement B.ent2.4<\/h4>\n<p>Sp\u00e9cifiez la fonction <code>concat<\/code> qui, appliqu\u00e9e \u00e0 une liste <code>a<\/code> et une liste <code>b<\/code>, retourne la liste obtenue par concat\u00e9nation de <code>a<\/code> et <code>b<\/code>. Vous ne devez <strong>pas<\/strong> utiliser l&rsquo;op\u00e9rateur de concat\u00e9nation <code>@<\/code>. Vous ne devez pas appeler d&rsquo;autre fonction.<\/p>\n<pre><code class=\"language-ocaml\">concat [1;2] [3;4];;   ---&gt; [1;2;3;4]\n<\/code><\/pre>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">Indice<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<pre><code class=\"language-ocaml\">let rec concat a b =\n  match a with\n  |[] -&gt; b\n  |ta::qa -&gt;\n      (*\u00c0 compl\u00e9ter*)\n;;\n<\/code><\/pre>\n<p>Si <code>a<\/code> est vide alors le r\u00e9sultat est <code>b<\/code>. Dans le cas contraire, quel est le premier \u00e9l\u00e9ment du r\u00e9sultat ? Comment obtenir la queue du r\u00e9sultat ?<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">R\u00e9ponse<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<pre><code class=\"language-ocaml\">let rec concat a b =\n  match a with\n  |[] -&gt; b\n  |ta::qa -&gt;\n      ta :: (concat qa b)\n;;\n<\/code><\/pre>\n<p><\/div>\n\t\t\t<\/div>\n<h4><a id=\"exercice-d-entrainement-b-ent2-5\" class=\"anchor\" aria-hidden=\"true\"><\/a>Exercice d&rsquo;entrainement B.ent2.5<\/h4>\n<p>On utilise le type <code>btree<\/code> d\u00e9finit plus haut.<\/p>\n<pre><code class=\"language-ocaml\">type btree = E | N of int * btree * btree;;\n<\/code><\/pre>\n<p>Sp\u00e9cifiez la fonction <code>nf<\/code> qui, appliqu\u00e9e \u00e0 un arbre <code>t<\/code> de type <code>btree<\/code>, retourne le nombre de feuilles de <code>t<\/code>.<\/p>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">Indice<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<pre><code class=\"language-ocaml\">let rec nf t =\n  match t with\n  |E -&gt; 1\n  |N(x,g,d) -&gt;\n      (*\u00c0 compl\u00e9ter*)\n;;\n<\/code><\/pre>\n<p><\/div>\n\t\t\t<\/div>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">R\u00e9ponse<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<pre><code class=\"language-ocaml\">let rec nf t =\n  match t with\n  |E -&gt; 1\n  |N(x,g,d) -&gt;\n      (nf g) + (nf d)\n;;\n<\/code><\/pre>\n<p><\/div>\n\t\t\t<\/div>\n<h4><a id=\"exercice-d-entrainement-b-ent2-6\" class=\"anchor\" aria-hidden=\"true\"><\/a>Exercice d&rsquo;entrainement B.ent2.6<\/h4>\n<p>On utilise le type <code>tree<\/code> suivant, qui repr\u00e9sente des arbres dont les feuilles sont \u00e9tiquet\u00e9es par des entiers et les noeuds ne sont pas \u00e9tiquet\u00e9s.<\/p>\n<pre><code class=\"language-ocaml\">type tree = F of int | N of tree * tree;;\n<\/code><\/pre>\n<p>Voici un exemple :<\/p>\n<pre><code class=\"language-ocaml\">let a = N(N(F 3, F 5),N(N(F 1, F 2), N(F 2, F 7)));;\n<\/code><\/pre>\n<p><img decoding=\"async\" src=\"https:\/\/9h15.net\/activ\/wp-content\/uploads\/2022\/01\/4-3.png\" alt=\"image-20220109175448506\" \/><\/p>\n<p>Sp\u00e9cifiez la fonction <code>minLeaf<\/code> qui, appliqu\u00e9e \u00e0 un arbre <code>t<\/code>, retourne la plus petite valeur d&rsquo;une feuille. Dans le cas de l&rsquo;exemple, la valeur est 1.<\/p>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">Indice<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<pre><code class=\"language-ocaml\">let rec minLeaf t =\n  match t with\n  |F x -&gt; (*\u00c0 compl\u00e9ter*)\n  |N(g,d) -&gt; \n      let m1 = minLeaf g in\n      let m2 = minLeaf d in\n      (*\u00c0 compl\u00e9ter*)\n;;\n<\/code><\/pre>\n<p><\/div>\n\t\t\t<\/div>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">R\u00e9ponse<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<pre><code class=\"language-ocaml\">let rec minLeaf t =\n  match t with\n  |F x -&gt; x\n  |N(g,d) -&gt; \n      let m1 = minLeaf g in\n      let m2 = minLeaf d in\n      if m1 &gt; m2 then m2\n      else m1\n;;\n<\/code><\/pre>\n<p><\/div>\n\t\t\t<\/div>\n<h4><a id=\"exercice-d-entrainement-b-ent2-7\" class=\"anchor\" aria-hidden=\"true\"><\/a>Exercice d&rsquo;entrainement B.ent2.7<\/h4>\n<p>On utilise le type <code>btree<\/code> d\u00e9finit ainsi.<\/p>\n<pre><code class=\"language-ocaml\">type btree = E | N of int * btree * btree;;\n<\/code><\/pre>\n<p>La liste des noeuds d&rsquo;un arbre en ordre pr\u00e9fixe est constitu\u00e9e le l&rsquo;\u00e9tiquette racine, suivie de la liste des noeuds du fils gauche en ordre pr\u00e9fixe, suivie de la liste des noeuds du fils droit en ordre pr\u00e9fixe.<\/p>\n<p>Dans le cas de l&rsquo;arbre suivant&#8230;<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/9h15.net\/activ\/wp-content\/uploads\/2022\/01\/5-3.png\" alt=\"image-20220109183520020\" \/><\/p>\n<p>&#8230;on obtient la liste <code>[5;15;2;3;5]<\/code>.<\/p>\n<p>Sp\u00e9cifiez la fonction <code>prefx<\/code> qui, appliqu\u00e9e \u00e0 un arbre <code>t<\/code>, retourne la liste de ses noeuds en ordre pr\u00e9fixe.<\/p>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">R\u00e9ponse<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<pre><code class=\"language-ocaml\">let rec prefx t =\n  match t with\n  |E -&gt; []\n  |N(x,g,d) -&gt; \n      x :: (prefx g) @ (prefx d)\n;;\n<\/code><\/pre>\n<p><\/div>\n\t\t\t<\/div>\n<h4><a id=\"exercice-d-entrainement-b-ent2-8\" class=\"anchor\" aria-hidden=\"true\"><\/a>Exercice d&rsquo;entrainement B.ent2.8<\/h4>\n<p>On s&rsquo;int\u00e9resse aux arbres constitu\u00e9s de noeud \u00e9tiquet\u00e9s par des entiers pouvant avoir aucun, un ou plusieurs fils. On les repr\u00e9sente avec le type suivant. Les noeuds n&rsquo;ayant aucun fils jouent le r\u00f4le des feuilles.<\/p>\n<pre><code class=\"language-ocaml\">type nTree = L of int * nTree list;;\n<\/code><\/pre>\n<p>Voici un exemple d&rsquo;un tel arbre&#8230;<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/9h15.net\/activ\/wp-content\/uploads\/2022\/01\/7-2.png\" alt=\"image-20220109203846492\" \/><\/p>\n<p>&#8230;et sa repr\u00e9sentation :<\/p>\n<pre><code class=\"language-ocaml\">let q = L(5,[ L(7,[L(0,[]);L(0,[])]); L(3,[L(0,[])]); L(0,[]) ]);;\n<\/code><\/pre>\n<p>Sp\u00e9cifiez une fonction <code>sumt<\/code> qui, appliqu\u00e9e \u00e0 un arbre <code>t<\/code> de type <code>nTree<\/code>, retourne la somme des valeurs des \u00e9tiquettes de cet arbre.<\/p>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">Indice1<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<pre><code class=\"language-ocaml\">let rec sumt tr =\n  match tr with\n  |L(x,[]) -&gt; x\n  |L(x,t::q) -&gt;\n      (*\u00c0 compl\u00e9ter*)\n;;\n<\/code><\/pre>\n<p>On distingue deux cas :<\/p>\n<ol>\n<li>L&rsquo;arbre est une feuille d&rsquo;\u00e9tiquette <code>x<\/code>. Dans ce cas, la somme des valeurs de ses \u00e9tiquettes est <code>x<\/code>.<\/li>\n<li>L&rsquo;arbre a pour racine un noeud d&rsquo;\u00e9tiquette <code>x<\/code> ayant une liste de fils. Cette liste peut \u00eatre d\u00e9compos\u00e9e en une t\u00eate <code>t<\/code>, qui est un arbre, et une queue <code>q<\/code>, qui est une liste d&rsquo;arbres. Le r\u00e9sultat sera la somme de <code>x<\/code>, des valeurs de <code>t<\/code>, et de la somme des valeurs de tous les arbre de la liste <code>q<\/code>, qui est aussi la somme des valeurs de l&rsquo;arbre <code>L(0,q)<\/code>.<\/li>\n<\/ol>\n<p><\/div>\n\t\t\t<\/div>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">Indice2<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<pre><code class=\"language-ocaml\">let rec sumt tr =\n  match tr with\n  |L(x,[]) -&gt; x\n  |L(x,t::q) -&gt;\n      let s1 = sumt t in\n      let s2 = sumt (*\u00c0 compl\u00e9ter*) in\n      (*\u00c0 compl\u00e9ter*)\n;;\n<\/code><\/pre>\n<p><\/div>\n\t\t\t<\/div>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">R\u00e9ponse<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<pre><code class=\"language-ocaml\">let rec sumt tr =\n  match tr with\n  |L(x,[]) -&gt; x\n  |L(x,t::q) -&gt;\n      let s1 = sumt t in\n      let s2 = sumt (L(0,q)) in\n      s1 + s2 + x\n;;\n<\/code><\/pre>\n<p>Le terme <code>L(0,q)<\/code> doit \u00eatre mis entre parenth\u00e8ses pour qu&rsquo;il ne soit pas interpr\u00e9t\u00e9 comme <code>L<\/code> appliqu\u00e9 \u00e0 <code>(0,q)<\/code>.<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<h2><a id=\"activit%C3%A9-b-top\" class=\"anchor\" aria-hidden=\"true\"><\/a>Activit\u00e9 B.top<\/h2>\n<p>Cette activit\u00e9 propose des exercices de <strong>consolidation<\/strong> qui ne doivent \u00eatre abord\u00e9s que par les personnes apprenantes ma\u00eetrisant bien la partie A et les parties suivantes disponibles.<\/p>\n<p>Par exemple, si les parties actuellement disponibles sont A et B, vous devez d&rsquo;abord ma\u00eetriser la parie B avant de faire cette activit\u00e9 de consolidation de la partie A.<\/p>\n<h3><a id=\"b-top1\" class=\"anchor\" aria-hidden=\"true\"><\/a>B.top1<\/h3>\n<h4><a id=\"exercice-de-consolidation-b-top1\" class=\"anchor\" aria-hidden=\"true\"><\/a>Exercice de consolidation B.top1<\/h4>\n<p>Vous devez sp\u00e9cifier une fonction <code>tri<\/code> qui, appliqu\u00e9e \u00e0 une liste d&rsquo;entiers <code>w<\/code>, retourne la liste des \u00e9l\u00e9ments de <code>w<\/code> tri\u00e9s en ordre croissant.<\/p>\n<p>Exemple d&rsquo;utilisation :<\/p>\n<pre><code class=\"language-ocaml\">tri [17;5;1;45;2;1;3;24];;   ---&gt; [1;1;2;3;5;17;24;45]\n<\/code><\/pre>\n<p>Le tri r\u00e9alis\u00e9 doit \u00eatre bas\u00e9 sur le principe suivant :<\/p>\n<ol>\n<li>Chaque \u00e9l\u00e9ment de la liste \u00e0 trier est ins\u00e9r\u00e9 dans un <strong>arbre binaire tri\u00e9<\/strong>.<\/li>\n<li>L&rsquo;arbre tri\u00e9 est converti e n liste.<\/li>\n<\/ol>\n<p>Un arbre binaire tri\u00e9 est un arbre binaire dont les noeuds sont \u00e9tiquet\u00e9s par des entiers, dont les feuilles n&rsquo;ont pas d&rsquo;\u00e9tiquette, et qui a les propri\u00e9t\u00e9 suivantes.<\/p>\n<ul>\n<li>Toutes les \u00e9tiquettes du fils gauche d&rsquo;un arbre tri\u00e9 sont au plus \u00e9gales \u00e0 l&rsquo;\u00e9tiquette de sa racine.<\/li>\n<li>Toutes les \u00e9tiquettes de son fils droit sont sup\u00e9rieures \u00e0 l&rsquo;\u00e9tiquette de sa racine.<\/li>\n<li>Les sous arbres d&rsquo;un arbre binaire tri\u00e9 sont des arbres binaires tri\u00e9s.<\/li>\n<\/ul>\n<p>Voici un exemple du processus de tri d&rsquo;une liste.<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/9h15.net\/activ\/wp-content\/uploads\/2022\/01\/8-2.png\" alt=\"image-20220111130220492\" \/><\/p>\n<p>Vous devez d\u00e9composer votre solution en plusieurs fonctions. L&rsquo;utilisation de l&rsquo;op\u00e9rateur de concat\u00e9nation <code>@<\/code> est autoris\u00e9e.<\/p>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">Indice1<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p>On cr\u00e9e un type :<\/p>\n<pre><code class=\"language-ocaml\">type stree = L | N of int * stree * stree;;\n<\/code><\/pre>\n<p>On peut d\u00e9composer le programme en 4 fonctions :<\/p>\n<ul>\n<li><code>insert x t<\/code>, o\u00f9 <code>x<\/code> est un entier et <code>t<\/code> un arbre tri\u00e9 : retourne l&rsquo;arbre tri\u00e9 obtenu en ins\u00e9rant <code>x<\/code> dans <code>t<\/code>.<\/li>\n<li><code>list2tree w<\/code> : retourne l&rsquo;arbre tri\u00e9 comportant tous les \u00e9l\u00e9ments de la liste <code>w<\/code>.<\/li>\n<li><code>tree2list t<\/code> : retourne la liste croissante des valeurs des \u00e9tiquettes de l&rsquo;arbre tri\u00e9 <code>t<\/code>.<\/li>\n<li><code>tri w<\/code> : retourne la liste tri\u00e9e des \u00e9l\u00e9ments de la liste <code>w<\/code>.<\/li>\n<\/ul>\n<p><\/div>\n\t\t\t<\/div>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">Indice2<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p>Voici une version \u00e0 comp\u00e9ter de la fonction <code>insert<\/code>.<\/p>\n<pre><code class=\"language-ocaml\">let rec insert x t =\n  match t with\n  |L -&gt; N(x,L,L)\n  |N(y,g,d) -&gt;\n      if x&lt;=y then (*\u00c0 compl\u00e9ter*)\n      else N (*\u00c0 compl\u00e9ter*)\n;;\n<\/code><\/pre>\n<p>Le principe est le suivant :<\/p>\n<ul>\n<li>Si <code>t<\/code> est une feuille, alors l&rsquo;arbre produit a une racine de valeur <code>x<\/code> et deux feuilles.<\/li>\n<li>Sinon, si <code>x<\/code> est inf\u00e9rieur ou \u00e9gale \u00e0 la valeur <code>y<\/code> de la racine de <code>t<\/code>, on retourne un arbre avec la m\u00eame racine <code>y<\/code>, le m\u00eame sous arbre droit, mais un sous arbre gauche dans lequel <code>x<\/code> a \u00e9t\u00e9 ins\u00e9r\u00e9 par un appel r\u00e9cursif.<\/li>\n<li>Sinon, on retourne un arbre avec la m\u00eame racine <code>y<\/code>, le m\u00eame sous arbre gauche, mais un sous arbre droit dans lequel <code>x<\/code> a \u00e9t\u00e9 ins\u00e9r\u00e9 par un appel r\u00e9cursif.<\/li>\n<\/ul>\n<p><\/div>\n\t\t\t<\/div>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">Indice3<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p>Voici la fonction <code>insert<\/code> compl\u00e8te et des versions incompl\u00e8tes des fonctions <code>list2tree<\/code> et <code>tree2list<\/code>.<\/p>\n<pre><code class=\"language-ocaml\">let rec insert x t =\n  match t with\n  |L -&gt; N(x,L,L)\n  |N(y,g,d) -&gt;\n      if x&lt;=y then N(y,(insert x g),d)\n      else N(y,g,(insert x d))\n;;\n  \nlet rec list2tree w =\n  match w with\n  |[] -&gt; L\n  |x::q -&gt; (*\u00c0 compl\u00e9ter*)\n;;\n\nlet rec tree2list t =\n  match t with\n  |L -&gt; []\n  |N(x,g,d) -&gt; \n      (*\u00c0 compl\u00e9ter*)\n;;\n<\/code><\/pre>\n<p>Dans <code>list2tree<\/code>, on construit une arbre en ins\u00e9rant la t\u00eate de <code>w<\/code> dans l&rsquo;arbre tri\u00e9 contenant les \u00e9l\u00e9ments de la queue de <code>w<\/code>.<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">Solution<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<pre><code class=\"language-ocaml\">type stree = L | N of int * stree * stree;;\n\nlet rec insert x t =\n  match t with\n  |L -&gt; N(x,L,L)\n  |N(y,g,d) -&gt;\n      if x&lt;=y then N(y,(insert x g),d)\n      else N(y,g,(insert x d))\n;;\n  \nlet rec list2tree w =\n  match w with\n  |[] -&gt; L\n  |x::q -&gt; insert x (list2tree q)\n;;\n\nlet rec tree2list t =\n  match t with\n  |L -&gt; []\n  |N(x,g,d) -&gt; \n      (tree2list g) @ x::(tree2list d)\n;;\n\nlet tri w =\n  tree2list (list2tree w)\n;;\n\n<\/code><\/pre>\n<p><\/div>\n\t\t\t<\/div>\n<h3><a id=\"b-top2\" class=\"anchor\" aria-hidden=\"true\"><\/a>B.top2<\/h3>\n<h4><a id=\"exercice-de-consolidation-b-top2\" class=\"anchor\" aria-hidden=\"true\"><\/a>Exercice de consolidation B.top2<\/h4>\n<p>On d\u00e9finit un type&#8230;<\/p>\n<pre><code class=\"language-ocaml\">type ntree = N of ntree list;;\n<\/code><\/pre>\n<p>&#8230;qui permet de repr\u00e9senter des arbres sans \u00e9tiquette dont chaque noeud poss\u00e8de un nombre arbitraire de fils.<\/p>\n<p><code>N([])<\/code> repr\u00e9sente une feuille. On peut se dispenser des parenth\u00e8ses et \u00e9crire <code>N[]<\/code> pour une meilleure lisibilit\u00e9.<\/p>\n<p>Voici une exemple d&rsquo;arbre de type ntree&#8230;<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/9h15.net\/activ\/wp-content\/uploads\/2022\/01\/9-1.png\" alt=\"image-20220112090453565\" \/><\/p>\n<p>&#8230;et sa repr\u00e9sentation :<\/p>\n<pre><code class=\"language-ocaml\">let tt = N[ N[N[];N[]]; N[N[]]; N[] ];;\n<\/code><\/pre>\n<p>On d\u00e9finit \u00e9galement le type&#8230;<\/p>\n<pre><code class=\"language-ocaml\">type bintree = E | F | B of bintree * bintree;;\n<\/code><\/pre>\n<p>&#8230;qui repr\u00e9sente un arbre binaire non \u00e9tiquet\u00e9 avec deux sortes de feuilles identifi\u00e9es par les symboles <code>E<\/code> et <code>F<\/code>.<\/p>\n<p>On peut \u00e9tablir une correspondance bijective entre les deux repr\u00e9sentations comme indiqu\u00e9 dans cet exemple :<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/9h15.net\/activ\/wp-content\/uploads\/2022\/01\/10-1.png\" alt=\"image-20220112093042081\" \/><\/p>\n<p>Vous devez sp\u00e9cifier la fonction <code>n2bin<\/code> qui traduit un arbre de type <code>ntree<\/code> en un arbre de type <code>bintree<\/code> et la fonction <code>bin2n<\/code> qui fait la traduction dans l&rsquo;autres sens.<\/p>\n<p>Attention, tout terme de type <code>ntree<\/code> doit pouvoir \u00eatre traduit en type <code>bintree<\/code>, mais certains termes de type <code>bintree<\/code> ne correspondent \u00e0 aucun arbre valide de type <code>ntree<\/code>.<\/p>\n<p>Par exemple, le terme <code>E<\/code> ne correspond \u00e0 aucun arbre de type <code>ntree<\/code>. Le symbole <code>E<\/code> sert uniquement \u00e0 terminer le cha\u00eenage des fils droits des noeuds binaires dont les fils gauches correspondent \u00e0 des fils de l&rsquo;arbre de type <code>ntree<\/code> correspondant. R\u00e9f\u00e9rez vous \u00e0 l&rsquo;exemple ci-dessus.<\/p>\n<p>De m\u00eame, le fils droit d&rsquo;un noeud binaire d&rsquo;un arbre de type <code>bintree<\/code> repr\u00e9sentant un arbre de type ntree ne peut jamais \u00eatre le terme <code>F<\/code>.<\/p>\n<p>Commencez par la fonction <code>n2bin<\/code> qui est plus facile.<\/p>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">Indice1<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p>Le principe de n2bin est le suivant :<\/p>\n<ul>\n<li><code>N[]<\/code> se traduit en <code>F<\/code>.<\/li>\n<li><code>N[u]<\/code>, un arbre dont la racine a un fils unique u, se traduit en <code>B({traduction de u}, E)<\/code>.<\/li>\n<li>La traduction de <code>N(h::q)<\/code>, un arbre dont la racine a au moins 2 fils, a pour fils gauche la traduction de <code>h<\/code> et pour fils droit&#8230; <strong>pas<\/strong> la traduction de <code>q<\/code> car <code>q<\/code> est une liste de termes de type <code>ntree<\/code> et pas un terme de type <code>ntree<\/code>. Il y a une subtilit\u00e9. Si <code>q = [ N[N[]]; N[] ]<\/code>, c&rsquo;est <code>N[ N[N[]]; N[] ]<\/code> qu&rsquo;il faut traduire.<\/li>\n<\/ul>\n<p><\/div>\n\t\t\t<\/div>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">Indice2<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p>Voici la sp\u00e9cification de <code>n2bin<\/code>.<\/p>\n<pre><code class=\"language-ocaml\">let rec n2bin t = \n  match t with\n  |N[] -&gt; F\n  |N[u] -&gt; B(n2bin u, E)\n  |N(h::q) -&gt; B(n2bin h, n2bin (N q))\n;;\n<\/code><\/pre>\n<p><\/div>\n\t\t\t<\/div>\n<p>Vous devez maintenant sp\u00e9cifier <code>bin2n<\/code>, qui est plus difficile. Examinons quelques cas sur lesquels vous pouvez vous appuyer.<\/p>\n<pre><code class=\"language-ocaml\">bin2n E;;   ---&gt; (*Impossible, ne correspond \u00e0 aucun terme de type ntree*)\nbin2n F;;   ---&gt; N[]\nbin2n (B(F,E)) ---&gt; N[N[]]\nbin2n (B( B(F,E), B(F,E) )) ---&gt; N[ N[N[]] ; N[] ]\n<\/code><\/pre>\n<p><img decoding=\"async\" src=\"https:\/\/9h15.net\/activ\/wp-content\/uploads\/2022\/01\/11-1.png\" alt=\"image-20220112115940566\" \/><\/p>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">Indice3<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<pre><code class=\"language-ocaml\">let rec bin2n t =\n  match t with \n  |E -&gt; failwith \"Erreur\"\n  |F -&gt; N[] \n  |B(g,E) -&gt; (*\u00c0 compl\u00e9ter*)\n  |B(g,d) -&gt; \n      let t1 = bin2n g in\n      let t2 = bin2n d in\n      match t2 with\n      |N[] -&gt; failwith \"Erreur\"\n      |N(h::q) -&gt; (*\u00c0 compl\u00e9ter*)\n;;\n<\/code><\/pre>\n<p><\/div>\n\t\t\t<\/div>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">Solution<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<pre><code class=\"language-ocaml\">type ntree = N of ntree list;;\n\ntype bintree = E | F | B of bintree * bintree;;\n\nlet rec n2bin t = \n  match t with\n  |N[] -&gt; F\n  |N[u] -&gt; B(n2bin u, E)\n  |N(h::q) -&gt; B(n2bin h, n2bin (N q))\n;;\n\nlet rec bin2n t =\n  match t with \n  |E -&gt; failwith \"Erreur\"\n  |F -&gt; N[] \n  |B(g,E) -&gt; N[bin2n g] \n  |B(g,d) -&gt; \n      let t1 = bin2n g in\n      let t2 = bin2n d in\n      match t2 with\n      |N[] -&gt; failwith \"Erreur\"\n      |N(h::q) -&gt; N(t1::h::q)\n;;\n\nlet tt = N[ N[N[];N[]]; N[N[]]; N[] ];;\n\nn2bin tt;;\n\n<\/code><\/pre>\n<p><\/div>\n\t\t\t<\/div>\n<hr \/>\n","protected":false},"excerpt":{"rendered":"<p>Par O. Bailleux, Ma\u00eetre de conf\u00e9rences HDR \u00e0 l&rsquo;universit\u00e9 de Bourgogne. Le langage CAML Les activit\u00e9s #.dec (dec pour D\u00e9couverte) consistent \u00e0 \u00e9tudier des pr\u00e9sentations explicatives et \u00e0 traiter tous les exercices de d\u00e9couverte propos\u00e9s. Si vous ne r\u00e9pondez pas correctement \u00e0 un exercice de d\u00e9couverte, revenez en arri\u00e8re pour relire les explications et identifier [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"","sticky":false,"template":"","format":"standard","meta":{"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[3],"tags":[],"class_list":["post-108","post","type-post","status-publish","format-standard","hentry","category-plf","entry"],"jetpack_sharing_enabled":true,"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/9h15.net\/activ\/wp-json\/wp\/v2\/posts\/108","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/9h15.net\/activ\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/9h15.net\/activ\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/9h15.net\/activ\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/9h15.net\/activ\/wp-json\/wp\/v2\/comments?post=108"}],"version-history":[{"count":3,"href":"https:\/\/9h15.net\/activ\/wp-json\/wp\/v2\/posts\/108\/revisions"}],"predecessor-version":[{"id":485,"href":"https:\/\/9h15.net\/activ\/wp-json\/wp\/v2\/posts\/108\/revisions\/485"}],"wp:attachment":[{"href":"https:\/\/9h15.net\/activ\/wp-json\/wp\/v2\/media?parent=108"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/9h15.net\/activ\/wp-json\/wp\/v2\/categories?post=108"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/9h15.net\/activ\/wp-json\/wp\/v2\/tags?post=108"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}