{
"cells": [
{
"cell_type": "markdown",
"metadata": {
"toc": "true"
},
"source": [
"# Table of Contents\n",
" "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# TP 1 - Programmation pour la préparation à l'agrégation maths option info\n",
"- En OCaml."
]
},
{
"cell_type": "code",
"execution_count": 12,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val print : ('a, out_channel, unit) format -> 'a = \n"
]
},
"execution_count": 12,
"metadata": {},
"output_type": "execute_result"
},
{
"name": "stdout",
"output_type": "stream",
"text": [
"The OCaml toplevel, version 4.04.2\n"
]
},
{
"data": {
"text/plain": [
"- : int = 0\n"
]
},
"execution_count": 12,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let print = Printf.printf;;\n",
"\n",
"Sys.command \"ocaml -version\";;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Fonctions"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exercice 4"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {
"scrolled": true
},
"outputs": [
{
"data": {
"text/plain": [
"val successeur : int -> int = \n"
]
},
"execution_count": 2,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let successeur (n : int) : int =\n",
" n + 1\n",
";;"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"- : int = 4\n"
]
},
"execution_count": 3,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : int = 5\n"
]
},
"execution_count": 3,
"metadata": {},
"output_type": "execute_result"
},
{
"name": "stdout",
"output_type": "stream",
"text": [
"\u001bM\u001bM\u001bM\u001bM\u001bM# successeur(3);;\n",
" successeur(2 * 2);;\n",
" successeur\u001b[4m(2.5)\u001b[24m;;\n",
"\u001b[24m\n",
"\n"
]
},
{
"ename": "error",
"evalue": "error",
"output_type": "error",
"traceback": [
"\u001b[31mFile \"[3]\", line 3, characters 10-15:\nError: This expression has type float but an expression was expected of type\n int\n\u001b[0m"
]
}
],
"source": [
"successeur(3);;\n",
"successeur(2 * 2);;\n",
"successeur(2.5);;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exercice 5"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val produit3 : int -> int -> int -> int = \n"
]
},
"execution_count": 4,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"val produit3_2 : int -> int -> int -> int = \n"
]
},
"execution_count": 4,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"val produit3_3 : int -> int -> int -> int = \n"
]
},
"execution_count": 4,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"val produit3_4 : int * int * int -> int = \n"
]
},
"execution_count": 4,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let produit3 (x : int) (y : int) (z : int) : int =\n",
" x * y * z\n",
";;\n",
"\n",
"let produit3_2 =\n",
" fun (x : int) (y : int) (z : int) : int ->\n",
" x * y * z\n",
";;\n",
"\n",
"let produit3_3 =\n",
" fun (x : int) ->\n",
" fun (y : int) ->\n",
" fun (z : int) : int ->\n",
" x * y * z\n",
";;\n",
"\n",
"let produit3_4 (tuple : (int * int * int)) : int =\n",
" let x, y, z = tuple in\n",
" x * y * z\n",
";;"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"- : int = 6\n"
]
},
"execution_count": 5,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : int = 6\n"
]
},
"execution_count": 5,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : int -> int = \n"
]
},
"execution_count": 5,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : int = 6\n"
]
},
"execution_count": 5,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : int = 6\n"
]
},
"execution_count": 5,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"produit3 1 2 3;;\n",
"produit3_2 1 2 3;;\n",
"(produit3_3 1)(2);; (* fun (z : int) -> int : 1 * 2 * z *)\n",
"((produit3_3 1)(2))(3);;\n",
"produit3_4 (1, 2, 3);;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exercice 6"
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val print : ('a, out_channel, unit) format -> 'a = \n"
]
},
"execution_count": 8,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"val exercice6 : int -> unit = \n"
]
},
"execution_count": 8,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let print = Printf.printf;;\n",
"\n",
"let exercice6 (n : int) : unit =\n",
" for i = 1 to n do\n",
" print \"%i\\n\" i;\n",
" done;\n",
" for i = n downto 1 do\n",
" print \"%i\\n\" i;\n",
" done;\n",
" flush_all ();\n",
";;"
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"1\n",
"2\n",
"3\n",
"4\n",
"4\n",
"3\n",
"2\n",
"1\n"
]
},
{
"data": {
"text/plain": [
"- : unit = ()\n"
]
},
"execution_count": 10,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"exercice6(4)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Récursivité"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exercice 7"
]
},
{
"cell_type": "code",
"execution_count": 13,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val factoriel : int -> int = \n"
]
},
"execution_count": 13,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"val factoriel : int -> int = \n"
]
},
"execution_count": 13,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"val factoriel : int -> int = \n"
]
},
"execution_count": 13,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"val factoriel : int -> int = \n"
]
},
"execution_count": 13,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let rec factoriel = function\n",
" | 0 -> 1\n",
" | n -> n * factoriel ( n - 1 );;\n",
"\n",
"let rec factoriel = fun n ->\n",
" match n with\n",
" | 0 -> 1\n",
" | n -> n * factoriel ( n - 1 );;\n",
"\n",
"let rec factoriel (n:int) : int =\n",
" match n with\n",
" | 0 -> 1\n",
" | n -> n * factoriel ( n - 1 );;\n",
"\n",
"let rec factoriel (n:int) : int =\n",
" if n = 0\n",
" then 1\n",
" else n * factoriel ( n - 1 );;"
]
},
{
"cell_type": "code",
"execution_count": 16,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"- : int = 24\n"
]
},
"execution_count": 16,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : int = 1\n"
]
},
"execution_count": 16,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : unit = ()\n"
]
},
"execution_count": 16,
"metadata": {},
"output_type": "execute_result"
},
{
"name": "stdout",
"output_type": "stream",
"text": [
"1! = 1\n",
"2! = 2\n",
"3! = 6\n",
"4! = 24\n",
"5! = 120\n",
"6! = 720\n",
"7! = 5040\n",
"8! = 40320\n"
]
},
{
"data": {
"text/plain": [
"- : unit = ()\n"
]
},
"execution_count": 16,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"factoriel 4;;\n",
"factoriel 0;;\n",
"\n",
"for i = 1 to 8 do\n",
" print \"%i! = %i\\n\" i (factoriel i)\n",
"done;;\n",
"flush_all ();;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exercice 8"
]
},
{
"cell_type": "code",
"execution_count": 17,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val pgcd : int -> int -> int = \n"
]
},
"execution_count": 17,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"(* Remarque: si a>b alors pgcd a b = pgcd (a-b) b *)\n",
"let rec pgcd (a : int) (b : int) : int =\n",
" if a = b\n",
" then a\n",
" else\n",
" if (a > b)\n",
" then pgcd (a-b) b\n",
" else pgcd a (b-a)\n",
";;"
]
},
{
"cell_type": "code",
"execution_count": 18,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"- : int = 16\n"
]
},
"execution_count": 18,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : int = 5\n"
]
},
"execution_count": 18,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"pgcd 16 1024;;\n",
"pgcd 25 130;;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Utilisons le générateur de nombres aléatoires pour faire quelques tests :"
]
},
{
"cell_type": "code",
"execution_count": 19,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"- : unit = ()\n"
]
},
"execution_count": 19,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"Random.self_init();;"
]
},
{
"cell_type": "code",
"execution_count": 20,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"- : unit = ()\n"
]
},
"execution_count": 20,
"metadata": {},
"output_type": "execute_result"
},
{
"name": "stdout",
"output_type": "stream",
"text": [
" 93 ^ 87 = 3\n",
" 91 ^ 54 = 1\n",
" 84 ^ 4 = 4\n",
" 32 ^ 99 = 1\n",
" 77 ^ 24 = 1\n",
" 83 ^ 22 = 1\n",
" 18 ^ 64 = 2\n",
" 77 ^ 20 = 1\n",
" 14 ^ 21 = 7\n",
" 80 ^ 72 = 8\n"
]
},
{
"data": {
"text/plain": [
"- : unit = ()\n"
]
},
"execution_count": 20,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"for _ = 1 to 10 do\n",
" let x = 1 + Random.int 100\n",
" and y = 1 + Random.int 100 in\n",
" let d = pgcd x y in\n",
" print \" %i ^ %i = %i\\n\" x y d;\n",
"done;;\n",
"flush_all ();;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exercice 9"
]
},
{
"cell_type": "code",
"execution_count": 21,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val fibonacci : int -> int = \n"
]
},
"execution_count": 21,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"(* fonction naive *)\n",
"let rec fibonacci (n : int) : int =\n",
" match n with\n",
" | 0 -> 1\n",
" | 1 -> 1\n",
" | n -> fibonacci (n-1) + fibonacci (n-2)\n",
";;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Avec ce morceau de code on peut facilement mesurer le temps d'exécution :"
]
},
{
"cell_type": "code",
"execution_count": 22,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val time : (unit -> 'a) -> 'a = \n"
]
},
"execution_count": 22,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let time (f : unit -> 'a) : 'a =\n",
" let t = Sys.time() in\n",
" let res = f () in\n",
" Printf.printf \" Temps en secondes: %fs\\n\" (Sys.time() -. t);\n",
" flush_all ();\n",
" res\n",
";;"
]
},
{
"cell_type": "code",
"execution_count": 23,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"- : int = 8\n"
]
},
"execution_count": 23,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : int = 2584\n"
]
},
"execution_count": 23,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"fibonacci 5;;\n",
"fibonacci 17;;"
]
},
{
"cell_type": "code",
"execution_count": 24,
"metadata": {
"scrolled": true
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
" Temps en secondes: 4.928000s\n"
]
},
{
"data": {
"text/plain": [
"- : int = 165580141\n"
]
},
"execution_count": 24,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"time (fun () -> fibonacci 40);;"
]
},
{
"cell_type": "code",
"execution_count": 26,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val fibonacci_lin : int -> int = \n"
]
},
"execution_count": 26,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let fibonacci_lin (n : int) : int =\n",
" (* invariant:\n",
" m >= 1\n",
" u = fibo(n-m+1)\n",
" v = fibo(n-m)\n",
" aux m u v = fibo(n) *)\n",
" let rec aux (m : int) (u : int) (v : int) : int =\n",
" assert (m>0);\n",
" if m = 1 then u\n",
" else aux (m-1) (u+v) u\n",
" in aux n 1 1\n",
";;"
]
},
{
"cell_type": "code",
"execution_count": 27,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"- : unit = ()\n"
]
},
"execution_count": 27,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"for i = 1 to 10 do\n",
" assert ((fibonacci i) = (fibonacci_lin i))\n",
"done;;"
]
},
{
"cell_type": "code",
"execution_count": 28,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"- : int = 14930352\n"
]
},
"execution_count": 28,
"metadata": {},
"output_type": "execute_result"
},
{
"name": "stdout",
"output_type": "stream",
"text": [
" Temps en secondes: 0.000000s\n"
]
}
],
"source": [
"time (fun () -> fibonacci_lin 35);;"
]
},
{
"cell_type": "code",
"execution_count": 29,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"- : int = 165580141\n"
]
},
"execution_count": 29,
"metadata": {},
"output_type": "execute_result"
},
{
"name": "stdout",
"output_type": "stream",
"text": [
" Temps en secondes: 0.000000s\n"
]
}
],
"source": [
"time (fun () -> fibonacci_lin 40);;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Voilà la différence."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exercice 10\n",
"\n",
"Aucune hypothèse n'est faite sur les arguments de la fonction, on supposera seulement qu'elle est itérable sur sa sortie."
]
},
{
"cell_type": "code",
"execution_count": 30,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val itere : ('a -> 'a) -> int -> 'a -> 'a = \n"
]
},
"execution_count": 30,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let rec itere (f : 'a -> 'a) (n : int) : 'a -> 'a =\n",
" match n with\n",
" | 0 -> (fun x -> x);\n",
" | n -> (fun x -> f (itere (f) (n - 1) x))\n",
";;"
]
},
{
"cell_type": "code",
"execution_count": 31,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"- : int = 11\n"
]
},
"execution_count": 31,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"(itere (fun x -> x + 1) 10)(1);;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exercice 11"
]
},
{
"cell_type": "code",
"execution_count": 33,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val print : ('a, out_channel, unit) format -> 'a = \n"
]
},
"execution_count": 33,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"val hanoi : int -> string -> string -> string -> unit = \n"
]
},
"execution_count": 33,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let print = Printf.printf;;\n",
"\n",
"let rec hanoi (n : int) (a : string) (b : string) (c : string) : unit =\n",
" if n > 1 then\n",
" hanoi (n-1) a c b;\n",
" print \"%s -> %s\\n\" a c;\n",
" if n > 1 then\n",
" hanoi (n-1) b a c;\n",
" flush_all ();\n",
";;"
]
},
{
"cell_type": "code",
"execution_count": 34,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"T1 -> T3\n"
]
},
{
"data": {
"text/plain": [
"- : unit = ()\n"
]
},
"execution_count": 34,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"hanoi 1 \"T1\" \"T2\" \"T3\";;"
]
},
{
"cell_type": "code",
"execution_count": 35,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"T1 -> T2\n",
"T1 -> T3\n",
"T2 -> T3\n"
]
},
{
"data": {
"text/plain": [
"- : unit = ()\n"
]
},
"execution_count": 35,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"hanoi 2 \"T1\" \"T2\" \"T3\";;"
]
},
{
"cell_type": "code",
"execution_count": 36,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"T1 -> T3\n",
"T1 -> T2\n",
"T3 -> T2\n",
"T1 -> T3\n",
"T2 -> T1\n",
"T2 -> T3\n",
"T1 -> T3\n",
"T1 -> T2\n",
"T3 -> T2\n",
"T3 -> T1\n",
"T2 -> T1\n",
"T3 -> T2\n",
"T1 -> T3\n",
"T1 -> T2\n",
"T3 -> T2\n",
"T1 -> T3\n",
"T2 -> T1\n",
"T2 -> T3\n",
"T1 -> T3\n",
"T2 -> T1\n",
"T3 -> T2\n",
"T3 -> T1\n",
"T2 -> T1\n",
"T2 -> T3\n",
"T1 -> T3\n",
"T1 -> T2\n",
"T3 -> T2\n",
"T1 -> T3\n",
"T2 -> T1\n",
"T2 -> T3\n",
"T1 -> T3\n"
]
},
{
"data": {
"text/plain": [
"- : unit = ()\n"
]
},
"execution_count": 36,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"hanoi 5 \"T1\" \"T2\" \"T3\";; (* 2^5 - 1 = 31 coups *)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Avec un compteur de coups joués (ce sera toujours $2^n - 1$) :"
]
},
{
"cell_type": "code",
"execution_count": 38,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val hanoi2 : int -> string -> string -> string -> int = \n"
]
},
"execution_count": 38,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let rec hanoi2 (n : int) (a : string) (b : string) (c : string) : int =\n",
" if n > 1 then begin\n",
" let coup = ref 0 in\n",
" coup := !coup + (hanoi2 (n-1) a c b);\n",
" print \"%s -> %s\\n\" a c;\n",
" coup := !coup + (hanoi2 (n-1) b a c);\n",
" flush_all ();\n",
" !coup + 1\n",
" end else begin\n",
" print \"%s -> %s\\n\" a c;\n",
" flush_all ();\n",
" 1;\n",
" end;\n",
";;"
]
},
{
"cell_type": "code",
"execution_count": 39,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"T1 -> T2\n",
"T1 -> T3\n",
"T2 -> T3\n"
]
},
{
"data": {
"text/plain": [
"- : int = 3\n"
]
},
"execution_count": 39,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"hanoi2 2 \"T1\" \"T2\" \"T3\";;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"----\n",
"# Listes\n",
"## Exercice 12\n",
"Les listes en Python sont des `list`.\n",
"Elles ne fonctionnent **pas** comme des listes simplement chaînées comme en Caml."
]
},
{
"cell_type": "code",
"execution_count": 40,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val concatenation : 'a list -> 'a list -> 'a list = \n"
]
},
"execution_count": 40,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let rec concatenation (l1 : 'a list) (l2 : 'a list) : 'a list =\n",
" match l1 with\n",
" | [] -> l2\n",
" | t :: q -> t :: (concatenation q l2)\n",
";;"
]
},
{
"cell_type": "code",
"execution_count": 41,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"- : int list = [1; 2; 3; 4; 5]\n"
]
},
"execution_count": 41,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"concatenation [1; 2; 3] [4; 5];;"
]
},
{
"cell_type": "code",
"execution_count": 42,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"- : int list = [1; 2; 3; 4; 5]\n"
]
},
"execution_count": 42,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"List.append [1; 2; 3] [4; 5];;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exercice 13"
]
},
{
"cell_type": "code",
"execution_count": 43,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val applique : ('a -> 'b) -> 'a list -> 'b list = \n"
]
},
"execution_count": 43,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let rec applique (f : 'a -> 'b) (liste : 'a list) : 'b list =\n",
" match liste with\n",
" | [] -> []\n",
" | t :: q -> (f t) :: (applique f q)\n",
";;"
]
},
{
"cell_type": "code",
"execution_count": 44,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"- : int list = [2; 3; 4]\n"
]
},
"execution_count": 44,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"applique (fun x -> x + 1) [1; 2; 3];;"
]
},
{
"cell_type": "code",
"execution_count": 45,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val plus_un_liste : int list -> int list = \n"
]
},
"execution_count": 45,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : int list = [2; 3; 4]\n"
]
},
"execution_count": 45,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let plus_un_liste = applique ((+) 1);;\n",
"plus_un_liste [1; 2; 3];; (* syntaxe sympa *)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exercice 14"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Avantage à la notation concise `applique f l` autorise à avoir `(applique f)(l)` au lieu de faire `fun l -> applique l f` si les deux arguments étaient dans l'autre sens."
]
},
{
"cell_type": "code",
"execution_count": 46,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val liste_carree : int list -> int list = \n"
]
},
"execution_count": 46,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let liste_carree = applique (fun x -> x*x);;"
]
},
{
"cell_type": "code",
"execution_count": 47,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"- : int list = [1; 4; 9]\n"
]
},
"execution_count": 47,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"liste_carree [1; 2; 3];;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exercice 15"
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val miroir_quad : 'a list -> 'a list = \n"
]
},
"execution_count": 1,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"val miroir_lin : 'a list -> 'a list = \n"
]
},
"execution_count": 1,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let rec miroir_quad : 'a list -> 'a list = function\n",
" | [] -> []\n",
" | a :: q -> (miroir_quad q) @ [a]\n",
";;\n",
"\n",
"let miroir_lin (liste : 'a list) : 'a list =\n",
" (* sous fonction utilisant un deuxieme argument d'accumulation du resultat *)\n",
" let rec miroir (l : 'a list) (accu : 'a list) : 'a list =\n",
" match l with\n",
" | [] -> accu\n",
" | a :: q -> miroir q (a::accu)\n",
" in\n",
" miroir liste []\n",
";;"
]
},
{
"cell_type": "code",
"execution_count": 49,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"- : int list = [3; 2; 1]\n"
]
},
"execution_count": 49,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : int list = [3; 2; 1]\n"
]
},
"execution_count": 49,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"miroir_quad [1; 2; 3];;\n",
"miroir_lin [1; 2; 3];;"
]
},
{
"cell_type": "code",
"execution_count": 50,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
" Temps en secondes: 0.000000s\n"
]
},
{
"data": {
"text/plain": [
"- : int list =\n",
"[20; 19; 18; 17; 16; 15; 14; 13; 12; 11; 10; 9; 8; 7; 6; 5; 4; 3; 2; 1]\n"
]
},
"execution_count": 50,
"metadata": {},
"output_type": "execute_result"
},
{
"name": "stdout",
"output_type": "stream",
"text": [
" Temps en secondes: 0.000000s\n"
]
},
{
"data": {
"text/plain": [
"- : int list =\n",
"[20; 19; 18; 17; 16; 15; 14; 13; 12; 11; 10; 9; 8; 7; 6; 5; 4; 3; 2; 1]\n"
]
},
"execution_count": 50,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"time (fun () -> miroir_quad [1;2;3;4;5;6;7;8;9;10;11;12;13;14;15;16;17;18;19;20]);;\n",
"time (fun () -> miroir_lin [1;2;3;4;5;6;7;8;9;10;11;12;13;14;15;16;17;18;19;20]);;\n",
"(* Pas de différence observable ici *)"
]
},
{
"cell_type": "code",
"execution_count": 51,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val longue_liste : int -> int list = \n"
]
},
"execution_count": 51,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let longue_liste (n : int) : int list =\n",
" Array.to_list (Array.init n (fun i -> i))\n",
";;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Avec de grandes listes, on voit la différence."
]
},
{
"cell_type": "code",
"execution_count": 52,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
" Temps en secondes: 1.220000s\n"
]
},
{
"data": {
"text/plain": [
"- : int list =\n",
"[9999; 9998; 9997; 9996; 9995; 9994; 9993; 9992; 9991; 9990; 9989; 9988;\n",
" 9987; 9986; 9985; 9984; 9983; 9982; 9981; 9980; 9979; 9978; 9977; 9976;\n",
" 9975; 9974; 9973; 9972; 9971; 9970; 9969; 9968; 9967; 9966; 9965; 9964;\n",
" 9963; 9962; 9961; 9960; 9959; 9958; 9957; 9956; 9955; 9954; 9953; 9952;\n",
" 9951; 9950; 9949; 9948; 9947; 9946; 9945; 9944; 9943; 9942; 9941; 9940;\n",
" 9939; 9938; 9937; 9936; 9935; 9934; 9933; 9932; 9931; 9930; 9929; 9928;\n",
" 9927; 9926; 9925; 9924; 9923; 9922; 9921; 9920; 9919; 9918; 9917; 9916;\n",
" 9915; 9914; 9913; 9912; 9911; 9910; 9909; 9908; 9907; 9906; 9905; 9904;\n",
" 9903; 9902; 9901; 9900; 9899; 9898; 9897; 9896; 9895; 9894; 9893; 9892;\n",
" 9891; 9890; 9889; 9888; 9887; 9886; 9885; 9884; 9883; 9882; 9881; 9880;\n",
" 9879; 9878; 9877; 9876; 9875; 9874; 9873; 9872; 9871; 9870; 9869; 9868;\n",
" 9867; 9866; 9865; 9864; 9863; 9862; 9861; 9860; 9859; 9858; 9857; 9856;\n",
" 9855; 9854; 9853; 9852; 9851; 9850; 9849; 9848; 9847; 9846; 9845; 9844;\n",
" 9843; 9842; 9841; 9840; 9839; 9838; 9837; 9836; 9835; 9834; 9833; 9832;\n",
" 9831; 9830; 9829; 9828; 9827; 9826; 9825; 9824; 9823; 9822; 9821; 9820;\n",
" 9819; 9818; 9817; 9816; 9815; 9814; 9813; 9812; 9811; 9810; 9809; 9808;\n",
" 9807; 9806; 9805; 9804; 9803; 9802; 9801; 9800; 9799; 9798; 9797; 9796;\n",
" 9795; 9794; 9793; 9792; 9791; 9790; 9789; 9788; 9787; 9786; 9785; 9784;\n",
" 9783; 9782; 9781; 9780; 9779; 9778; 9777; 9776; 9775; 9774; 9773; 9772;\n",
" 9771; 9770; 9769; 9768; 9767; 9766; 9765; 9764; 9763; 9762; 9761; 9760;\n",
" 9759; 9758; 9757; 9756; 9755; 9754; 9753; 9752; 9751; 9750; 9749; 9748;\n",
" 9747; 9746; 9745; 9744; 9743; 9742; 9741; 9740; 9739; 9738; 9737; 9736;\n",
" 9735; 9734; 9733; 9732; 9731; 9730; 9729; 9728; 9727; 9726; 9725; 9724;\n",
" 9723; 9722; 9721; 9720; 9719; 9718; 9717; 9716; 9715; 9714; 9713; 9712;\n",
" 9711; 9710; 9709; 9708; 9707; 9706; 9705; 9704; 9703; 9702; 9701; ...]\n"
]
},
"execution_count": 52,
"metadata": {},
"output_type": "execute_result"
},
{
"name": "stdout",
"output_type": "stream",
"text": [
" Temps en secondes: 0.000000s\n"
]
},
{
"data": {
"text/plain": [
"- : int list =\n",
"[9999; 9998; 9997; 9996; 9995; 9994; 9993; 9992; 9991; 9990; 9989; 9988;\n",
" 9987; 9986; 9985; 9984; 9983; 9982; 9981; 9980; 9979; 9978; 9977; 9976;\n",
" 9975; 9974; 9973; 9972; 9971; 9970; 9969; 9968; 9967; 9966; 9965; 9964;\n",
" 9963; 9962; 9961; 9960; 9959; 9958; 9957; 9956; 9955; 9954; 9953; 9952;\n",
" 9951; 9950; 9949; 9948; 9947; 9946; 9945; 9944; 9943; 9942; 9941; 9940;\n",
" 9939; 9938; 9937; 9936; 9935; 9934; 9933; 9932; 9931; 9930; 9929; 9928;\n",
" 9927; 9926; 9925; 9924; 9923; 9922; 9921; 9920; 9919; 9918; 9917; 9916;\n",
" 9915; 9914; 9913; 9912; 9911; 9910; 9909; 9908; 9907; 9906; 9905; 9904;\n",
" 9903; 9902; 9901; 9900; 9899; 9898; 9897; 9896; 9895; 9894; 9893; 9892;\n",
" 9891; 9890; 9889; 9888; 9887; 9886; 9885; 9884; 9883; 9882; 9881; 9880;\n",
" 9879; 9878; 9877; 9876; 9875; 9874; 9873; 9872; 9871; 9870; 9869; 9868;\n",
" 9867; 9866; 9865; 9864; 9863; 9862; 9861; 9860; 9859; 9858; 9857; 9856;\n",
" 9855; 9854; 9853; 9852; 9851; 9850; 9849; 9848; 9847; 9846; 9845; 9844;\n",
" 9843; 9842; 9841; 9840; 9839; 9838; 9837; 9836; 9835; 9834; 9833; 9832;\n",
" 9831; 9830; 9829; 9828; 9827; 9826; 9825; 9824; 9823; 9822; 9821; 9820;\n",
" 9819; 9818; 9817; 9816; 9815; 9814; 9813; 9812; 9811; 9810; 9809; 9808;\n",
" 9807; 9806; 9805; 9804; 9803; 9802; 9801; 9800; 9799; 9798; 9797; 9796;\n",
" 9795; 9794; 9793; 9792; 9791; 9790; 9789; 9788; 9787; 9786; 9785; 9784;\n",
" 9783; 9782; 9781; 9780; 9779; 9778; 9777; 9776; 9775; 9774; 9773; 9772;\n",
" 9771; 9770; 9769; 9768; 9767; 9766; 9765; 9764; 9763; 9762; 9761; 9760;\n",
" 9759; 9758; 9757; 9756; 9755; 9754; 9753; 9752; 9751; 9750; 9749; 9748;\n",
" 9747; 9746; 9745; 9744; 9743; 9742; 9741; 9740; 9739; 9738; 9737; 9736;\n",
" 9735; 9734; 9733; 9732; 9731; 9730; 9729; 9728; 9727; 9726; 9725; 9724;\n",
" 9723; 9722; 9721; 9720; 9719; 9718; 9717; 9716; 9715; 9714; 9713; 9712;\n",
" 9711; 9710; 9709; 9708; 9707; 9706; 9705; 9704; 9703; 9702; 9701; ...]\n"
]
},
"execution_count": 52,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let _ = time (fun () -> miroir_quad (longue_liste 10000));;\n",
"let _ = time (fun () -> miroir_lin (longue_liste 10000));;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exercice 16"
]
},
{
"cell_type": "code",
"execution_count": 53,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val insertionDansListeTriee : 'a list -> 'a -> 'a list = \n"
]
},
"execution_count": 53,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let rec insertionDansListeTriee (liste : 'a list) (x : 'a) : 'a list =\n",
" match liste with\n",
" | [] -> [x]\n",
" | t :: q when t < x -> t :: (insertionDansListeTriee q x)\n",
" | _ -> x :: liste (* x est plus petit que le plus petit de la liste *)\n",
";;"
]
},
{
"cell_type": "code",
"execution_count": 54,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"- : int list = [1; 2; 4; 5; 6]\n"
]
},
"execution_count": 54,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"insertionDansListeTriee [1; 2; 5; 6] 4;;"
]
},
{
"cell_type": "code",
"execution_count": 55,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val triInsertion : 'a list -> 'a list = \n"
]
},
"execution_count": 55,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let triInsertion (liste : 'a list) : 'a list =\n",
" let rec tri (l : 'a list) (accu : 'a list) : 'a list =\n",
" match l with\n",
" | [] -> accu\n",
" | t :: q -> tri q (insertionDansListeTriee accu t)\n",
" in\n",
" tri liste []\n",
";;"
]
},
{
"cell_type": "code",
"execution_count": 56,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"- : int list = [1; 2; 4; 5; 6]\n"
]
},
"execution_count": 56,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"triInsertion [5; 2; 6; 1; 4];;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exercice 17\n",
"\n",
"Pour un ordre, de type `ordre : 'a -> 'a -> 'a` :\n",
"- `x < y` $\\implies$ `ordre x y = -1`,\n",
"- `x = y` $\\implies$ `ordre x y = 0`,\n",
"- `x > y` $\\implies$ `ordre x y =1`."
]
},
{
"cell_type": "code",
"execution_count": 57,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"type 'a ordre = 'a -> 'a -> 'a\n"
]
},
"execution_count": 57,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"type 'a ordre = 'a -> 'a -> 'a;;"
]
},
{
"cell_type": "code",
"execution_count": 58,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val ordre_croissant : int ordre = \n"
]
},
"execution_count": 58,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"val ordre_decroissant : int ordre = \n"
]
},
"execution_count": 58,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let ordre_croissant : int ordre =\n",
" fun (x : int) (y : int) ->\n",
" match y with\n",
" | yv when yv = x -> 0\n",
" | yv when yv < x -> +1\n",
" | yv when yv > x -> -1\n",
" | _ -> failwith \"Erreur comparaison impossible (ordre_decroissant)\"\n",
";;\n",
"\n",
"let ordre_decroissant : int ordre =\n",
" fun (x : int) (y : int) ->\n",
" match y with\n",
" | yv when yv = x -> 0\n",
" | yv when yv < x -> -1\n",
" | yv when yv > x -> +1\n",
" | _ -> failwith \"Erreur comparaison impossible (ordre_decroissant)\"\n",
";;"
]
},
{
"cell_type": "code",
"execution_count": 59,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val insertionDansListeTrieeOrdre : int ordre -> int list -> int -> int list =\n",
" \n"
]
},
"execution_count": 59,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let rec insertionDansListeTrieeOrdre (ordre : 'a ordre) (liste : 'a list) (x : 'a) : 'a list =\n",
" match liste with\n",
" | [] -> [x]\n",
" | t :: q when (ordre t x < 0) -> t :: (insertionDansListeTrieeOrdre ordre q x)\n",
" | _ -> x :: liste (* x est plus petit que le plus petit de la liste *)\n",
";;"
]
},
{
"cell_type": "code",
"execution_count": 60,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"- : int list = [6; 5; 4; 2; 1; 2]\n"
]
},
"execution_count": 60,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"insertionDansListeTrieeOrdre ordre_decroissant [6; 5; 2; 1; 2] 4;;"
]
},
{
"cell_type": "code",
"execution_count": 61,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val triInsertionOrdre : int ordre -> int list -> int list = \n"
]
},
"execution_count": 61,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let triInsertionOrdre (ordre : 'a ordre) (liste : 'a list) : 'a list =\n",
" let rec tri (l : 'a list) (accu : 'a list) : 'a list =\n",
" match l with\n",
" | [] -> accu\n",
" | t :: q -> tri q (insertionDansListeTrieeOrdre ordre accu t)\n",
" in\n",
" tri liste []\n",
";;"
]
},
{
"cell_type": "code",
"execution_count": 62,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"- : int list = [6; 5; 4; 2; 1]\n"
]
},
"execution_count": 62,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"triInsertionOrdre ordre_decroissant [5; 2; 6; 1; 4];;"
]
},
{
"cell_type": "code",
"execution_count": 63,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"- : int list = [1; 2; 4; 5; 6]\n"
]
},
"execution_count": 63,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"triInsertionOrdre ordre_croissant [5; 2; 6; 1; 4];;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"----\n",
"# Exponentiation rapide\n",
"## Exercice 18"
]
},
{
"cell_type": "code",
"execution_count": 64,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val puiss : int -> int -> int = \n"
]
},
"execution_count": 64,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let rec puiss (x : int) : int -> int = function\n",
" | 0 -> 1\n",
" | n -> x * (puiss x (n-1))\n",
";;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Complexité** : linéaire ($\\mathcal{O}(x)$)..."
]
},
{
"cell_type": "code",
"execution_count": 67,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"- : unit = ()\n"
]
},
"execution_count": 67,
"metadata": {},
"output_type": "execute_result"
},
{
"name": "stdout",
"output_type": "stream",
"text": [
" 3 ** 0 = 1\n",
" 3 ** 1 = 3\n",
" 3 ** 2 = 9\n",
" 3 ** 3 = 27\n",
" 3 ** 4 = 81\n",
" 3 ** 5 = 243\n",
" 3 ** 6 = 729\n",
" 3 ** 7 = 2187\n",
" 3 ** 8 = 6561\n",
" 3 ** 9 = 19683\n",
" 3 ** 10 = 59049\n",
" 3 ** 0 = 1\n",
" 3 ** 1 = 3\n",
" 3 ** 2 = 9\n",
" 3 ** 3 = 27\n",
" 3 ** 4 = 81\n",
" 3 ** 5 = 243\n",
" 3 ** 6 = 729\n",
" 3 ** 7 = 2187\n",
" 3 ** 8 = 6561\n",
" 3 ** 9 = 19683\n",
" 3 ** 10 = 59049\n"
]
},
{
"data": {
"text/plain": [
"- : unit = ()\n"
]
},
"execution_count": 67,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let x = 3 in\n",
"for n = 0 to 10 do\n",
" print \" %i ** %i = %i\\n\" x n (puiss x n);\n",
"done;;\n",
"flush_all ();;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exercice 19"
]
},
{
"cell_type": "code",
"execution_count": 68,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val puissRapide : int -> int -> int = \n"
]
},
"execution_count": 68,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let rec puissRapide (x : int) : int -> int = function\n",
" | 0 -> 1\n",
" | n when (n mod 2) = 0 -> puissRapide (x * x) (n / 2)\n",
" | n -> (puissRapide (x * x) ((n-1)/2)) * x\n",
" (* Important de mettre * x à droite pour être récursive terminale. *)\n",
";;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Complexité** : logarithmique ($\\mathcal{O}(\\log_2 x)$)."
]
},
{
"cell_type": "code",
"execution_count": 69,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"- : unit = ()\n"
]
},
"execution_count": 69,
"metadata": {},
"output_type": "execute_result"
},
{
"name": "stdout",
"output_type": "stream",
"text": [
" 3 ** 0 = 1\n",
" 3 ** 1 = 3\n",
" 3 ** 2 = 9\n",
" 3 ** 3 = 27\n",
" 3 ** 4 = 81\n",
" 3 ** 5 = 243\n",
" 3 ** 6 = 729\n",
" 3 ** 7 = 2187\n",
" 3 ** 8 = 6561\n",
" 3 ** 9 = 19683\n",
" 3 ** 10 = 59049\n"
]
},
{
"data": {
"text/plain": [
"- : unit = ()\n"
]
},
"execution_count": 69,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let x = 3 in\n",
"for n = 0 to 10 do\n",
" print \" %i ** %i = %i\\n\" x n (puissRapide x n);\n",
"done;;\n",
"flush_all ();;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exercice 20"
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"type 'a monoide = { mult : 'a -> 'a -> 'a; neutre : 'a; }\n"
]
},
"execution_count": 1,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"(* le type monoide *)\n",
"type 'a monoide = { mult : 'a -> 'a -> 'a; neutre : 'a };;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Avec des champs d'enregistrement, c'est concis :"
]
},
{
"cell_type": "code",
"execution_count": 17,
"metadata": {},
"outputs": [
{
"name": "stderr",
"output_type": "stream",
"text": [
"File \"[17]\", line 3, characters 22-28:\n",
"Warning 10: this expression should have type unit.\n"
]
},
{
"ename": "error",
"evalue": "compile_error",
"output_type": "error",
"traceback": [
"\u001b[32mFile \"[17]\", line 5, characters 4-10:\n\u001b[31mError: Unbound value neutre\n\u001b[36m 4: \u001b[30m (* ce ; est quoi ? fin de fun ou fin de mult ? *)\n\u001b[36m 5: \u001b[30m \u001b[4mneutre\u001b[0m\u001b[30m = 1.0\n\u001b[36m 6: \u001b[30m}\u001b[0m\n"
]
}
],
"source": [
"(* Ca rale ici ! *)\n",
"let floatmonoide = {\n",
" mult = fun a b -> a *. b;\n",
" (* ce ; est quoi ? fin de fun ou fin de mult ? *)\n",
" neutre = 1.0\n",
"}"
]
},
{
"cell_type": "code",
"execution_count": 18,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val floatmonoide : float monoide = {mult = ; neutre = 1.}\n"
]
},
"execution_count": 18,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let floatmonoide = {\n",
" mult = (fun a b -> a *. b);\n",
" neutre = 1.0\n",
"}"
]
},
{
"cell_type": "code",
"execution_count": 19,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val floatMonoide : float monoide = {mult = ; neutre = 1.}\n"
]
},
"execution_count": 19,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let floatMonoide : 'float monoide = {\n",
" mult = ( *. ); (* fun x y -> x *. y *)\n",
" neutre = 1.\n",
"};;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Par contre, impossible d'avoir un neutre de taille quelconque donc on doit écrire un monoied pour les matrices qui soit dépendent d'une taille $n$."
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val mult_matrice : int array array -> int array array -> int array array =\n",
" \n"
]
},
"execution_count": 3,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let mult_matrice (x : int array array) (y : int array array) : int array array =\n",
" let n = Array.length x in\n",
" let z = Array.make_matrix n n 0 in\n",
" for i = 0 to n-1 do\n",
" for j = 0 to n-1 do\n",
" for k = 0 to n-1 do\n",
" z.(i).(j) <- z.(i).(j) + x.(i).(k) * y.(k).(j)\n",
" done\n",
" done\n",
" done;\n",
" z\n",
";;"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"- : int array array = [|[|4; 6|]; [|4; 6|]|]\n"
]
},
"execution_count": 4,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"mult_matrice [| [|1; 1|]; [|1; 1|]|] [|[|1; 2|]; [|3; 4|]|];;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Manuellement ce n'est pas trop dur :"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val matrixMonoide : int -> int array array monoide = \n"
]
},
"execution_count": 5,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let matrixMonoide n = {\n",
" mult = mult_matrice;\n",
" neutre = Array.init n (fun i -> Array.init n (fun j -> if i = j then 1 else 0));\n",
"};;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exercice 21\n",
"Première approche naïve :"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val exp_rapide : 'a monoide -> 'a -> int -> 'a = \n"
]
},
"execution_count": 6,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let rec exp_rapide (m : 'a monoide) (x : 'a) (n : int) : 'a =\n",
" match n with\n",
" | 0 -> m.neutre\n",
" | n -> m.mult (exp_rapide m x (n-1)) x\n",
";;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Avec l'approche récursive :"
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val exp_rapide : 'a monoide -> 'a -> int -> 'a = \n"
]
},
"execution_count": 10,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let rec exp_rapide (m : 'a monoide) (x : 'a) (n : int) : 'a =\n",
" match n with\n",
" | 0 -> m.neutre\n",
" | n when (n mod 2) = 0 -> exp_rapide m (m.mult x x) (n / 2)\n",
" | n -> m.mult (exp_rapide m (m.mult x x) ((n-1)/2)) x\n",
";;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exercice 22"
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val exp_rapide_float : float -> int -> float = \n"
]
},
"execution_count": 11,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let exp_rapide_float = exp_rapide floatMonoide;;"
]
},
{
"cell_type": "code",
"execution_count": 12,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"- : float = 256.\n"
]
},
"execution_count": 12,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"exp_rapide_float 2.0 8;;"
]
},
{
"cell_type": "code",
"execution_count": 13,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"- : float = 2.56000000000000217e-06\n"
]
},
"execution_count": 13,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"exp_rapide_float 0.2 8;;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Et pour les matrices, un petit piège à cause des tailles :"
]
},
{
"cell_type": "code",
"execution_count": 79,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val exp_rapide_mat : int array array -> int -> int array array = \n"
]
},
"execution_count": 79,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let exp_rapide_mat x n = exp_rapide (matrixMonoide (Array.length x)) x n;;"
]
},
{
"cell_type": "code",
"execution_count": 80,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"- : int array array = [|[|1; 0|]; [|0; 1|]|]\n"
]
},
"execution_count": 80,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : int array array = [|[|1; 1|]; [|1; 1|]|]\n"
]
},
"execution_count": 80,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : int array array = [|[|2; 2|]; [|2; 2|]|]\n"
]
},
"execution_count": 80,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : int array array = [|[|4; 4|]; [|4; 4|]|]\n"
]
},
"execution_count": 80,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : int array array = [|[|8; 8|]; [|8; 8|]|]\n"
]
},
"execution_count": 80,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"exp_rapide_mat [|[|1; 1|]; [|1; 1|]|] 0;;\n",
"exp_rapide_mat [|[|1; 1|]; [|1; 1|]|] 1;;\n",
"exp_rapide_mat [|[|1; 1|]; [|1; 1|]|] 2;;\n",
"exp_rapide_mat [|[|1; 1|]; [|1; 1|]|] 3;;\n",
"exp_rapide_mat [|[|1; 1|]; [|1; 1|]|] 4;;"
]
},
{
"cell_type": "code",
"execution_count": 81,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"- : int array array = [|[|1; 0; 0|]; [|0; 1; 0|]; [|0; 0; 1|]|]\n"
]
},
"execution_count": 81,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : int array array = [|[|0; 1; 2|]; [|0; 0; 1|]; [|0; 0; 0|]|]\n"
]
},
"execution_count": 81,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : int array array = [|[|0; 0; 1|]; [|0; 0; 0|]; [|0; 0; 0|]|]\n"
]
},
"execution_count": 81,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : int array array = [|[|0; 0; 0|]; [|0; 0; 0|]; [|0; 0; 0|]|]\n"
]
},
"execution_count": 81,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : int array array = [|[|0; 0; 0|]; [|0; 0; 0|]; [|0; 0; 0|]|]\n"
]
},
"execution_count": 81,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"(* nilpotente ! *)\n",
"exp_rapide_mat [|[|0; 1; 2|]; [|0; 0; 1|]; [|0; 0; 0|]|] 0;;\n",
"exp_rapide_mat [|[|0; 1; 2|]; [|0; 0; 1|]; [|0; 0; 0|]|] 1;;\n",
"exp_rapide_mat [|[|0; 1; 2|]; [|0; 0; 1|]; [|0; 0; 0|]|] 2;;\n",
"exp_rapide_mat [|[|0; 1; 2|]; [|0; 0; 1|]; [|0; 0; 0|]|] 3;;\n",
"exp_rapide_mat [|[|0; 1; 2|]; [|0; 0; 1|]; [|0; 0; 0|]|] 4;;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exercice 23"
]
},
{
"cell_type": "code",
"execution_count": 82,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val monoideFonction : ('a -> 'a) monoide = {mult = ; neutre = }\n"
]
},
"execution_count": 82,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"val itereMonoide : ('a -> 'a) -> int -> 'a -> 'a = \n"
]
},
"execution_count": 82,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let monoideFonction = {\n",
" mult = (fun f g x -> f (g x) );\n",
" neutre = (fun x -> x)\n",
"};;\n",
"\n",
"let itereMonoide f n = exp_rapide monoideFonction f n;;"
]
},
{
"cell_type": "code",
"execution_count": 83,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"- : int = 10\n"
]
},
"execution_count": 83,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : int = 10\n"
]
},
"execution_count": 83,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"itereMonoide (fun x -> x + 1) 10 0;;\n",
"itereMonoide ((+) 1) 10 0;;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"----\n",
"# Formule du calcul propositionnel\n",
"\n",
"## Exercice 24"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"type variable = string\n"
]
},
"execution_count": 2,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"type formule =\n",
" V of variable\n",
" | Non of formule\n",
" | Conj of formule * formule\n",
" | Disj of formule * formule\n"
]
},
"execution_count": 2,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"type variable = string;;\n",
"\n",
"type formule =\n",
" | V of variable\n",
" | Non of formule\n",
" | Conj of formule * formule\n",
" | Disj of formule * formule\n",
";;"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val f : formule =\n",
" Conj (Non (V \"p\"), Disj (Conj (V \"q\", Non (V \"p\")), Disj (V \"r\", V \"q\")))\n"
]
},
"execution_count": 3,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let f = (\n",
" Conj(\n",
" Non(V(\"p\")),\n",
" Disj(\n",
" Conj(V(\"q\"), Non(V(\"p\"))),\n",
" Disj(V(\"r\"), V(\"q\"))\n",
" )\n",
" )\n",
") ;;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exercice 25"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val taille : formule -> int = \n"
]
},
"execution_count": 4,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let rec taille : formule -> int = function\n",
" | V(_) -> 1\n",
" | Non(f) -> 1 + (taille f)\n",
" | Conj(f,g) -> 1 + (taille f) + (taille g)\n",
" | Disj(f,g) -> 1 + (taille f) + (taille g)\n",
";;"
]
},
{
"cell_type": "code",
"execution_count": 87,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"- : int = 11\n"
]
},
"execution_count": 87,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"taille f;;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exercice 26"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val formule_to_string : formule -> string = \n"
]
},
"execution_count": 5,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let rec formule_to_string : formule -> string = function\n",
" | V(p) -> p\n",
" | Non(f) -> \"non \"^(formule_to_string f)\n",
" | Conj(f,g) -> \"(\"^(formule_to_string f)^\" ^ \"^(formule_to_string g)^\")\"\n",
" | Disj(f,g) -> \"(\"^(formule_to_string f)^\" v \"^(formule_to_string g)^\")\"\n",
";;"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val print : ('a, out_channel, unit) format -> 'a = \n"
]
},
"execution_count": 6,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"val affiche : formule -> unit = \n"
]
},
"execution_count": 6,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let print = Printf.printf;;\n",
"\n",
"let affiche (f : formule) : unit =\n",
" print \"%s\\n\" (formule_to_string f);\n",
" flush_all ();\n",
";;"
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"(non p ^ ((q ^ non p) v (r v q)))\n"
]
},
{
"data": {
"text/plain": [
"- : unit = ()\n"
]
},
"execution_count": 7,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"affiche f;;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Et voilà. Pas si difficile non ?"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exercice 27\n",
"Les valeurs des variables seront données comme une fonction associant nom de variable à valeurs booléennes.\n",
"On a l'avantage de pouvoir mettre les valeurs par défaut à `true` ou `false` via la filtration."
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"type valuation = variable -> bool\n"
]
},
"execution_count": 8,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"val eval : valuation -> formule -> bool = \n"
]
},
"execution_count": 8,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"val valuFalse : valuation = \n"
]
},
"execution_count": 8,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"val valuTrue : valuation = \n"
]
},
"execution_count": 8,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"type valuation = variable -> bool;;\n",
"\n",
"let rec eval (v : valuation) : formule -> bool = function\n",
" | V(x) -> v(x)\n",
" | Non(f) -> not (eval v f)\n",
" | Conj(f,g) -> (eval v f) && (eval v g)\n",
" | Disj(f,g) -> (eval v f) || (eval v g)\n",
";;\n",
"\n",
"let valuFalse : valuation = function\n",
" | \"p\" -> true\n",
" | \"q\" -> false\n",
" | \"r\" -> false\n",
" | _ -> false\n",
";;\n",
"\n",
"let valuTrue : valuation = function\n",
" | \"p\" -> false\n",
" | \"q\" -> false\n",
" | \"r\" -> true\n",
" | _ -> false\n",
";;"
]
},
{
"cell_type": "code",
"execution_count": 93,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"- : bool = true\n"
]
},
"execution_count": 93,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"eval valuTrue f;;"
]
},
{
"cell_type": "code",
"execution_count": 94,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"- : bool = false\n"
]
},
"execution_count": 94,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"eval valuFalse f;;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exercice 28"
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val inserUneFois : 'a -> 'a list -> 'a list = \n"
]
},
"execution_count": 9,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let rec inserUneFois (x : 'a) : ('a list -> 'a list) = function\n",
" | [] -> [x]\n",
" | t :: q when (x = t) -> t :: q\n",
" | t :: q -> t :: (inserUneFois x q)\n",
";;"
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {
"scrolled": true
},
"outputs": [
{
"data": {
"text/plain": [
"val recupererVariable : formule -> variable list = \n"
]
},
"execution_count": 10,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let recupererVariable (f : formule) : variable list =\n",
" let rec recup (l : variable list) : formule -> variable list = function\n",
" | V(x) -> inserUneFois x l\n",
" | Non(f) -> recup l f\n",
" | Conj(f,g) -> recup (recup l f) g\n",
" | Disj(f,g) -> recup (recup l f) g\n",
" in\n",
" recup [] f\n",
";;"
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"- : variable list = [\"p\"; \"q\"; \"r\"]\n"
]
},
"execution_count": 11,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"recupererVariable f;;"
]
},
{
"cell_type": "code",
"execution_count": 12,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val nouvelleValu : valuation -> variable list -> valuation = \n"
]
},
"execution_count": 12,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let rec nouvelleValu (v : valuation) : 'a list -> valuation = function\n",
" | [] -> v\n",
" | t :: q ->\n",
" if (v t) then\n",
" let nv x = if (x = t) then false else v x in\n",
" nouvelleValu nv q\n",
" else function x ->\n",
" if (x = t) then true else v x\n",
";;"
]
},
{
"cell_type": "code",
"execution_count": 13,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val isTrue : valuation -> variable list -> bool = \n"
]
},
"execution_count": 13,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let rec isTrue (v : valuation) : variable list -> bool = function\n",
" | [] -> true\n",
" | t :: q -> if v t then isTrue v q else false\n",
";;"
]
},
{
"cell_type": "code",
"execution_count": 14,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val valuToString : valuation -> variable list -> string = \n"
]
},
"execution_count": 14,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let rec valuToString (v : valuation) : variable list -> string = function\n",
" | [] -> \"\"\n",
" | t :: q -> (if v t then \"1\" else \"0\") ^ \" \" ^ (valuToString v q)\n",
";;"
]
},
{
"cell_type": "code",
"execution_count": 17,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val print : ('a, out_channel, unit) format -> 'a = \n"
]
},
"execution_count": 17,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"val printVariableList : variable list -> unit = \n"
]
},
"execution_count": 17,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let print = Printf.printf;;\n",
"\n",
"let rec printVariableList : variable list -> unit = function\n",
" | [ ] -> print \"| \"\n",
" | t :: q ->\n",
" print \"%s \" t;\n",
" flush_all ();\n",
" printVariableList q\n",
";;"
]
},
{
"cell_type": "code",
"execution_count": 18,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val tableVerite : formule -> unit = \n"
]
},
"execution_count": 18,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let tableVerite (f : formule) : unit =\n",
" let variables = recupererVariable f in\n",
" let valu = ref (function _ -> false) in\n",
" (* on construit dynamiquement la nouvelle valuation... moche mais ça marche *)\n",
" printVariableList variables;\n",
" affiche f;\n",
" while not (isTrue (!valu) variables) do\n",
" print_string ( (valuToString (!valu) variables)^\"| \"^(if eval (!valu) f then \"1\" else \"0\")^\"\\n\");\n",
" valu := nouvelleValu (!valu) variables\n",
" done\n",
";;"
]
},
{
"cell_type": "code",
"execution_count": 19,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"p q r | (non p ^ ((q ^ non p) v (r v q)))\n"
]
},
{
"data": {
"text/plain": [
"- : unit = ()\n"
]
},
"execution_count": 19,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"tableVerite f;;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"> On peut vérifier, par exemple sur [Wolfram|Alpha](https%3A%2F%2Fwww.wolframalpha.com%2Finput%2F%3Fi%3D%28%7Ep%2B%2526%2B%28%28q%2B%2526%2B%7Ep%29%2B%257C%2B%28r%2B%257C%2Bq%29%29%29) que l'on obtient bien le bon résultat..."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"----\n",
"\n",
"# Conclusion\n",
"\n",
"Voilà pour aujourd'hui !\n",
"\n",
"Cette solution est aussi disponible en Python : [TP1__Python.ipynb](https://nbviewer.jupyter.org/github/Naereen/notebooks/tree/master/agreg/TP_Programmation_2017-18/TP1__Python.ipynb/).\n",
"\n",
"Là où Caml excelle pour les types définis, le filtrage et la récursion, Python gagne en simplicité sur l'affichage, sa librairie standard et les dictionnaires et ensembles..."
]
}
],
"metadata": {
"kernelspec": {
"display_name": "OCaml 4.04.2",
"language": "OCaml",
"name": "ocaml-jupyter"
},
"language_info": {
"codemirror_mode": "text/x-ocaml",
"file_extension": ".ml",
"mimetype": "text/x-ocaml",
"name": "OCaml",
"nbconverter_exporter": null,
"pygments_lexer": "OCaml",
"version": "4.04.2"
},
"toc": {
"colors": {
"hover_highlight": "#DAA520",
"running_highlight": "#FF0000",
"selected_highlight": "#FFD700"
},
"moveMenuLeft": true,
"nav_menu": {
"height": "365px",
"width": "251px"
},
"navigate_menu": true,
"number_sections": true,
"sideBar": true,
"threshold": 4,
"toc_cell": true,
"toc_position": {
"height": "523px",
"left": "0px",
"right": "1068px",
"top": "116px",
"width": "212px"
},
"toc_section_display": "block",
"toc_window_display": true
},
"varInspector": {
"cols": {
"lenName": 16,
"lenType": 16,
"lenVar": 40
},
"kernels_config": {
"python": {
"delete_cmd_postfix": "",
"delete_cmd_prefix": "del ",
"library": "var_list.py",
"varRefreshCmd": "print(var_dic_list())"
},
"r": {
"delete_cmd_postfix": ") ",
"delete_cmd_prefix": "rm(",
"library": "var_list.r",
"varRefreshCmd": "cat(var_dic_list()) "
}
},
"types_to_exclude": [
"module",
"function",
"builtin_function_or_method",
"instance",
"_Feature"
],
"window_display": false
}
},
"nbformat": 4,
"nbformat_minor": 2
}