{"id":213,"date":"2022-02-04T22:28:57","date_gmt":"2022-02-04T22:28:57","guid":{"rendered":"https:\/\/9h15.net\/activ\/?p=213"},"modified":"2022-02-04T22:29:04","modified_gmt":"2022-02-04T22:29:04","slug":"ds-de-lambdacalcul-et-caml","status":"publish","type":"post","link":"https:\/\/9h15.net\/activ\/ds-de-lambdacalcul-et-caml\/","title":{"rendered":"DS de lambda-calcul et CAML"},"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=\"sujet-de-devoir-surveill%C3%A9-de-2021\" class=\"anchor\" aria-hidden=\"true\"><span class=\"octicon octicon-link\"><\/span><\/a>Sujet de devoir surveill\u00e9 de 2021<\/h1>\n<h2><a id=\"lambda-calcul\" class=\"anchor\" aria-hidden=\"true\"><span class=\"octicon octicon-link\"><\/span><\/a>Lambda-calcul<\/h2>\n<h3><a id=\"a1-1-5-points\" class=\"anchor\" aria-hidden=\"true\"><span class=\"octicon octicon-link\"><\/span><\/a>A1 (1.5 points)<\/h3>\n<p>D\u00e9composez le terme suivant en abstractions (encadrez-les en pointill\u00e9s) et applications (encadrez-les en trait plein).<\/p>\n<p>\\[a \\; b \\; \\lambda x . \\; \\lambda y . \\; x \\; a \\; y \\; \\lambda a . \\; a \\; b<br \/>\n\\]<\/p>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;R\u00e9ponse&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p><img decoding=\"async\" src=\"https:\/\/9h15.net\/activ\/wp-content\/uploads\/2022\/02\/1-2.png\" alt=\"image-2022020421295974\" \/><\/p>\n<p><\/div>\n\t\t\t<\/div>\n<h3><a id=\"a2-1-5-points\" class=\"anchor\" aria-hidden=\"true\"><span class=\"octicon octicon-link\"><\/span><\/a>A2 (1.5 points)<\/h3>\n<p>Dans le terme suivant, entourez les occurrences libres de variables et reliez par des traits les occurrences li\u00e9es entre elles.<\/p>\n<p>\\[a \\; b \\; \\lambda x . \\; \\lambda y . \\; x \\; a \\; y \\; \\lambda a . \\; a \\; b<br \/>\n\\]<\/p>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;R\u00e9ponse&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p><img decoding=\"async\" src=\"https:\/\/9h15.net\/activ\/wp-content\/uploads\/2022\/02\/2-1.png\" alt=\"image-20220204213632076\" \/><\/p>\n<p><\/div>\n\t\t\t<\/div>\n<h3><a id=\"a2-2-points\" class=\"anchor\" aria-hidden=\"true\"><span class=\"octicon octicon-link\"><\/span><\/a>A2 (2 points)<\/h3>\n<p>Pour chacune des paires de termes suivantes, indiquez si les termes sont \u00e9quivalents. R\u00e9pondez par oui ou non.<\/p>\n<ol>\n<li>\\(a\\lambda b. ab\\) et \\(a\\lambda c. ac\\)<\/li>\n<li>\\(a\\lambda b. ab\\) et \\(b\\lambda b. bc\\)<\/li>\n<li>\\(\\lambda x.\\lambda f. f (fx)\\) et \\(\\lambda x.\\lambda f. f f x\\)<\/li>\n<li>\\(\\lambda x.\\lambda f. f (fx)\\) et \\(\\lambda f.\\lambda x. x (x f)\\)<\/li>\n<li>\\(a \\lambda x.x\\) et \\(a \\lambda y. y\\)<\/li>\n<li>\\(\\lambda x .xy \\lambda x . x\\) et \\(\\lambda x .yx \\lambda y . y\\)<\/li>\n<\/ol>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;R\u00e9ponse&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<ol>\n<li>oui<\/li>\n<li>non<\/li>\n<li>non<\/li>\n<li>oui<\/li>\n<li>oui<\/li>\n<li>non<\/li>\n<\/ol>\n<p><\/div>\n\t\t\t<\/div>\n<h3><a id=\"a2-5-points\" class=\"anchor\" aria-hidden=\"true\"><span class=\"octicon octicon-link\"><\/span><\/a>A2 (5 points)<\/h3>\n<p>\u00c9valuez chacun des termes suivants. Encadrez le redex utilis\u00e9 \u00e0 chaque \u00e9tape.<\/p>\n<p>\\[(\\lambda w. ww) a a<br \/>\n\\]<\/p>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;R\u00e9ponse&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<ol>\n<li>\\((aa)a\\) \u00e9quivalent \u00e0 \\(aaa\\)<\/li>\n<\/ol>\n<p><\/div>\n\t\t\t<\/div>\n<p>\\[(\\lambda w.waw)\\lambda x.x<br \/>\n\\]<\/p>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;R\u00e9ponse&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<ol>\n<li>\\((\\lambda x .x) a (\\lambda x . x)\\)<\/li>\n<li>\\(a(\\lambda x . x)\\) \u00e9quivalent \u00e0 \\(a \\lambda x.x\\)<\/li>\n<\/ol>\n<p><\/div>\n\t\t\t<\/div>\n<p>\\[u(\\lambda w.waw)(\\lambda x.x)bb<br \/>\n\\]<\/p>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;R\u00e9ponse&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p>Il n&rsquo;y a aucun redex car le terme se d\u00e9compose en :<\/p>\n<p>\\[[\\;[\\;[\\;[u(\\lambda w.waw)](\\lambda x.x)\\;]b\\;]b\\;]<br \/>\n\\]<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<p>\\[(\\lambda w . \\lambda y. aw)\\lambda x.yb<br \/>\n\\]<\/p>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;R\u00e9ponse&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<ol>\n<li>Un renommage est n\u00e9cessaire : \\((\\lambda w . \\lambda t. aw)\\lambda x.yb\\)<\/li>\n<li>\\(\\lambda t. a(\\lambda x.yb)\\)<\/li>\n<\/ol>\n<p><\/div>\n\t\t\t<\/div>\n<p>\\[(\\lambda g.\\lambda y.gy)(\\lambda f.\\lambda x.fx)<br \/>\n\\]<\/p>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;R\u00e9ponse&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<ol>\n<li>\\(\\lambda y.(\\lambda f.\\lambda x.fx)y\\)<\/li>\n<li>\\(\\lambda y.\\lambda x.yx\\)<\/li>\n<\/ol>\n<p><\/div>\n\t\t\t<\/div>\n<h2><a id=\"caml\" class=\"anchor\" aria-hidden=\"true\"><span class=\"octicon octicon-link\"><\/span><\/a>CAML<\/h2>\n<h3><a id=\"b1-1-5-points\" class=\"anchor\" aria-hidden=\"true\"><span class=\"octicon octicon-link\"><\/span><\/a>B1 (1.5 points)<\/h3>\n<p>Soit les fonctions suivantes :<\/p>\n<pre><code class=\"language-ocaml\">let rec fn f n x =\n  if(n &lt;= 0) then x\n  else fn f (n-1) (f x);;\n\nlet h x = 2*x;;\n<\/code><\/pre>\n<p>Donnez les valeurs retourn\u00e9es par :<\/p>\n<pre><code class=\"language-ocaml\">fn h 0 1;;\nfn h 1 1;;\nfn h 2 1;;\n<\/code><\/pre>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;R\u00e9ponse&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<pre><code class=\"language-ocaml\">1\n2\n4\n<\/code><\/pre>\n<p><\/div>\n\t\t\t<\/div>\n<h3><a id=\"b2-3-points\" class=\"anchor\" aria-hidden=\"true\"><span class=\"octicon octicon-link\"><\/span><\/a>B2 (3 points)<\/h3>\n<p>R\u00e9alisez une fonction <code>revconc<\/code> telle que si <code>a<\/code> et <code>b<\/code> sont des listes (contenant des \u00e9l\u00e9ments de m\u00eame type), alors <code>revconc a b<\/code> retourne la liste obtenue en concat\u00e9nant le miroir de <code>a<\/code> avec <code>b<\/code>. Voici un exemple d\u2019utilisation.<\/p>\n<pre><code class=\"language-ocaml\">revconc [1;2;3] [10;20;30];;\nint list = [3;2;1;10;20;30]\n<\/code><\/pre>\n<p>Le principe est le suivant :<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/9h15.net\/activ\/wp-content\/uploads\/2022\/02\/3-1.png\" alt=\"3\" \/><\/p>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;R\u00e9ponse&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<pre><code class=\"language-ocaml\">let rec revconc a b =\n  match a with\n  |[] -&gt; b\n  |t::q -&gt; revconc q (t::b)\n;;\n<\/code><\/pre>\n<p><\/div>\n\t\t\t<\/div>\n<h3><a id=\"b3-1-5-points\" class=\"anchor\" aria-hidden=\"true\"><span class=\"octicon octicon-link\"><\/span><\/a>B3 (1.5 points)<\/h3>\n<p>On d\u00e9finit le type <code>arbre<\/code> qui repr\u00e9sente des arbres binaires dont les n\u0153uds sont \u00e9tiquet\u00e9s par des entiers.<\/p>\n<pre><code class=\"language-ocaml\">type arbre = Vide | Noeud of int * arbre * arbre ;;\n<\/code><\/pre>\n<p>On dit qu\u2019un tel arbre <code>t<\/code> est <strong>tri\u00e9<\/strong> si et seulement si <code>t<\/code> est une feuille (repr\u00e9sent\u00e9 par <code>Vide<\/code>) ou <code>t<\/code> est un n\u0153ud d\u2019\u00e9tiquette <code>x<\/code>, de fils gauche <code>g<\/code> et de fils droit <code>d<\/code> respectant les conditions suivantes :<\/p>\n<ul>\n<li>\n<p>les valeurs des \u00e9tiquettes de <code>g<\/code> sont toutes strictement inf\u00e9rieures \u00e0 <code>x<\/code>,<\/p>\n<\/li>\n<li>\n<p>les valeurs des \u00e9tiquettes de <code>d<\/code> sont toute sup\u00e9rieures ou \u00e9gale \u00e0 <code>x<\/code>,<\/p>\n<\/li>\n<li>\n<p><code>d<\/code> et <code>g<\/code> sont tri\u00e9s.<\/p>\n<\/li>\n<\/ul>\n<p><img decoding=\"async\" src=\"https:\/\/9h15.net\/activ\/wp-content\/uploads\/2022\/02\/4-1.png\" alt=\"4\" \/><\/p>\n<p>La fonction <code>insert<\/code> permet d\u2019ins\u00e9rer une valeur dans un arbre tri\u00e9. Si <code>t<\/code> est un arbre tri\u00e9 et <code>x<\/code> un entier, alors <code>insert x t<\/code> produit un arbre tri\u00e9 contenant <code>x<\/code> et les valeurs de <code>t<\/code>.<\/p>\n<pre><code class=\"language-ocaml\">let rec insert x t = match t with\n  |Vide-&gt;Noeud(x,Vide,Vide);\n  |Noeud(y,g,d)-&gt;if x&lt;y \n      then Noeud(y, insert x g, d)\n      else Noeud(y, g, insert x d)\n;;\n<\/code><\/pre>\n<p>Donnez la ligne de code permettant de produire l\u2019arbre repr\u00e9sent\u00e9 par la figure pr\u00e9c\u00e9dente par insertion des valeurs des \u00e9tiquettes dans l\u2019ordre appropri\u00e9 \u00e0 l\u2019aide de la fonction <code>insert<\/code>.<\/p>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;R\u00e9ponse&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<pre><code class=\"language-ocaml\">let t = insert 7 (insert 3 (insert 2 (insert 5 Vide)));;\n<\/code><\/pre>\n<p><\/div>\n\t\t\t<\/div>\n<h3><a id=\"b4-2-points\" class=\"anchor\" aria-hidden=\"true\"><span class=\"octicon octicon-link\"><\/span><\/a>B4 (2 points)<\/h3>\n<p>R\u00e9alisez une fonction <code>liste2arbre<\/code> telle que si <code>w<\/code> est une liste d\u2019entiers, alors <code>liste2arbre w<\/code> produit un arbre tri\u00e9 contenant tous les \u00e9l\u00e9ments de <code>w<\/code>. L\u2019arbre est produit par insertions successives, \u00e0 l\u2019aide de la fonction <code>insert<\/code>, des \u00e9l\u00e9ments de <code>w<\/code> dans un arbre initialement vide.<\/p>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;R\u00e9ponse&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<pre><code class=\"language-ocaml\">let rec liste2arbre w =\n  match w with\n  |[] -&gt; Vide\n  |x::q -&gt; insert x (liste2arbre q)\n;;\n<\/code><\/pre>\n<p><\/div>\n\t\t\t<\/div>\n<h3><a id=\"b5-2-points\" class=\"anchor\" aria-hidden=\"true\"><span class=\"octicon octicon-link\"><\/span><\/a>B5 (2 points)<\/h3>\n<p>R\u00e9alisez une fonction <code>arbre2liste<\/code> telle que si <code>t<\/code> est un arbre tri\u00e9 alors <code>arbre2liste t<\/code> retourne la liste tri\u00e9e des valeurs situ\u00e9es dans <code>t<\/code>.<\/p>\n<p>Par exemple, <code>arbre2liste (liste2arbre [5; 1; 7; 4; 2; 6])<\/code> produit le r\u00e9sultat <code>[1;2;4;5;6;7]<\/code>.<\/p>\n<p>Vous pouvez utiliser l\u2019op\u00e9rateur <code>@<\/code> de concat\u00e9nation des listes. Par exemple <code>[1;2]@[3;4]<\/code> a pour r\u00e9sultat <code>[1;2;3;4]<\/code>.<\/p>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;R\u00e9ponse&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<pre><code class=\"language-ocaml\">let rec arbre2liste t =\n  match t with\n  |Vide -&gt; []\n  |Noeud(x,g,d) -&gt; \n      (arbre2liste g) @ x::(arbre2liste d)\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. Sujet de devoir surveill\u00e9 de 2021 Lambda-calcul A1 (1.5 points) D\u00e9composez le terme suivant en abstractions (encadrez-les en pointill\u00e9s) et applications (encadrez-les en trait plein). \\[a \\; b \\; \\lambda x . \\; \\lambda y . \\; x \\; a \\; y \\; \\lambda [&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-213","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\/213","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=213"}],"version-history":[{"count":1,"href":"https:\/\/9h15.net\/activ\/wp-json\/wp\/v2\/posts\/213\/revisions"}],"predecessor-version":[{"id":214,"href":"https:\/\/9h15.net\/activ\/wp-json\/wp\/v2\/posts\/213\/revisions\/214"}],"wp:attachment":[{"href":"https:\/\/9h15.net\/activ\/wp-json\/wp\/v2\/media?parent=213"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/9h15.net\/activ\/wp-json\/wp\/v2\/categories?post=213"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/9h15.net\/activ\/wp-json\/wp\/v2\/tags?post=213"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}