td11-dico.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "source": [
    "# Dictionnaires"
   ],
   "metadata": {}
  },
  {
   "cell_type": "markdown",
   "source": [
    "## Structures et opérations élémentaires"
   ],
   "metadata": {}
  },
  {
   "cell_type": "markdown",
   "source": [
    "### Exercice 1"
   ],
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "source": [
    "type ('a, 'b) table = {data : ('a * 'b) list array; hash : 'a -> int}"
   ],
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": [
       "type ('a, 'b) table = { data : ('a * 'b) list array; hash : 'a -> int; }\n"
      ]
     },
     "metadata": {},
     "execution_count": 5
    }
   ],
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "source": [
    "let rec set_list (k, v) u = \r\n",
    "   match u with\r\n",
    "  |[]-> [(k,v)]\r\n",
    "  |(p,m)::r when p=k -> set_list (k,v) r\r\n",
    "  |x::r-> x::(set_list (k,v) r) ;;"
   ],
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": [
       "val set_list : 'a * 'b -> ('a * 'b) list -> ('a * 'b) list = <fun>\n"
      ]
     },
     "metadata": {},
     "execution_count": 6
    }
   ],
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "source": [
    "let rec get_list k u = match u with\r\n",
    "    |[] -> None\r\n",
    "    |(p,m)::r when p = k -> Some m\r\n",
    "    |x::r -> get_list k r ;;"
   ],
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": [
       "val get_list : 'a -> ('a * 'b) list -> 'b option = <fun>\n"
      ]
     },
     "metadata": {},
     "execution_count": 7
    }
   ],
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "source": [
    "let rec rem_list k u =  match u with\r\n",
    "    |[] -> []\r\n",
    "    |(p,m)::r when p = k -> r\r\n",
    "    |x::r -> x::(rem_list k r) ;;"
   ],
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": [
       "val rem_list : 'a -> ('a * 'b) list -> ('a * 'b) list = <fun>\n"
      ]
     },
     "metadata": {},
     "execution_count": 8
    }
   ],
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "source": [
    "let test_exo1 () =\r\n",
    "  let u =\r\n",
    "    [(12, 35); (1, 43); (10, 30)]\r\n",
    "    |> set_list (17, 24)\r\n",
    "    |> set_list (1, 42)\r\n",
    "    |> rem_list 10 in\r\n",
    "  assert (get_list 10 u = None\r\n",
    "          && get_list 12 u = Some 35\r\n",
    "          && get_list 1 u = Some 42\r\n",
    "          && get_list 17 u = Some 24)"
   ],
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": [
       "val test_exo1 : unit -> unit = <fun>\n"
      ]
     },
     "metadata": {},
     "execution_count": 9
    }
   ],
   "metadata": {}
  },
  {
   "cell_type": "markdown",
   "source": [
    "### Exercice 2"
   ],
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "source": [
    "let empty_table n f = { data = Array.make n [] ; hash = f }"
   ],
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": [
       "val empty_table : int -> ('a -> int) -> ('a, 'b) table = <fun>\n"
      ]
     },
     "metadata": {},
     "execution_count": 10
    }
   ],
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "source": [
    "let get k {data = t; hash = f} = get_list k t.(f k mod (Array.length t)) ;;"
   ],
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": [
       "val get : 'a -> ('a, 'b) table -> 'b option = <fun>\n"
      ]
     },
     "metadata": {},
     "execution_count": 11
    }
   ],
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "source": [
    "let set (k, v) {data = t; hash = f} = t.(f k mod (Array.length t)) <- set_list (k,v) t.(f k mod (Array.length t)) ;;"
   ],
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": [
       "val set : 'a * 'b -> ('a, 'b) table -> unit = <fun>\n"
      ]
     },
     "metadata": {},
     "execution_count": 12
    }
   ],
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "source": [
    "let rem k {data = t; hash = f} = t.(f k) <- rem_list k t.(f k mod (Array.length t))"
   ],
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": [
       "val rem : 'a -> ('a, 'b) table -> unit = <fun>\n"
      ]
     },
     "metadata": {},
     "execution_count": 13
    }
   ],
   "metadata": {}
  },
  {
   "cell_type": "markdown",
   "source": [
    "### Exercice 3"
   ],
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "source": [
    "let from_list u n f = let t = Array.make n [] in List.iter ( fun (k,v) -> t.(f k) <- (k,v)::t.(f k)) u ;\r\n",
    "    {data = t ; hash = f} ;;"
   ],
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": [
       "val from_list : ('a * 'b) list -> int -> ('a -> int) -> ('a, 'b) table =\n",
       "  <fun>\n"
      ]
     },
     "metadata": {},
     "execution_count": 14
    }
   ],
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "source": [
    "let items { data = t ; hash = f} =\r\n",
    "    let a =  ref [] in \r\n",
    "    for c = 0 to Array.length t -1 do \r\n",
    "        a := t.(c) @ (!a) \r\n",
    "    done ; !a ;;"
   ],
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": [
       "val items : ('a, 'b) table -> ('a * 'b) list = <fun>\n"
      ]
     },
     "metadata": {},
     "execution_count": 15
    }
   ],
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "source": [
    "let keys { data = t ; hash = f} =\r\n",
    "    let a = ref []\r\n",
    "    in for c = 0 to Array.length t -1 do\r\n",
    "        match t.(c) with \r\n",
    "        |[]->()\r\n",
    "        |(k,v)::r -> a:= k::(!a)\r\n",
    "    done ; !a ;;"
   ],
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": [
       "val keys : ('a, 'b) table -> 'a list = <fun>\n"
      ]
     },
     "metadata": {},
     "execution_count": 16
    }
   ],
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "source": [
    "let items { data = t ; hash = f} = (* par construction il n'y a pas de doublons de v*)\r\n",
    "    let a = ref []\r\n",
    "    in let c = ref 0\r\n",
    "    in while !c < Array.length t -1 do\r\n",
    "        match t.(!c) with \r\n",
    "        |[]-> c:= !c+1\r\n",
    "        |(k,v)::r -> a:= (k,v) :: !a\r\n",
    "    done ; !a ;;"
   ],
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": [
       "val items : ('a, 'b) table -> ('a * 'b) list = <fun>\n"
      ]
     },
     "metadata": {},
     "execution_count": 17
    }
   ],
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "source": [
    "let rec card { data = t ; hash = f} = \r\n",
    "    let c = ref 0 in\r\n",
    "    for k = 0 to Array.length t -1 do\r\n",
    "        c:= !c + List.length t.(k)\r\n",
    "    done ; !c ;;"
   ],
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": [
       "val card : ('a, 'b) table -> int = <fun>\n"
      ]
     },
     "metadata": {},
     "execution_count": 18
    }
   ],
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "source": [
    "let test_exo3 () =\r\n",
    "  let u = [(1, 10); (2, 20); (3, 30)] in\r\n",
    "  let t = from_list u 3 Hashtbl.hash in\r\n",
    "  set (4, 40) t;\r\n",
    "  rem 2 t;\r\n",
    "  rem 7 t;\r\n",
    "  set (0, 50) t; \r\n",
    "  assert (List.sort compare (items t) = [(0, 50); (1, 10); (3, 30); (4, 40)])"
   ],
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": [
       "val test_exo3 : unit -> unit = <fun>\n"
      ]
     },
     "metadata": {},
     "execution_count": 19
    }
   ],
   "metadata": {}
  },
  {
   "cell_type": "markdown",
   "source": [
    "## Applications"
   ],
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "source": [
    "#require \"str\""
   ],
   "outputs": [
    {
     "output_type": "stream",
     "name": "stderr",
     "text": [
      "/home/opam/.opam/4.08.1+flambda/lib/ocaml/str.cma: loaded\n"
     ]
    }
   ],
   "metadata": {}
  },
  {
   "cell_type": "markdown",
   "source": [
    "### Exercice 4"
   ],
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "source": [
    "let texte_exemple =\r\n",
    "  \"Ceci est un texte. Un exemple de texte. \r\n",
    "Texte ! Oui, un joli texte en exemple...\"\r\n",
    "\r\n",
    "let gatsby =\r\n",
    "  \"Most of the big shore places were closed now and there were hardly any\r\n",
    "lights except the shadowy, moving glow of a ferryboat across the Sound.\r\n",
    "And as the moon rose higher the inessential houses began to melt away\r\n",
    "until gradually I became aware of the old island here that flowered\r\n",
    "once for Dutch sailors' eyes--a fresh, green breast of the new world.\r\n",
    "Its vanished trees, the trees that had made way for Gatsby's house, had\r\n",
    "once pandered in whispers to the last and greatest of all human dreams;\r\n",
    "for a transitory enchanted moment man must have held his breath in the\r\n",
    "presence of this continent, compelled into an aesthetic contemplation\r\n",
    "he neither understood nor desired, face to face for the last time in\r\n",
    "history with something commensurate to his capacity for wonder.\r\n",
    "\r\n",
    "And as I sat there brooding on the old, unknown world, I thought of\r\n",
    "Gatsby's wonder when he first picked out the green light at the end of\r\n",
    "Daisy's dock. He had come a long way to this blue lawn and his dream must\r\n",
    "have seemed so close that he could hardly fail to grasp it. He did not\r\n",
    "know that it was already behind him, somewhere back in that vast obscurity\r\n",
    "beyond the city, where the dark fields of the republic rolled on under\r\n",
    "the night.\r\n",
    "\r\n",
    "Gatsby believed in the green light, the orgastic future that year by\r\n",
    "year recedes before us. It eluded us then, but that's no matter--tomorrow\r\n",
    "we will run faster, stretch out our arms farther. . . . And one fine\r\n",
    "morning----\r\n",
    "\r\n",
    "So we beat on, boats against the current, borne back ceaselessly into\r\n",
    "the past.\""
   ],
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": [
       "val texte_exemple : string =\n",
       "  \"Ceci est un texte. Un exemple de texte. \\nTexte ! Oui, un joli texte en exemple...\"\n"
      ]
     },
     "metadata": {},
     "execution_count": 21
    },
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": [
       "val gatsby : string =\n",
       "  \"Most of the big shore places were closed now and there were hardly any\\nlights except the shadowy, moving glow of a ferryboat across the Sound.\\nAnd as the moon rose higher the inessential houses began to melt away\\nuntil gradually I became aware of the old island here that flowered\\nonce for Dutch sai\"... (* string length 1516; truncated *)\n"
      ]
     },
     "metadata": {},
     "execution_count": 21
    }
   ],
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "source": [
    "let liste_mots texte = \r\n",
    "  let temp = Str.split (Str.regexp \"[- ,?;.:!\\n]+\") texte in \r\n",
    "  List.map String.lowercase_ascii temp"
   ],
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": [
       "val liste_mots : string -> string list = <fun>\n"
      ]
     },
     "metadata": {},
     "execution_count": 22
    }
   ],
   "metadata": {}
  },
  {
   "cell_type": "markdown",
   "source": [
    "#### Questions"
   ],
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "source": [
    "let avec_positions liste_mots =\r\n",
    "    let rec aux u v s = match u with\r\n",
    "        |[] -> v\r\n",
    "        |x::r -> aux r ((x,s)::v) (s+1)\r\n",
    "    in List.rev (aux liste_mots [] 1)  ;;"
   ],
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": [
       "val avec_positions : 'a list -> ('a * int) list = <fun>\n"
      ]
     },
     "metadata": {},
     "execution_count": 23
    }
   ],
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "source": [
    "let ajoute index (mot, pos) = (* on parcourt, si on a rien trouvé c'est qu'il n'y a pas d'associations déjà présentes*)\r\n",
    "    let trouve = ref false in\r\n",
    "    for c = 0 to Array.length index.data -1 do \r\n",
    "    match index.data.(c) with\r\n",
    "    |[] -> if !trouve then () else index.data.(c) <- [(mot , [pos] )]\r\n",
    "    |[(p,m)] when p = mot -> index.data.(c) <- [(mot , pos ::m)]\r\n",
    "    |_::_ -> failwith \"error\"\r\n",
    "    done ;;\r\n",
    "    "
   ],
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": [
       "val ajoute : ('a, 'b list) table -> 'a * 'b -> unit = <fun>\n"
      ]
     },
     "metadata": {},
     "execution_count": 39
    }
   ],
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "source": [
    "let cree_index texte =\r\n",
    "    let u = avec_positions (liste_mots texte) in\r\n",
    "    let t = {data = Array.make (List.length u) [] ; hash = (fun a -> a )} in\r\n",
    "    aux u t ;;\r\n"
   ],
   "outputs": [
    {
     "output_type": "error",
     "ename": "error",
     "evalue": "compile_error",
     "traceback": [
      "File \"[42]\", line 4, characters 10-11:\n4 |     aux u t ;;\n              ^\nError: This expression has type (int, 'a) table\n       but an expression was expected of type (string, int list) table\n       Type int is not compatible with type string \n"
     ]
    }
   ],
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "source": [
    " let rec aux u t = match u with\r\n",
    "        |[]-> t.data\r\n",
    "        |x::r -> ajoute t x ; aux r t ;;"
   ],
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": [
       "val aux : ('a * 'b) list -> ('a, 'b list) table -> ('a * 'b list) list array =\n",
       "  <fun>\n"
      ]
     },
     "metadata": {},
     "execution_count": 41
    }
   ],
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "source": [
    "let par_occ texte =\r\n",
    "    let a = cree_index texte in let l = ref []  in \r\n",
    "    for c=0 to Array.length a.data do\r\n",
    "    let x,y = a.data.(c) in \r\n",
    "    l:= (x,List.length y) :: !l\r\n",
    "    done ; List.sort (fun (x,y) (a,b) -> y-b) l ;;"
   ],
   "outputs": [
    {
     "output_type": "error",
     "ename": "error",
     "evalue": "compile_error",
     "traceback": [
      "File \"[26]\", line 2, characters 12-22:\n2 |     let a = cree_index texte in let l = ref []  in \n                ^^^^^^^^^^\nError: Unbound value cree_index\n"
     ]
    }
   ],
   "metadata": {}
  },
  {
   "cell_type": "markdown",
   "source": [
    "### Exercice 5"
   ],
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "source": [
    "let inverse index =  \r\n",
    "    let rec l n u =\r\n",
    "     let c = ref 0 in while !c< Array.length t -1 do\r\n",
    "         (* on récupère le mot avec la n-ième occurence, on enlève le nombre de l'occurence de la liste, on remet la liste, on ajoute ce mot dans u, puis on\r\n",
    "         fait de manière terminale en renvoyant u si on a rien trouvé ie n est trop grand ie la fin de la phrase, du texte .. *)"
   ],
   "outputs": [
    {
     "output_type": "error",
     "ename": "error",
     "evalue": "compile_error",
     "traceback": [
      "File \"[27]\", line 2, characters 0-0:\nError: Syntax error\n"
     ]
    }
   ],
   "metadata": {}
  },
  {
   "cell_type": "markdown",
   "source": [
    "### Exercice 6"
   ],
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "source": [
    "let rec syr n = if n = 1 then 0 else \r\n",
    "    if n mod 2 = 0 then 1+ syr (n/2) \r\n",
    "        else 1+ syr (3*n+1) ;;"
   ],
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": [
       "val syr : int -> int = <fun>\n"
      ]
     },
     "metadata": {},
     "execution_count": 28
    }
   ],
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "source": [
    "let rec max_syr n = if n = 1 then 0 else max (syr n) (max_syr (n-1)) ;;"
   ],
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": [
       "val max_syr : int -> int = <fun>\n"
      ]
     },
     "metadata": {},
     "execution_count": 29
    }
   ],
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "source": [
    "let rec syr_mem n t = \r\n",
    "  failwith \"Pas implemente\""
   ],
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": [
       "val syr_mem : 'a -> 'b -> 'c = <fun>\n"
      ]
     },
     "metadata": {},
     "execution_count": 30
    }
   ],
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "source": [
    "let max_syr_mem n = \r\n",
    "  failwith \"Pas implemente\""
   ],
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": [
       "val max_syr_mem : 'a -> 'b = <fun>\n"
      ]
     },
     "metadata": {},
     "execution_count": 31
    }
   ],
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "source": [],
   "outputs": [],
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "source": [],
   "outputs": [],
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "source": [],
   "outputs": [],
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "source": [
    "\r\n"
   ],
   "outputs": [],
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "source": [],
   "outputs": [],
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "source": [],
   "outputs": [],
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "source": [],
   "outputs": [],
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "source": [],
   "outputs": [],
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "source": [],
   "outputs": [],
   "metadata": {}
  }
 ],
 "metadata": {
  "kernelspec": {
   "name": "python3",
   "display_name": "Python 3.6.12 64-bit ('Rain': conda)"
  },
  "language_info": {
   "codemirror_mode": "text/x-ocaml",
   "file_extension": ".ml",
   "mimetype": "text/x-ocaml",
   "name": "python",
   "nbconverter_exporter": null,
   "pygments_lexer": "OCaml",
   "version": "3.6.12"
  },
  "interpreter": {
   "hash": "d40da10f21f31fd42271ea583274926137a040a4d1ed6e52a4fd22df08a650b3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}