Benchmarks for Example Driven Synthesis.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "23cc572a",
   "metadata": {},
   "source": [
    "## Lists"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "df81f5b3",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val is_empty : 'a list -> string = <fun>\n"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Not empty\n",
      "Not empty\n",
      "Empty\n"
     ]
    }
   ],
   "source": [
    "(* is_empty *)\n",
    "\n",
    "let is_empty lst =\n",
    "  match lst with\n",
    "  | [] -> \"Empty\"\n",
    "  | _ -> \"Not empty\";;\n",
    "\n",
    "let () =\n",
    "  let print_result lst =\n",
    "    let res = is_empty lst in\n",
    "    Printf.printf \"%s\\n\" res\n",
    "  in\n",
    "  print_result [1; 2; 3; 4];    (* prints \"Not empty\" *)\n",
    "  print_result [2; 5];           (* prints \"Not empty\" *)\n",
    "  print_result [];                (* prints \"Empty\" *)\n",
    "  flush stdout"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "37b107e1",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val is_member : 'a list -> 'a -> string = <fun>\n"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Is a Member\n",
      "Is a Member\n",
      "Not a Member\n",
      "Not a Member\n"
     ]
    }
   ],
   "source": [
    "(* is_member *)\n",
    "\n",
    "let is_member lst elem =\n",
    "  if List.mem elem lst then\n",
    "    \"Is a Member\"\n",
    "  else\n",
    "    \"Not a Member\";;\n",
    "\n",
    "let () =\n",
    "  let print_result lst elem =\n",
    "    let res = is_member lst elem in\n",
    "    Printf.printf \"%s\\n\" res\n",
    "  in\n",
    "  print_result [1; 2; 3; 4; 7] 7;   (* prints \"Is a Member\" *)\n",
    "  print_result [2; 5] 2;             (* prints \"Is a Member\" *)\n",
    "  print_result [3; 4] 5;             (* prints \"Not a Member\" *)\n",
    "  print_result [] 1;                  (* prints \"Not a Member\" *)\n",
    "  flush stdout"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "774a1106",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val duplicate_elements : 'a list -> 'a list = <fun>\n"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1; 1; 2; 2; 3; 3; 4; 4\n",
      "\n"
     ]
    }
   ],
   "source": [
    "(* duplicate_each_element *)\n",
    "\n",
    "let duplicate_elements lst =\n",
    "  List.flatten (List.map (fun x -> [x; x]) lst);;\n",
    "\n",
    "let () =\n",
    "  let print_result lst =\n",
    "    let res = duplicate_elements lst in\n",
    "    Printf.printf \"%s\\n\" (String.concat \"; \" (List.map string_of_int res))\n",
    "  in\n",
    "  print_result [1; 2; 3; 4];   (* prints \"1; 1; 2; 2; 3; 3; 4; 4\" *)\n",
    "  print_result [];              (* prints \"\" *)\n",
    "  flush stdout"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "d44b786f",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val repeat_elements : 'a list -> int -> 'a list = <fun>\n"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1; 1; 1; 1; 2; 2; 2; 2\n",
      "\n",
      "4\n"
     ]
    }
   ],
   "source": [
    "(* replicate *)\n",
    "\n",
    "let repeat_elements lst n =\n",
    "  List.flatten (List.map (fun x -> List.init n (fun _ -> x)) lst);;\n",
    "\n",
    "let () =\n",
    "  let print_result lst n =\n",
    "    let res = repeat_elements lst n in\n",
    "    Printf.printf \"%s\\n\" (String.concat \"; \" (List.map string_of_int res))\n",
    "  in\n",
    "  print_result [1; 2] 4;    (* prints \"1; 1; 1; 1; 2; 2; 2; 2\" *)\n",
    "  print_result [] 2;         (* prints \"\" *)\n",
    "  print_result [4] 1;         (* prints \"4\" *)\n",
    "  flush stdout"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "7c7d55bd",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val concat_lists : 'a list -> 'a list -> 'a list = <fun>\n"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1; 2; 3; 4\n",
      "2; 4\n",
      "4; 2\n"
     ]
    }
   ],
   "source": [
    "(* append_lists *)\n",
    "\n",
    "let concat_lists lst1 lst2 = lst1 @ lst2;;\n",
    "\n",
    "let () =\n",
    "  let print_result lst1 lst2 =\n",
    "    let res = concat_lists lst1 lst2 in\n",
    "    Printf.printf \"%s\\n\" (String.concat \"; \" (List.map string_of_int res))\n",
    "  in\n",
    "  print_result [1; 2] [3; 4];    (* prints \"1; 2; 3; 4\" *)\n",
    "  print_result [] [2; 4];         (* prints \"2; 4\" *)\n",
    "  print_result [4] [2];            (* prints \"4; 2\" *)\n",
    "  flush stdout"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "e2983834",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val flatten_lists : 'a list list -> 'a list = <fun>\n"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1; 2; 3; 4\n",
      "2; 4; 6; 0; 2; 3\n",
      "4; 2; 1\n"
     ]
    }
   ],
   "source": [
    "(* concatenate_list_of_lists *)\n",
    "\n",
    "let flatten_lists lst = List.flatten lst;;\n",
    "\n",
    "let () =\n",
    "  let print_result lst =\n",
    "    let res = flatten_lists lst in\n",
    "    Printf.printf \"%s\\n\" (String.concat \"; \" (List.map string_of_int res))\n",
    "  in\n",
    "  print_result [[1; 2]; [3; 4]];     (* prints \"1; 2; 3; 4\" *)\n",
    "  print_result [[2;4;6];[0;2;3]];    (* prints \"2; 4; 6; 0; 2; 3\" *)\n",
    "  print_result [[4]; [2];[1]];        (* prints \"4; 2; 1\" *)\n",
    "  flush stdout;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "363175cf",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val take_elements : 'a list -> int -> 'a list = <fun>\n"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1; 2\n",
      "2; 4; 6; 0; 2\n",
      "List has less elements\n"
     ]
    }
   ],
   "source": [
    "(* take_first_n_elements *)\n",
    "\n",
    "let rec take_elements lst n =\n",
    "  if n <= 0 then []\n",
    "  else match lst with\n",
    "    | [] -> failwith \"List has less elements\"\n",
    "    | h::t -> h :: take_elements t (n - 1);;\n",
    "\n",
    "let () =\n",
    "  let print_result lst n =\n",
    "    try\n",
    "      let res = take_elements lst n in\n",
    "      Printf.printf \"%s\\n\" (String.concat \"; \" (List.map string_of_int res))\n",
    "    with Failure msg -> Printf.printf \"%s\\n\" msg\n",
    "  in\n",
    "  print_result [1; 2; 3; 4] 2;          (* prints \"1; 2\" *)\n",
    "  print_result [2; 4; 6; 0; 2; 3] 5;    (* prints \"2; 4; 6; 0; 2\" *)\n",
    "  print_result [4; 2; 1] 4;              (* prints \"List has less elements\" *)\n",
    "  flush stdout"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "5a3ee1ea",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val drop_elements : 'a list -> int -> 'a list = <fun>\n"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3; 4\n",
      "3\n",
      "\n",
      "List has less elements\n"
     ]
    }
   ],
   "source": [
    "(* drop_first_n_elements *)\n",
    "\n",
    "let rec drop_elements lst n =\n",
    "  if n <= 0 then lst\n",
    "  else match lst with\n",
    "    | [] -> failwith \"List has less elements\"\n",
    "    | _::t -> drop_elements t (n - 1);;\n",
    "\n",
    "let () =\n",
    "  let print_result lst n =\n",
    "    try\n",
    "      let res = drop_elements lst n in\n",
    "      Printf.printf \"%s\\n\" (String.concat \"; \" (List.map string_of_int res))\n",
    "    with Failure msg -> Printf.printf \"%s\\n\" msg\n",
    "  in\n",
    "  print_result [1; 2; 3; 4] 2;          (* prints \"3; 4\" *)\n",
    "  print_result [2; 4; 6; 0; 2; 3] 5;    (* prints \"3\" *)\n",
    "  print_result [2] 1;                    (* prints \"\" *)\n",
    "  print_result [4; 2; 1] 4;               (* prints \"List has less elements\" *)\n",
    "  flush stdout"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "43edf57c",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val remove_element : 'a list -> 'a -> 'a list = <fun>\n"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1; 3; 4\n",
      "Element Not in List\n",
      "Element Not in List\n",
      "2; 1\n"
     ]
    }
   ],
   "source": [
    "(* delete_value *)\n",
    "\n",
    "let rec remove_element lst x =\n",
    "  match lst with\n",
    "  | [] -> failwith \"Element Not in List\"\n",
    "  | h::t -> if h = x then t else h :: remove_element t x;;\n",
    "\n",
    "let () =\n",
    "  let print_result lst x =\n",
    "    try\n",
    "      let res = remove_element lst x in\n",
    "      Printf.printf \"%s\\n\" (String.concat \"; \" (List.map string_of_int res))\n",
    "    with Failure msg -> Printf.printf \"%s\\n\" msg\n",
    "  in\n",
    "  print_result [1; 2; 3; 4] 2;          (* prints \"1; 3; 4\" *)\n",
    "  print_result [2; 4; 6; 0; 2; 3] 5;    (* prints \"Element Not in List\" *)\n",
    "  print_result [] 1;                     (* prints \"Element Not in List\" *)\n",
    "  print_result [4; 2; 1] 4;               (* prints \"2; 1\" *)\n",
    "  flush stdout"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "327e028b",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val apply_to_all : ('a -> 'b) -> 'a list -> 'b list = <fun>\n"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2; 4; 6; 8\n",
      "2; 3; 4; 5\n"
     ]
    }
   ],
   "source": [
    "(* map *)\n",
    "\n",
    "let apply_to_all f lst = List.map f lst;;\n",
    "\n",
    "let () =\n",
    "  let print_result f lst =\n",
    "    let res = apply_to_all f lst in\n",
    "    Printf.printf \"%s\\n\" (String.concat \"; \" (List.map string_of_int res))\n",
    "  in\n",
    "  print_result (fun x -> x * 2) [1; 2; 3; 4];  (* prints \"2; 4; 6; 8\" *)\n",
    "  print_result (fun x -> x + 1) [1; 2; 3; 4];   (* prints \"2; 3; 4; 5\" *)\n",
    "  flush stdout"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "e23bd989",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val combine_lists : 'a list -> 'b list -> ('a * 'b) list = <fun>\n"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(1,5); (2,2); (3,3); (4,7)\n",
      "(1,2); (2,3)\n",
      "\n"
     ]
    }
   ],
   "source": [
    "(* zip *)\n",
    "\n",
    "let rec combine_lists lst1 lst2 =\n",
    "  match lst1, lst2 with\n",
    "  | [], _ | _, [] -> []\n",
    "  | h1::t1, h2::t2 -> (h1, h2) :: combine_lists t1 t2;;\n",
    "\n",
    "let () =\n",
    "  let print_result lst1 lst2 =\n",
    "    let res = combine_lists lst1 lst2 in\n",
    "    Printf.printf \"%s\\n\" \n",
    "      (String.concat \"; \" (List.map (fun (x, y) -> \"(\" ^ string_of_int x ^ \",\" ^ string_of_int y ^ \")\") res))\n",
    "  in\n",
    "  print_result [1; 2; 3; 4] [5; 2; 3; 7];  (* prints \"(1,5); (2,2); (3,3); (4,7)\" *)\n",
    "  print_result [1; 2; 3] [2; 3];            (* prints \"(1,2); (2,3)\" *)\n",
    "  print_result [] [2; 3];                    (* prints \"\" *)\n",
    "  flush stdout"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "3fe6723c",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val combine_with_func : 'a list -> 'b list -> ('a -> 'b -> 'c) -> 'c list =\n",
       "  <fun>\n"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "6; 4; 6; 11\n",
      "Hello1; World2\n"
     ]
    }
   ],
   "source": [
    "(* zip with function *)\n",
    "\n",
    "let rec combine_with_func lst1 lst2 f =\n",
    "  match lst1, lst2 with\n",
    "  | [], _ | _, [] -> []\n",
    "  | h1::t1, h2::t2 -> (f h1 h2) :: combine_with_func t1 t2 f;;\n",
    "\n",
    "let () =\n",
    "  let print_result_int f lst1 lst2 =\n",
    "    let res = combine_with_func lst1 lst2 f in\n",
    "    Printf.printf \"%s\\n\" (String.concat \"; \" (List.map string_of_int res))\n",
    "  in\n",
    "  let print_result_string f lst1 lst2 =\n",
    "    let res = combine_with_func lst1 lst2 f in\n",
    "    Printf.printf \"%s\\n\" (String.concat \"; \" res)\n",
    "  in\n",
    "  print_result_int (fun x y -> x + y) [1; 2; 3; 4] [5; 2; 3; 7];  (* prints \"6; 4; 6; 11\" *)\n",
    "  print_result_string (fun x y -> y ^ string_of_int x) [1; 2; 3] [\"Hello\"; \"World\"];   (* prints \"Hello1; World2\" *)\n",
    "  flush stdout"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "d038061f",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val cartesian_product : 'a list -> 'b list -> ('a * 'b) list = <fun>\n"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(a,1); (a,2); (b,1); (b,2)\n",
      "(a,1); (b,1); (c,1)\n"
     ]
    }
   ],
   "source": [
    "(* cartesian product *)\n",
    "\n",
    "let cartesian_product lst1 lst2 =\n",
    "  List.concat (List.map (fun e1 -> List.map (fun e2 -> (e1, e2)) lst2) lst1);;\n",
    "\n",
    "let () =\n",
    "  let print_result lst1 lst2 =\n",
    "    let res = cartesian_product lst1 lst2 in\n",
    "    Printf.printf \"%s\\n\" \n",
    "      (String.concat \"; \" (List.map (fun (x, y) -> \"(\" ^ x ^ \",\" ^ string_of_int y ^ \")\") res))\n",
    "  in\n",
    "  print_result [\"a\"; \"b\"] [1; 2];  (* prints \"(a,1); (a,2); (b,1); (b,2)\" *)\n",
    "  print_result [\"a\"; \"b\"; \"c\"] [1] ;  (* prints \"(1,a); (1,b); (1,c)\" *)\n",
    "  flush stdout"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "3b63198d",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val get_nth_element : 'a list -> int -> 'a = <fun>\n"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3\n",
      "7\n",
      "Index out of Bound\n"
     ]
    }
   ],
   "source": [
    "(* ith-element *)\n",
    "\n",
    "let rec get_nth_element lst n =\n",
    "  match lst with\n",
    "  | [] -> failwith \"Index out of Bound\"\n",
    "  | h :: t -> if n = 1 then h else get_nth_element t (n-1);;\n",
    "\n",
    "let () =\n",
    "  let print_result lst n =\n",
    "    try\n",
    "      let res = get_nth_element lst n in\n",
    "      Printf.printf \"%d\\n\" res\n",
    "    with Failure msg -> Printf.printf \"%s\\n\" msg\n",
    "  in\n",
    "  print_result [1; 2; 3; 4] 3;  (* prints \"3\" *)\n",
    "  print_result [7; 2; 3; 4] 1;  (* prints \"7\" *)\n",
    "  print_result [3] 2;           (* prints \"Index out of Bound\" *)\n",
    "  flush stdout"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "a8c36b38",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val get_index : 'a list -> 'a -> int -> int = <fun>\n"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3\n",
      "1\n",
      "Element not found\n"
     ]
    }
   ],
   "source": [
    "(* index of element *)\n",
    "\n",
    "let rec get_index lst x idx =\n",
    "  match lst with\n",
    "  | [] -> failwith \"Element not found\"\n",
    "  | h :: t -> if h = x then idx else get_index t x (idx + 1);;\n",
    "\n",
    "let () =\n",
    "  let print_result lst x =\n",
    "    try\n",
    "      let res = get_index lst x 1 in\n",
    "      Printf.printf \"%d\\n\" res\n",
    "    with Failure msg -> Printf.printf \"%s\\n\" msg\n",
    "  in\n",
    "  print_result [1; 2; 3; 4] 3;  (* prints \"3\" *)\n",
    "  print_result [10; 15] 10;  (* prints \"1\" *)\n",
    "  print_result [3] 2;  (* prints \"Element not found\" *)\n",
    "  flush stdout"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "513db5e4",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val add_element : 'a list -> 'a -> 'a list = <fun>\n"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1; 2; 3; 4; 5\n",
      "10; 15; 16\n",
      "Hello; World\n"
     ]
    }
   ],
   "source": [
    "(* insert at end *)\n",
    "\n",
    "let add_element lst x = lst @ [x];;\n",
    "\n",
    "let () =\n",
    "  let print_result_int lst x =\n",
    "    let res = add_element lst x in\n",
    "    Printf.printf \"%s\\n\" (String.concat \"; \" (List.map string_of_int res))\n",
    "  in\n",
    "  let print_result_string lst x =\n",
    "    let res = add_element lst x in\n",
    "    Printf.printf \"%s\\n\" (String.concat \"; \" res)\n",
    "  in\n",
    "  print_result_int [1; 2; 3; 4] 5;  (* prints \"1; 2; 3; 4; 5\" *)\n",
    "  print_result_int [10; 15] 16;  (* prints \"10; 15; 16\" *)\n",
    "  print_result_string [\"Hello\"] \"World\";  (* prints \"Hello; World\" *)\n",
    "  flush stdout"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "f250619a",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val reverse_list : 'a list -> 'a list = <fun>\n"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5; 4; 3; 2; 1\n",
      "World; Hello\n"
     ]
    }
   ],
   "source": [
    "(* reverse *)\n",
    "\n",
    "let reverse_list lst = List.rev lst;;\n",
    "\n",
    "let () =\n",
    "  let print_result_int lst =\n",
    "    let res = reverse_list lst in\n",
    "    Printf.printf \"%s\\n\" (String.concat \"; \" (List.map string_of_int res))\n",
    "  in\n",
    "  let print_result_string lst =\n",
    "    let res = reverse_list lst in\n",
    "    Printf.printf \"%s\\n\" (String.concat \"; \" res)\n",
    "  in\n",
    "  print_result_int [1; 2; 3; 4; 5];  (* prints \"5; 4; 3; 2; 1\" *)\n",
    "  print_result_string [\"Hello\"; \"World\"];  (* prints \"World; Hello\" *)\n",
    "  flush stdout"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "c4796282",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val sum_list : int list -> int = <fun>\n"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val concat_list : string list -> string = <fun>\n"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "15\n",
      "cba\n",
      "WorldHello\n"
     ]
    }
   ],
   "source": [
    "(* foldr *)\n",
    "\n",
    "let sum_list lst = List.fold_left (+) 0 lst;;\n",
    "\n",
    "let concat_list lst = List.fold_left (fun acc x -> x ^ acc) \"\" lst;;\n",
    "\n",
    "let () =\n",
    "  let print_result_int lst =\n",
    "    let res = sum_list lst in\n",
    "    Printf.printf \"%d\\n\" res\n",
    "  in\n",
    "  let print_result_string lst =\n",
    "    let res = concat_list lst in\n",
    "    Printf.printf \"%s\\n\" res\n",
    "  in\n",
    "  print_result_int [1; 2; 3; 4; 5];  (* prints \"15\" *)\n",
    "  print_result_string [\"a\"; \"b\"; \"c\"];  (* prints \"cba\" *)\n",
    "  print_result_string [\"Hello\"; \"World\"];  (* prints \"WorldHello\" *)\n",
    "  flush stdout"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "8efd4f08",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val list_length : 'a list -> int = <fun>\n"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5\n",
      "3\n",
      "2\n"
     ]
    }
   ],
   "source": [
    "(* length using fold *)\n",
    "\n",
    "let list_length lst = List.fold_left (fun acc _ -> acc + 1) 0 lst;;\n",
    "\n",
    "let () =\n",
    "  let print_result lst =\n",
    "    let res = list_length lst in\n",
    "    Printf.printf \"%d\\n\" res\n",
    "  in\n",
    "  print_result [1; 2; 3; 4; 5];  (* prints \"5\" *)\n",
    "  print_result [\"a\"; \"b\"; \"c\"];  (* prints \"3\" *)\n",
    "  print_result [\"Hello\"; \"World\"];  (* prints \"2\" *)\n",
    "  flush stdout"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "id": "e1649dfb",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val append_elem : 'a list -> 'a -> 'a list = <fun>\n"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1; 2; 3; 4; 5\n",
      "10; 15; 16\n",
      "Hello; World\n"
     ]
    }
   ],
   "source": [
    "(* append using fold *)\n",
    "\n",
    "let append_elem lst elem = List.fold_right (fun x acc -> x :: acc) lst [elem];;\n",
    "\n",
    "let () =\n",
    "  let print_result_int lst elem =\n",
    "    let res = append_elem lst elem in\n",
    "    Printf.printf \"%s\\n\" (String.concat \"; \" (List.map string_of_int res))\n",
    "  in\n",
    "  let print_result_string lst elem =\n",
    "    let res = append_elem lst elem in\n",
    "    Printf.printf \"%s\\n\" (String.concat \"; \" res)\n",
    "  in\n",
    "  print_result_int [1; 2; 3; 4] 5;  (* prints \"1; 2; 3; 4; 5\" *)\n",
    "  print_result_int [10; 15] 16;  (* prints \"10; 15; 16\" *)\n",
    "  print_result_string [\"Hello\"] \"World\";  (* prints \"Hello; World\" *)\n",
    "  flush stdout"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "589fc4b6",
   "metadata": {},
   "source": [
    "## Unique List"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "id": "cb32915b",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val append_if_not_present : 'a list -> 'a -> 'a list = <fun>\n"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1; 2; 3; 4; 5\n",
      "2; 3\n"
     ]
    }
   ],
   "source": [
    "(* insert *)\n",
    "\n",
    "let append_if_not_present lst elem = \n",
    "  if List.mem elem lst then lst else lst @ [elem];;\n",
    "\n",
    "let () =\n",
    "  let print_result lst elem =\n",
    "    let res = append_if_not_present lst elem in\n",
    "    Printf.printf \"%s\\n\" (String.concat \"; \" (List.map string_of_int res))\n",
    "  in\n",
    "  print_result [1; 2; 3; 4] 5;  (* prints \"1; 2; 3; 4; 5\" *)\n",
    "  print_result [2; 3] 3;  (* prints \"2; 3\" *)\n",
    "  flush stdout"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "id": "4482fcf0",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val remove_elem : 'a list -> 'a -> 'a list = <fun>\n"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1; 3; 4\n",
      "3\n",
      "Element not present\n"
     ]
    }
   ],
   "source": [
    "(* delete *)\n",
    "\n",
    "let remove_elem lst elem = \n",
    "  if List.mem elem lst then\n",
    "    List.filter (fun x -> x <> elem) lst\n",
    "  else\n",
    "    failwith \"Element not present\";;\n",
    "\n",
    "let () =\n",
    "  let print_result lst elem =\n",
    "    try \n",
    "      let res = remove_elem lst elem in\n",
    "      Printf.printf \"%s\\n\" (String.concat \"; \" (List.map string_of_int res))\n",
    "    with Failure msg -> Printf.printf \"%s\\n\" msg\n",
    "  in\n",
    "  print_result [1; 2; 3; 4] 2;  (* prints \"1; 3; 4\" *)\n",
    "  print_result [3; 2] 2;  (* prints \"3\" *)\n",
    "  print_result [4; 7] 8;  (* prints \"Element not present\" *)\n",
    "  flush stdout"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "id": "c066f402",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val remove_duplicates : 'a list -> 'a list = <fun>\n"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1; 2; 4\n",
      "3; 2\n",
      "4; 6; 7; 8\n"
     ]
    }
   ],
   "source": [
    "(* remove the duplicates *)\n",
    "\n",
    "let remove_duplicates lst =\n",
    "  let rec aux acc = function\n",
    "    | [] -> List.rev acc\n",
    "    | x :: t -> \n",
    "      if List.mem x acc then \n",
    "        aux acc t\n",
    "      else \n",
    "        aux (x :: acc) t\n",
    "  in\n",
    "  aux [] lst;;\n",
    "\n",
    "let () =\n",
    "  let print_result lst =\n",
    "    let res = remove_duplicates lst in\n",
    "    Printf.printf \"%s\\n\" (String.concat \"; \" (List.map string_of_int res))\n",
    "  in\n",
    "  print_result [1; 1; 2; 4; 4; 4];  (* prints \"1; 2; 4\" *)\n",
    "  print_result [3; 2];  (* prints \"3; 2\" *)\n",
    "  print_result [4; 4; 6; 6; 6; 7; 6; 6; 4; 4; 4; 4; 8];  (* prints \"4; 6; 7; 8\" *)\n",
    "  flush stdout"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "id": "bfb1ed08",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val remove_consecutive_duplicates : 'a list -> 'a list = <fun>\n"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1; 2; 4\n",
      "3; 2\n",
      "4; 6; 7; 6; 4; 8\n"
     ]
    }
   ],
   "source": [
    "(* remove the adjacent duplicates *)\n",
    "\n",
    "let remove_consecutive_duplicates lst =\n",
    "  let rec aux acc = function\n",
    "    | x :: (y :: _ as t) when x = y -> aux acc t\n",
    "    | x :: t -> aux (x :: acc) t\n",
    "    | [] -> List.rev acc\n",
    "  in\n",
    "  aux [] lst;;\n",
    "\n",
    "let () =\n",
    "  let print_result lst =\n",
    "    let res = remove_consecutive_duplicates lst in\n",
    "    Printf.printf \"%s\\n\" (String.concat \"; \" (List.map string_of_int res))\n",
    "  in\n",
    "  print_result [1; 1; 2; 4; 4; 4];  (* prints \"1; 2; 4\" *)\n",
    "  print_result [3; 2];  (* prints \"3; 2\" *)\n",
    "  print_result [4; 4; 6; 6; 6; 7; 6; 6; 4; 4; 4; 4; 8];  (* prints \"4; 6; 7; 6; 4; 8\" *)\n",
    "  flush stdout"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "id": "b114be8c",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val range : int -> int -> int list = <fun>\n"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val generate_list : int -> int -> int list = <fun>\n"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1; 2; 3; 4; 5\n",
      "2; 3; 4; 5; 6; 7\n",
      "Wrong Limit\n"
     ]
    }
   ],
   "source": [
    "(* integer range *)\n",
    "\n",
    "let rec range a b =\n",
    "  if a > b then\n",
    "    []\n",
    "  else\n",
    "    a :: (range (a + 1) b)\n",
    ";;\n",
    "\n",
    "let generate_list a b = \n",
    "  if a <= b then \n",
    "    range a b\n",
    "  else\n",
    "    failwith \"Wrong Limit\"\n",
    ";;\n",
    "\n",
    "let () =\n",
    "  let print_result a b =\n",
    "    try \n",
    "      let res = generate_list a b in\n",
    "      Printf.printf \"%s\\n\" (String.concat \"; \" (List.map string_of_int res))\n",
    "    with Failure msg -> Printf.printf \"%s\\n\" msg\n",
    "  in\n",
    "  print_result 1 5;  (* prints \"1; 2; 3; 4; 5\" *)\n",
    "  print_result 2 7;  (* prints \"2; 3; 4; 5; 6; 7\" *)\n",
    "  print_result 3 2;  (* prints \"Wrong Limit\" *)\n",
    "  flush stdout"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "009ca6df",
   "metadata": {},
   "source": [
    "## Strictly Sorted List"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "id": "daaf0db2",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val insert_in_sorted_list : 'a -> 'a list -> 'a list = <fun>\n"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1; 2; 3; 4; 5; 7\n",
      "2; 3; 3; 4\n",
      "4; 6; 7; 9; 10\n"
     ]
    }
   ],
   "source": [
    "(* insert *)\n",
    "\n",
    "let rec insert_in_sorted_list elem = function\n",
    "  | [] -> [elem]\n",
    "  | head :: tail as l -> if elem <= head then elem :: l else head :: insert_in_sorted_list elem tail\n",
    ";;\n",
    "\n",
    "let () =\n",
    "  let print_list lst = \n",
    "    String.concat \"; \" (List.map string_of_int lst) |> print_endline\n",
    "  in\n",
    "  insert_in_sorted_list 5 [1;2;3;4;7] |> print_list;  (* prints \"1; 2; 3; 4; 5; 7\" *)\n",
    "  insert_in_sorted_list 3 [2;3;4] |> print_list;  (* prints \"2; 3; 4\" *)\n",
    "  insert_in_sorted_list 7 [4;6;9;10] |> print_list;  (* prints \"4; 6; 7; 9; 10\" *)\n",
    "  flush stdout"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "id": "5dc0af1e",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val remove_from_list : 'a -> 'a list -> 'a list = <fun>\n"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1; 3; 4; 5; 7\n",
      "Element not present\n",
      "4; 6; 10\n"
     ]
    }
   ],
   "source": [
    "(* delete *)\n",
    "\n",
    "let remove_from_list elem lst =\n",
    "  if List.mem elem lst then\n",
    "    List.filter ((<>) elem) lst\n",
    "  else\n",
    "    failwith \"Element not present\"\n",
    ";;\n",
    "\n",
    "let () =\n",
    "  let print_result elem lst =\n",
    "    try \n",
    "      let res = remove_from_list elem lst in\n",
    "      Printf.printf \"%s\\n\" (String.concat \"; \" (List.map string_of_int res))\n",
    "    with Failure msg -> Printf.printf \"%s\\n\" msg\n",
    "  in\n",
    "  print_result 2 [1;2;3;4;5;7];  (* prints \"1; 3; 4; 5; 7\" *)\n",
    "  print_result 5 [2;3;4];  (* prints \"Element not present\" *)\n",
    "  print_result 9 [4;6;9;10];  (* prints \"4; 6; 10\" *)\n",
    "  flush stdout"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "id": "5e47b5f6",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val intersection : 'a list -> 'a list -> 'a list = <fun>\n"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 3 4 5 7\n",
      "3\n",
      "None\n"
     ]
    }
   ],
   "source": [
    "(* intersect *)\n",
    "\n",
    "let intersection lst1 lst2 = \n",
    "  List.filter (fun x -> List.mem x lst2) lst1;;\n",
    "\n",
    "let () =\n",
    "  let print_result lst1 lst2 =\n",
    "    match intersection lst1 lst2 with\n",
    "    | [] -> print_endline \"None\"\n",
    "    | lst -> Printf.printf \"%s\\n\" (String.concat \" \" (List.map string_of_int lst))\n",
    "  in\n",
    "  print_result [1;2;3;4;5;7] [1;3;4;5;7];  (* prints \"1 3 4 5 7\" *)\n",
    "  print_result [2;3;4] [3;6;7];  (* prints \"3\" *)\n",
    "  print_result [4;6;9;10] [1;2;3];  (* prints \"None\" *)\n",
    "  flush stdout"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bf14fcfc",
   "metadata": {},
   "source": [
    "## Sorting"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "id": "81e5bbcd",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val sort_list : 'a list -> 'a list = <fun>\n"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1; 2; 3; 4; 5; 6; 7\n",
      "2; 3; 4\n",
      "7; 9\n"
     ]
    }
   ],
   "source": [
    "(* insertion sort *)\n",
    "\n",
    "let sort_list lst = \n",
    "  List.sort compare lst;;\n",
    "\n",
    "let () =\n",
    "  let print_result lst =\n",
    "    let res = sort_list lst in\n",
    "    Printf.printf \"%s\\n\" (String.concat \"; \" (List.map string_of_int res))\n",
    "  in\n",
    "  print_result [7;5;1;4;3;2;6];  (* prints \"1; 2; 3; 4; 5; 6; 7\" *)\n",
    "  print_result [3;2;4];  (* prints \"2; 3; 4\" *)\n",
    "  print_result [9;7];  (* prints \"7; 9\" *)\n",
    "  flush stdout"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "id": "b5519dea",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val remove_min : 'a list -> 'a * 'a list = <fun>\n"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 7; 5; 4; 3; 2; 6\n",
      "2 3; 4\n",
      "7 9\n"
     ]
    }
   ],
   "source": [
    "(* extract minimum *)\n",
    "\n",
    "let remove_min lst = \n",
    "  match lst with\n",
    "  | [] -> failwith \"Empty list\"\n",
    "  | _ -> \n",
    "    let min = List.fold_left min (List.hd lst) lst in\n",
    "    (min, List.filter (fun x -> x <> min) lst);;\n",
    "\n",
    "let () =\n",
    "  let print_result lst =\n",
    "    let (min, res) = remove_min lst in\n",
    "    Printf.printf \"%d %s\\n\" min (String.concat \"; \" (List.map string_of_int res))\n",
    "  in\n",
    "  print_result [7;5;1;4;3;2;6];  (* prints \"1 [7;5;4;3;2;6]\" *)\n",
    "  print_result [3;2;4];  (* prints \"2 [3;4]\" *)\n",
    "  print_result [9;7];  (* prints \"7 [9]\" *)\n",
    "  flush stdout"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "id": "60e1d344",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val split_at : int -> 'a list -> 'a list * 'a list = <fun>\n"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val sort_and_split : 'a list -> 'a list * 'a list = <fun>\n"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1; 2; 3 5; 6; 7\n",
      "2 3\n"
     ]
    }
   ],
   "source": [
    "(* balanced split *)\n",
    "\n",
    "let split_at n lst =\n",
    "  let rec aux i acc = function\n",
    "    | [] -> List.rev acc, []\n",
    "    | h :: t as l -> if i = 0 then List.rev acc, l\n",
    "                     else aux (i-1) (h :: acc) t  in\n",
    "  aux n [] lst;;\n",
    "\n",
    "let sort_and_split lst =\n",
    "  let sorted = List.sort compare lst in\n",
    "  let len = List.length sorted in\n",
    "  let mid = (len + 1) / 2 in\n",
    "  split_at mid sorted;;\n",
    "\n",
    "let () =\n",
    "  let print_result lst =\n",
    "    let (first_half, second_half) = sort_and_split lst in\n",
    "    Printf.printf \"%s %s\\n\" \n",
    "      (String.concat \"; \" (List.map string_of_int first_half))\n",
    "      (String.concat \"; \" (List.map string_of_int second_half))\n",
    "  in\n",
    "  print_result [7;5;1;3;2;6];  (* prints \"[1; 2; 3; 4] [5; 6; 7]\" *)\n",
    "  print_result [3;2];  (* prints \"[2] [3]\" *)\n",
    "  flush stdout"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "id": "b5c3f14b",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val merge_sorted_lists : 'a list -> 'a list -> 'a list = <fun>\n"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1; 2; 3; 4; 5; 9\n",
      "6; 7; 7; 8; 10\n"
     ]
    }
   ],
   "source": [
    "(* merge *)\n",
    "\n",
    "let rec merge_sorted_lists lst1 lst2 = match lst1, lst2 with\n",
    "  | [], _ -> lst2\n",
    "  | _, [] -> lst1\n",
    "  | h1 :: t1, h2 :: t2 -> \n",
    "    if h1 < h2 then h1 :: merge_sorted_lists t1 lst2\n",
    "    else h2 :: merge_sorted_lists lst1 t2\n",
    "\n",
    "let () =\n",
    "  let print_result lst1 lst2 =\n",
    "    let merged = merge_sorted_lists lst1 lst2 in\n",
    "    Printf.printf \"%s\\n\" (String.concat \"; \" (List.map string_of_int merged))\n",
    "  in\n",
    "  print_result [1;4;9] [2;3;5];  (* prints \"1; 2; 3; 4; 5; 9\" *)\n",
    "  print_result [6;7;10] [7;8];  (* prints \"6; 7; 7; 8; 10\" *)\n",
    "  flush stdout"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "id": "a968e0da",
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "File \"[33]\", line 5, characters 23-41:\n",
      "5 |     | [] -> (List.sort Pervasives.compare odds, List.sort Pervasives.compare evens)\n",
      "                           ^^^^^^^^^^^^^^^^^^\n",
      "Alert deprecated: module Stdlib.Pervasives\n",
      "Use Stdlib instead.\n",
      "\n",
      "If you need to stay compatible with OCaml < 4.07, you can use the \n",
      "stdlib-shims library: https://github.com/ocaml/stdlib-shims\n",
      "File \"[33]\", line 5, characters 58-76:\n",
      "5 |     | [] -> (List.sort Pervasives.compare odds, List.sort Pervasives.compare evens)\n",
      "                                                              ^^^^^^^^^^^^^^^^^^\n",
      "Alert deprecated: module Stdlib.Pervasives\n",
      "Use Stdlib instead.\n",
      "\n",
      "If you need to stay compatible with OCaml < 4.07, you can use the \n",
      "stdlib-shims library: https://github.com/ocaml/stdlib-shims\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "val split_odd_even : int list -> int list * int list = <fun>\n"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Odd numbers: [1; 3; 5; 9], Even numbers: [2; 4; 10; 12]\n",
      "Odd numbers: [1; 7], Even numbers: [2; 6; 8; 10]\n"
     ]
    }
   ],
   "source": [
    "(* partition *)\n",
    "\n",
    "let split_odd_even lst =\n",
    "  let rec aux odds evens = function\n",
    "    | [] -> (List.sort Pervasives.compare odds, List.sort Pervasives.compare evens)\n",
    "    | h :: t -> if h mod 2 = 0 then aux odds (h :: evens) t else aux (h :: odds) evens t\n",
    "  in\n",
    "  aux [] [] lst\n",
    "\n",
    "let () =\n",
    "  let print_result lst =\n",
    "    let (odds, evens) = split_odd_even lst in\n",
    "    let print_list l = List.map string_of_int l |> String.concat \"; \" in\n",
    "    Printf.printf \"Odd numbers: [%s], Even numbers: [%s]\\n\"\n",
    "      (print_list odds) (print_list evens)\n",
    "  in\n",
    "  print_result [2;4;5;9;10;12;1;3];  (* prints \"Odd numbers: [1; 3; 5; 9], Even numbers: [2; 4; 10; 12]\" *)\n",
    "  print_result [6;7;8;10;1;2];  (* prints \"Odd numbers: [1; 7], Even numbers: [2; 6; 8; 10]\" *)\n",
    "  flush stdout"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "adb95765",
   "metadata": {},
   "source": [
    "## Tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "id": "dccb6992",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "type 'a binary_tree = Empty | Node of 'a * 'a binary_tree * 'a binary_tree\n"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "type 'a binary_tree =\n",
    "  | Empty\n",
    "  | Node of 'a * 'a binary_tree * 'a binary_tree;;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "id": "23a34a09",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val find_in_tree : 'a -> 'a binary_tree -> bool = <fun>\n"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "true\n",
      "false\n"
     ]
    }
   ],
   "source": [
    "(* is member *)\n",
    "\n",
    "let rec find_in_tree x = function\n",
    "  | Empty -> false\n",
    "  | Node (y, left, right) ->\n",
    "    if x = y then true\n",
    "    else find_in_tree x left || find_in_tree x right;;\n",
    "\n",
    "let () =\n",
    "  let t1 = Node (4,\n",
    "                 Node (2,\n",
    "                     Node (1, Empty, Empty),\n",
    "                     Node (3, Empty, Empty)),\n",
    "                Node (5, Empty, Empty)) in\n",
    "\n",
    "  let t2 = Node (6,\n",
    "                 Node (8,\n",
    "                     Node (2, Node (12, Empty, Empty), Empty),\n",
    "                     Node (11, Empty, Empty)),\n",
    "                Node (10, Empty, Empty)) in\n",
    "\n",
    "  print_endline (string_of_bool (find_in_tree 2 t1));  (* prints \"true\" *)\n",
    "  print_endline (string_of_bool (find_in_tree 7 t2));  (* prints \"false\" *)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "id": "ef669382",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val count_nodes : 'a binary_tree -> int = <fun>\n"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "6\n",
      "7\n"
     ]
    }
   ],
   "source": [
    "(* node count *)\n",
    "\n",
    "let rec count_nodes = function\n",
    "  | Empty -> 0\n",
    "  | Node (_, left, right) -> 1 + count_nodes left + count_nodes right;;\n",
    "\n",
    "let () =\n",
    "  let t1 = Node (4,\n",
    "                 Node (2,\n",
    "                     Node (1, Empty, Empty),\n",
    "                     Node (3, Empty, Empty)),\n",
    "                Node (5, Node (10, Empty, Empty), Empty)) in\n",
    "\n",
    "  let t2 = Node (6,\n",
    "                 Node (8,\n",
    "                     Node (2, Node (12, Empty, Empty), Empty),\n",
    "                     Node (11, Empty, Empty)),\n",
    "                Node (10, Node (3, Empty, Empty), Empty)) in\n",
    "\n",
    "  print_endline (string_of_int (count_nodes t1));  (* prints \"6\" *)\n",
    "  print_endline (string_of_int (count_nodes t2));  (* prints \"7\" *)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "id": "9e36888e",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val preorder_traversal : 'a binary_tree -> 'a list = <fun>\n"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[4; 2; 1; 3; 5; 10]\n",
      "[6; 8; 2; 12; 11; 10; 3]\n"
     ]
    }
   ],
   "source": [
    "(* pre-order *)\n",
    "\n",
    "let rec preorder_traversal = function\n",
    "  | Empty -> []\n",
    "  | Node (x, left, right) -> x :: (preorder_traversal left @ preorder_traversal right);;\n",
    "\n",
    "let () =\n",
    "  let t1 = Node (4,\n",
    "                 Node (2,\n",
    "                     Node (1, Empty, Empty),\n",
    "                     Node (3, Empty, Empty)),\n",
    "                Node (5, Node (10, Empty, Empty), Empty)) in\n",
    "\n",
    "  let t2 = Node (6,\n",
    "                 Node (8,\n",
    "                     Node (2, Node (12, Empty, Empty), Empty),\n",
    "                     Node (11, Empty, Empty)),\n",
    "                Node (10, Node (3, Empty, Empty), Empty)) in\n",
    "\n",
    "  let print_result lst = Printf.printf \"[%s]\\n\" (String.concat \"; \" (List.map string_of_int lst)) in\n",
    "\n",
    "  print_result (preorder_traversal t1);  (* prints \"[4; 2; 1; 3; 5; 10]\" *)\n",
    "  print_result (preorder_traversal t2);  (* prints \"[6; 8; 2; 12; 11; 10; 3]\" *)\n",
    "  flush stdout"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4b0c7b1d",
   "metadata": {},
   "source": [
    "## BST"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "id": "a88b4bf0",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val bst_contains : 'a -> 'a binary_tree -> bool = <fun>\n"
      ]
     },
     "execution_count": 38,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "true\n",
      "false\n"
     ]
    }
   ],
   "source": [
    "(* is member *)\n",
    "\n",
    "let rec bst_contains x = function\n",
    "  | Empty -> false\n",
    "  | Node (y, left, right) ->\n",
    "    if x = y then true\n",
    "    else if x < y then bst_contains x left\n",
    "    else bst_contains x right;;\n",
    "\n",
    "let () =\n",
    "  let t1 = Node (10,\n",
    "                 Node (7,\n",
    "                     Node (1, Empty, Empty),\n",
    "                     Node (8, Empty, Empty)),\n",
    "                Node (12, Node (11, Empty, Empty), Empty)) in\n",
    "\n",
    "  let t2 = Node (20,\n",
    "                 Node (15,\n",
    "                     Node (12, Node (8, Empty, Empty), Empty),\n",
    "                     Node (16, Empty, Empty)),\n",
    "                Node (25, Node (22, Empty, Empty), Empty)) in\n",
    "\n",
    "  print_endline (string_of_bool (bst_contains 1 t1));  (* prints \"true\" *)\n",
    "  print_endline (string_of_bool (bst_contains 7 t2));  (* prints \"false\" *)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "id": "746b91f9",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val insert_bst : 'a -> 'a binary_tree -> 'a binary_tree = <fun>\n"
      ]
     },
     "execution_count": 39,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val to_string : int binary_tree -> string = <fun>\n"
      ]
     },
     "execution_count": 39,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Node (10, Node (7, Node (1, Empty, Node (6, Empty, Empty)), Node (8, Empty, Empty)), Node (12, Node (11, Empty, Empty), Empty))\n",
      "Node (20, Node (15, Node (12, Node (8, Empty, Empty), Node (13, Empty, Empty)), Node (16, Empty, Empty)), Node (25, Node (22, Empty, Empty), Empty))\n"
     ]
    }
   ],
   "source": [
    "(* insert *)\n",
    "\n",
    "let rec insert_bst x = function\n",
    "  | Empty -> Node (x, Empty, Empty)\n",
    "  | Node (y, left, right) as node ->\n",
    "    if x = y then node\n",
    "    else if x < y then Node (y, insert_bst x left, right)\n",
    "    else Node (y, left, insert_bst x right);;\n",
    "\n",
    "let rec to_string = function\n",
    "  | Empty -> \"Empty\"\n",
    "  | Node (x, left, right) ->\n",
    "    Printf.sprintf \"Node (%d, %s, %s)\" x (to_string left) (to_string right)\n",
    "\n",
    "let () =\n",
    "  let t1 = Node (10,\n",
    "                 Node (7,\n",
    "                     Node (1, Empty, Empty),\n",
    "                     Node (8, Empty, Empty)),\n",
    "                Node (12, Node (11, Empty, Empty), Empty)) in\n",
    "\n",
    "  let t2 = Node (20,\n",
    "                 Node (15,\n",
    "                     Node (12, Node (8, Empty, Empty), Empty),\n",
    "                     Node (16, Empty, Empty)),\n",
    "                Node (25, Node (22, Empty, Empty), Empty)) in\n",
    "\n",
    "  print_endline (to_string (insert_bst 6 t1));\n",
    "  print_endline (to_string (insert_bst 13 t2));"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "id": "ebe75b64",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val min_value_bst : 'a binary_tree -> 'a = <fun>\n"
      ]
     },
     "execution_count": 40,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val delete_bst : 'a -> 'a binary_tree -> 'a binary_tree = <fun>\n"
      ]
     },
     "execution_count": 40,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val to_string : int binary_tree -> string = <fun>\n"
      ]
     },
     "execution_count": 40,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Node (10, Node (8, Node (6, Node (1, Empty, Empty), Empty), Empty), Node (12, Node (11, Empty, Empty), Empty))\n",
      "Node (20, Node (15, Node (12, Node (8, Empty, Empty), Node (13, Empty, Empty)), Empty), Node (25, Node (22, Empty, Empty), Empty))\n"
     ]
    }
   ],
   "source": [
    "(* delete *)\n",
    "\n",
    "let rec min_value_bst = function\n",
    "  | Empty -> failwith \"Empty tree has no minimum\"\n",
    "  | Node(x, Empty, _) -> x\n",
    "  | Node(_, left, _) -> min_value_bst left\n",
    "\n",
    "let rec delete_bst x = function\n",
    "  | Empty -> Empty\n",
    "  | Node(y, left, right) when x < y -> Node(y, delete_bst x left, right)\n",
    "  | Node(y, left, right) when x > y -> Node(y, left, delete_bst x right)\n",
    "  | Node(_, Empty, right) -> right\n",
    "  | Node(_, left, Empty) -> left\n",
    "  | Node(_, left, right) ->\n",
    "    let min_right = min_value_bst right in\n",
    "    Node(min_right, left, delete_bst min_right right)\n",
    "\n",
    "let rec to_string = function\n",
    "  | Empty -> \"Empty\"\n",
    "  | Node (x, left, right) ->\n",
    "    Printf.sprintf \"Node (%d, %s, %s)\" x (to_string left) (to_string right)\n",
    "\n",
    "let () =\n",
    "  let t1 = Node (10,\n",
    "                 Node (7,\n",
    "                     Node (6, Node (1, Empty, Empty), Empty),\n",
    "                     Node (8, Empty, Empty)),\n",
    "                Node (12, Node (11, Empty, Empty), Empty)) in\n",
    "\n",
    "  let t2 = Node (20,\n",
    "                 Node (15,\n",
    "                     Node (12, Node (8, Empty, Empty), Node (13, Empty, Empty)),\n",
    "                     Node (16, Empty, Empty)),\n",
    "                Node (25, Node (22, Empty, Empty), Empty)) in\n",
    "\n",
    "  print_endline (to_string (delete_bst 7 t1));\n",
    "  print_endline (to_string (delete_bst 16 t2));"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "id": "c2eae7e3",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val insert_bst : 'a -> 'a binary_tree -> 'a binary_tree = <fun>\n"
      ]
     },
     "execution_count": 41,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val build_bst : 'a list -> 'a binary_tree = <fun>\n"
      ]
     },
     "execution_count": 41,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val inorder_traversal : 'a binary_tree -> 'a list = <fun>\n"
      ]
     },
     "execution_count": 41,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1; 6; 7; 8; 10; 11; 12]\n",
      "[12; 13; 15; 16; 20; 22; 25]\n"
     ]
    }
   ],
   "source": [
    "(* bst_sort *)\n",
    "\n",
    "let rec insert_bst x = function\n",
    "  | Empty -> Node (x, Empty, Empty)\n",
    "  | Node (y, left, right) as node ->\n",
    "    if x = y then node\n",
    "    else if x < y then Node (y, insert_bst x left, right)\n",
    "    else Node (y, left, insert_bst x right);;\n",
    "\n",
    "let build_bst lst = \n",
    "  List.fold_left (fun tree x -> insert_bst x tree) Empty lst;;\n",
    "\n",
    "let rec inorder_traversal = function\n",
    "  | Empty -> []\n",
    "  | Node (x, left, right) -> inorder_traversal left @ [x] @ inorder_traversal right;;\n",
    "\n",
    "let () =\n",
    "  let print_list lst = Printf.printf \"[%s]\\n\" (String.concat \"; \" (List.map string_of_int lst)) in\n",
    "  let print_result lst = \n",
    "    let tree = build_bst lst in\n",
    "    let sorted = inorder_traversal tree in\n",
    "    print_list sorted\n",
    "  in\n",
    "\n",
    "  print_result [11; 12; 8; 10; 7; 6; 1];  (* prints \"[1; 6; 7; 8; 10; 11; 12]\" *)\n",
    "  print_result [16; 20; 15; 12; 13; 25; 22];  (* prints \"[12; 13; 15; 16; 20; 22; 25]\" *)\n",
    "  flush stdout"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2ba780f6",
   "metadata": {},
   "source": [
    "## Binary Heap"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "id": "3717553b",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "type 'a heap = Empty | Node of 'a * 'a heap * 'a heap\n"
      ]
     },
     "execution_count": 42,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "type 'a heap = \n",
    "  | Empty\n",
    "  | Node of 'a * 'a heap * 'a heap;;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "id": "da63e2b5",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val contains : 'a -> 'a heap -> bool = <fun>\n"
      ]
     },
     "execution_count": 43,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val build_heap : 'a list -> 'a heap = <fun>\n"
      ]
     },
     "execution_count": 43,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "true\n",
      "false\n"
     ]
    }
   ],
   "source": [
    "(* is member *)\n",
    "\n",
    "let rec contains x = function\n",
    "  | Empty -> false\n",
    "  | Node (y, left, right) -> \n",
    "    if x = y then true\n",
    "    else if x < y then false\n",
    "    else contains x left || contains x right;;\n",
    "\n",
    "let build_heap lst =\n",
    "  let rec aux i =\n",
    "    if i >= List.length lst then Empty\n",
    "    else Node (List.nth lst i, aux (2*i+1), aux (2*i+2))\n",
    "  in\n",
    "  aux 0;;\n",
    "\n",
    "let () =\n",
    "  print_endline (string_of_bool (contains 3 (build_heap [1; 2; 3; 4; 5; 6; 7])));  (* prints \"true\" *)\n",
    "  print_endline (string_of_bool (contains 10 (build_heap [1; 7; 6; 12; 13; 8; 9])));  (* prints \"false\" *)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "id": "97dcf92c",
   "metadata": {},
   "outputs": [
    {
     "ename": "error",
     "evalue": "compile_error",
     "output_type": "error",
     "traceback": [
      "File \"[44]\", line 23, characters 174-175:\n23 |   let heap2 = insert 7 (Node (10, Node (20, Node (25, Empty, Empty), Node (35, Node (27, Empty, Empty), Node (30, Node (29, Empty, Empty), Node (37, Empty, Empty))))), Empty)) in\n                                                                                                                                                                                   ^\nError: Syntax error\n"
     ]
    }
   ],
   "source": [
    "(* insert *)\n",
    "\n",
    "let rec insert x heap = \n",
    "  match heap with\n",
    "  | Empty -> Node (x, Empty, Empty)\n",
    "  | Node (y, left, right) -> \n",
    "    if x <= y \n",
    "    then Node (x, insert y right, left)\n",
    "    else Node (y, insert x right, left);;\n",
    "\n",
    "let heap_to_string heap = \n",
    "  let rec aux = function\n",
    "    | Empty -> \"Empty\"\n",
    "    | Node (v, left, right) -> \n",
    "        \"Node (\" ^ string_of_int v ^ \", \" ^ aux left ^ \", \" ^ aux right ^ \")\"\n",
    "  in\n",
    "  aux heap;;\n",
    "\n",
    "let () =\n",
    "  let heap1 = insert 10 (Node (1, Node (7, Node (6, Empty, Empty), Node (12, Node (13, Empty, Empty), Node (8, Node (9, Empty, Empty), Empty))), Empty)) in\n",
    "  print_endline (heap_to_string heap1);\n",
    "  \n",
    "  let heap2 = insert 7 (Node (10, Node (20, Node (25, Empty, Empty), Node (35, Node (27, Empty, Empty), Node (30, Node (29, Empty, Empty), Node (37, Empty, Empty))))), Empty)) in\n",
    "  print_endline (heap_to_string heap2)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4c6e12bb",
   "metadata": {},
   "source": [
    "## AVL"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "id": "6a15d181",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "type tree = Empty | Node of int * int * tree * tree\n"
      ]
     },
     "execution_count": 45,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "type tree = Empty | Node of int * int * tree * tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "id": "53b6aa01",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val height : tree -> int = <fun>\n"
      ]
     },
     "execution_count": 46,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val update_height : tree -> tree = <fun>\n"
      ]
     },
     "execution_count": 46,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "File \"[46]\", lines 14-17, characters 2-103:\n",
      "14 | ..match tree with\n",
      "15 |   | Empty -> Empty\n",
      "16 |   | Node(value, _, left, Node(right_value, _, right_left, right_right)) ->\n",
      "17 |     update_height (Node(right_value, 0, update_height (Node(value, 0, left, right_left)), right_right))\n",
      "Warning 8 [partial-match]: this pattern-matching is not exhaustive.\n",
      "Here is an example of a case that is not matched:\n",
      "Node (_, _, _, Empty)\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "val rotate_left : tree -> tree = <fun>\n"
      ]
     },
     "execution_count": 46,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val tree : tree =\n",
       "  Node (8, 3, Empty, Node (9, 2, Empty, Node (10, 1, Empty, Empty)))\n"
      ]
     },
     "execution_count": 46,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val rotated_tree : tree =\n",
       "  Node (9, 2, Node (8, 1, Empty, Empty), Node (10, 1, Empty, Empty))\n"
      ]
     },
     "execution_count": 46,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(* left rotate *)\n",
    "\n",
    "let height tree = \n",
    "  match tree with\n",
    "  | Empty -> 0\n",
    "  | Node(_, h, _, _) -> h\n",
    "\n",
    "let update_height tree =\n",
    "  match tree with\n",
    "  | Empty -> Empty\n",
    "  | Node(v, _, l, r) -> Node(v, max (height l) (height r) + 1, l, r)\n",
    "\n",
    "let rotate_left tree =\n",
    "  match tree with\n",
    "  | Empty -> Empty\n",
    "  | Node(value, _, left, Node(right_value, _, right_left, right_right)) ->\n",
    "    update_height (Node(right_value, 0, update_height (Node(value, 0, left, right_left)), right_right))\n",
    "\n",
    "let tree = Node (8, 3, Empty, Node(9, 2, Empty, Node(10, 1, Empty, Empty)))\n",
    "let rotated_tree = rotate_left tree\n",
    "(* This should result in Node (9, 2, Node (8, 1, Empty, Empty), Node (10, 1, Empty, Empty)) *)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "id": "fffb891d",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val height : tree -> int = <fun>\n"
      ]
     },
     "execution_count": 47,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val update_height : tree -> tree = <fun>\n"
      ]
     },
     "execution_count": 47,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "File \"[47]\", lines 14-17, characters 2-101:\n",
      "14 | ..match tree with\n",
      "15 |   | Empty -> Empty\n",
      "16 |   | Node(value, _, Node(left_value, _, left_left, left_right), right) ->\n",
      "17 |     update_height (Node(left_value, 0, left_left, update_height (Node(value, 0, left_right, right))))\n",
      "Warning 8 [partial-match]: this pattern-matching is not exhaustive.\n",
      "Here is an example of a case that is not matched:\n",
      "Node (_, _, Empty, _)\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "val rotate_right : tree -> tree = <fun>\n"
      ]
     },
     "execution_count": 47,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val tree : tree =\n",
       "  Node (10, 3, Node (9, 2, Node (8, 1, Empty, Empty), Empty), Empty)\n"
      ]
     },
     "execution_count": 47,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val rotated_tree : tree =\n",
       "  Node (9, 2, Node (8, 1, Empty, Empty), Node (10, 1, Empty, Empty))\n"
      ]
     },
     "execution_count": 47,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(* right rotate *)\n",
    "\n",
    "let height tree = \n",
    "  match tree with\n",
    "  | Empty -> 0\n",
    "  | Node(_, h, _, _) -> h\n",
    "\n",
    "let update_height tree =\n",
    "  match tree with\n",
    "  | Empty -> Empty\n",
    "  | Node(v, _, l, r) -> Node(v, max (height l) (height r) + 1, l, r)\n",
    "\n",
    "let rotate_right tree =\n",
    "  match tree with\n",
    "  | Empty -> Empty\n",
    "  | Node(value, _, Node(left_value, _, left_left, left_right), right) ->\n",
    "    update_height (Node(left_value, 0, left_left, update_height (Node(value, 0, left_right, right))))\n",
    "\n",
    "let tree = Node (10, 3, Node(9, 2, Node(8, 1, Empty, Empty), Empty), Empty)\n",
    "let rotated_tree = rotate_right tree\n",
    "(* This should result in Node (9, 2, Node (8, 1, Empty, Empty), Node (10, 1, Empty, Empty)) *)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "id": "da04b8d4",
   "metadata": {},
   "outputs": [],
   "source": [
    "(* For balance, insert and delete, chatGPT was able to infer which method was implemented from the examples but wrote \n",
    "incorrect code for the operation. *)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "OCaml 4.12.1",
   "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.12.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}