Benchmarks for Synquid.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "90e0b9e6",
   "metadata": {},
   "source": [
    "## Lists"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "2271263e",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val is_empty : 'a list -> bool = <fun>\n"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Not empty\n",
      "Empty\n"
     ]
    }
   ],
   "source": [
    "(* is_empty *)\n",
    "\n",
    "let is_empty lst =\n",
    "  match lst with\n",
    "  | [] -> true\n",
    "  | _  -> false\n",
    "\n",
    "let () =\n",
    "  let test_lst1 = [1; 2; 3] in\n",
    "  let test_lst2 = [] in\n",
    "  print_string (if is_empty test_lst1 then \"Empty\\n\" else \"Not empty\\n\");\n",
    "  print_string (if is_empty test_lst2 then \"Empty\\n\" else \"Not empty\\n\");\n",
    "  flush stdout"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "db94a5ed",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val is_member : 'a -> 'a list -> bool = <fun>\n"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Yes\n",
      "Yes\n"
     ]
    }
   ],
   "source": [
    "(* is_member *)\n",
    "\n",
    "let rec is_member x lst =\n",
    "  match lst with\n",
    "  | [] -> false\n",
    "  | hd :: tl -> hd = x || is_member x tl\n",
    "\n",
    "let () =\n",
    "  let test_lst = [1; 2; 3] in\n",
    "  print_string (if is_member 2 test_lst then \"Yes\\n\" else \"No\\n\");\n",
    "  print_string (if is_member 4 test_lst then \"Yes\\n\" else \"No\\n\");\n",
    "  flush stdout"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "e082cac3",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val duplicate_each : '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 \n"
     ]
    }
   ],
   "source": [
    "(* duplicate_each_element *)\n",
    "\n",
    "let rec duplicate_each lst =\n",
    "  match lst with\n",
    "  | [] -> []\n",
    "  | hd :: tl -> hd :: hd :: duplicate_each tl\n",
    "\n",
    "let () =\n",
    "  let test_lst = [1; 2; 3] in\n",
    "  let result = duplicate_each test_lst in\n",
    "  List.iter (Printf.printf \"%d \") result;\n",
    "  print_newline ()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "7584001d",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val replicate : 'a list -> int -> 'a list = <fun>\n",
       "val repeat : 'a -> int -> 'a list = <fun>\n"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 1 1 2 2 2 3 3 3 \n"
     ]
    }
   ],
   "source": [
    "(* replicate *)\n",
    "\n",
    "let rec replicate lst n =\n",
    "  match lst with\n",
    "  | [] -> []\n",
    "  | hd :: tl -> (repeat hd n) @ replicate tl n\n",
    "and repeat x n =\n",
    "  if n <= 0 then [] else x :: repeat x (n-1)\n",
    "\n",
    "let () =\n",
    "  let test_lst = [1; 2; 3] in\n",
    "  let result = replicate test_lst 3 in\n",
    "  List.iter (Printf.printf \"%d \") result;\n",
    "  print_newline ()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "e76f678d",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val append_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 5 6 \n"
     ]
    }
   ],
   "source": [
    "(* append_lists *)\n",
    "\n",
    "let rec append_lists lst1 lst2 =\n",
    "  match lst1 with\n",
    "  | [] -> lst2\n",
    "  | hd :: tl -> hd :: append_lists tl lst2\n",
    "\n",
    "let () =\n",
    "  let test_lst1 = [1; 2; 3] in\n",
    "  let test_lst2 = [4; 5; 6] in\n",
    "  let result = append_lists test_lst1 test_lst2 in\n",
    "  List.iter (Printf.printf \"%d \") result;\n",
    "  print_newline ()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "c6a7148b",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val concatenate_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 5 6 7 8 9 \n"
     ]
    }
   ],
   "source": [
    "(* concatenate_list_of_lists *)\n",
    "\n",
    "let rec concatenate_lists lst =\n",
    "  match lst with\n",
    "  | [] -> []\n",
    "  | hd :: tl -> hd @ concatenate_lists tl\n",
    "\n",
    "let () =\n",
    "  let test_lst = [[1; 2; 3]; [4; 5; 6]; [7; 8; 9]] in\n",
    "  let result = concatenate_lists test_lst in\n",
    "  List.iter (Printf.printf \"%d \") result;\n",
    "  print_newline ()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "7eb98dba",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val take : int -> 'a list -> 'a list = <fun>\n"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 2 3 \n"
     ]
    }
   ],
   "source": [
    "(* take_first_n_elements *)\n",
    "\n",
    "let rec take n lst =\n",
    "  if n <= 0 then []\n",
    "  else match lst with\n",
    "  | [] -> []\n",
    "  | hd :: tl -> hd :: take (n-1) tl\n",
    "\n",
    "let () =\n",
    "  let test_lst = [1; 2; 3; 4; 5] in\n",
    "  let result = take 3 test_lst in\n",
    "  List.iter (Printf.printf \"%d \") result;\n",
    "  print_newline ()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "b2494b28",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val drop : int -> 'a list -> 'a list = <fun>\n"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4 5 \n"
     ]
    }
   ],
   "source": [
    "(* drop_first_n_elements *)\n",
    "\n",
    "let rec drop n lst =\n",
    "  if n <= 0 then lst\n",
    "  else match lst with\n",
    "  | [] -> []\n",
    "  | _ :: tl -> drop (n-1) tl\n",
    "\n",
    "let () =\n",
    "  let test_lst = [1; 2; 3; 4; 5] in\n",
    "  let result = drop 3 test_lst in\n",
    "  List.iter (Printf.printf \"%d \") result;\n",
    "  print_newline ()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "6967e769",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val delete_value : 'a -> 'a list -> 'a list = <fun>\n"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 2 4 5 \n"
     ]
    }
   ],
   "source": [
    "(* delete_value *)\n",
    "\n",
    "let rec delete_value x lst =\n",
    "  match lst with\n",
    "  | [] -> []\n",
    "  | hd :: tl -> if hd = x then tl else hd :: delete_value x tl\n",
    "\n",
    "let () =\n",
    "  let test_lst = [1; 2; 3; 4; 5] in\n",
    "  let result = delete_value 3 test_lst in\n",
    "  List.iter (Printf.printf \"%d \") result;\n",
    "  print_newline ()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "b2063e38",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val map : ('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 10 \n"
     ]
    }
   ],
   "source": [
    "(* map *)\n",
    "\n",
    "let rec map f lst =\n",
    "  match lst with\n",
    "  | [] -> []\n",
    "  | hd :: tl -> f hd :: map f tl\n",
    "\n",
    "let () =\n",
    "  let test_lst = [1; 2; 3; 4; 5] in\n",
    "  let result = map (fun x -> x * 2) test_lst in\n",
    "  List.iter (Printf.printf \"%d \") result;\n",
    "  print_newline ()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "fb7c30d0",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val zip : 'a list -> 'b list -> ('a * 'b) list = <fun>\n"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(1, 4) (2, 5) (3, 6) \n"
     ]
    }
   ],
   "source": [
    "(* zip *)\n",
    "\n",
    "let rec zip lst1 lst2 =\n",
    "  match lst1, lst2 with\n",
    "  | [], _ | _, [] -> []\n",
    "  | hd1 :: tl1, hd2 :: tl2 -> (hd1, hd2) :: zip tl1 tl2\n",
    "\n",
    "let () =\n",
    "  let test_lst1 = [1; 2; 3] in\n",
    "  let test_lst2 = [4; 5; 6] in\n",
    "  let result = zip test_lst1 test_lst2 in\n",
    "  List.iter (fun (x, y) -> Printf.printf \"(%d, %d) \" x y) result;\n",
    "  print_newline ()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "733e09dc",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val zip_with : ('a -> 'b -> 'c) -> 'a list -> 'b list -> 'c list = <fun>\n"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5 7 9 \n"
     ]
    }
   ],
   "source": [
    "(* zip with function *)\n",
    "\n",
    "let rec zip_with f lst1 lst2 =\n",
    "  match lst1, lst2 with\n",
    "  | [], _ | _, [] -> []\n",
    "  | hd1 :: tl1, hd2 :: tl2 -> f hd1 hd2 :: zip_with f tl1 tl2\n",
    "\n",
    "let () =\n",
    "  let test_lst1 = [1; 2; 3] in\n",
    "  let test_lst2 = [4; 5; 6] in\n",
    "  let result = zip_with (+) test_lst1 test_lst2 in\n",
    "  List.iter (Printf.printf \"%d \") result;\n",
    "  print_newline ()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "876f2ac6",
   "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": [
      "(1, a) (1, b) (1, c) (2, a) (2, b) (2, c) (3, a) (3, b) (3, c) \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 test_lst1 = [1; 2; 3] in\n",
    "  let test_lst2 = ['a'; 'b'; 'c'] in\n",
    "  let result = cartesian_product test_lst1 test_lst2 in\n",
    "  List.iter (fun (x, y) -> Printf.printf \"(%d, %c) \" x y) result;\n",
    "  print_newline ()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "3b622425",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val ith_element : int -> 'a list -> 'a = <fun>\n"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3\n"
     ]
    }
   ],
   "source": [
    "(* ith-product *)\n",
    "\n",
    "let rec ith_element i lst =\n",
    "  match lst with\n",
    "  | [] -> failwith \"Index out of bounds\"\n",
    "  | hd :: tl -> if i = 0 then hd else ith_element (i-1) tl\n",
    "\n",
    "let () =\n",
    "  let test_lst = [1; 2; 3; 4; 5] in\n",
    "  let result = ith_element 2 test_lst in\n",
    "  Printf.printf \"%d\\n\" result;\n",
    "  flush stdout"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "997f0bc7",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val index_of : 'a -> 'a list -> int option = <fun>\n"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(* index of element *)\n",
    "\n",
    "let rec index_of elt lst =\n",
    "  let rec aux i = function\n",
    "    | [] -> None\n",
    "    | hd :: tl -> if hd = elt then Some i else aux (i+1) tl\n",
    "  in aux 0 lst\n",
    "\n",
    "let () =\n",
    "  let test_lst = [1; 2; 3; 4; 5] in\n",
    "  match index_of 3 test_lst with\n",
    "  | Some i -> Printf.printf \"Element found at index %d\\n\" i\n",
    "  | None -> Printf.printf \"Element not found\\n\" ;\n",
    "  flush stdout"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "21870c80",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val add_to_end : 'a -> 'a list -> 'a list = <fun>\n"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Element found at index 2\n",
      "1 2 3 4 5 6 \n"
     ]
    }
   ],
   "source": [
    "(* insert at end *)\n",
    "\n",
    "let add_to_end x lst = lst @ [x]\n",
    "\n",
    "let () =\n",
    "  let test_lst = [1; 2; 3; 4; 5] in\n",
    "  let result = add_to_end 6 test_lst in\n",
    "  List.iter (Printf.printf \"%d \") result;\n",
    "  print_newline ()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "69146780",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val rev : '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"
     ]
    }
   ],
   "source": [
    "(* reverse *)\n",
    "\n",
    "let rev lst =\n",
    "  let rec aux acc = function\n",
    "    | [] -> acc\n",
    "    | hd :: tl -> aux (hd :: acc) tl\n",
    "  in aux [] lst\n",
    "\n",
    "let () =\n",
    "  let test_lst = [1; 2; 3; 4; 5] in\n",
    "  let result = rev test_lst in\n",
    "  List.iter (Printf.printf \"%d \") result;\n",
    "  print_newline ()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "43ba5567",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val foldr : ('a -> 'b -> 'b) -> 'b -> 'a list -> 'b = <fun>\n"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "15\n"
     ]
    }
   ],
   "source": [
    "(* foldr *)\n",
    "\n",
    "let rec foldr f acc lst =\n",
    "  match lst with\n",
    "  | [] -> acc\n",
    "  | hd :: tl -> f hd (foldr f acc tl)\n",
    "\n",
    "let () =\n",
    "  let test_lst = [1; 2; 3; 4; 5] in\n",
    "  let result = foldr (fun x y -> x + y) 0 test_lst in\n",
    "  Printf.printf \"%d\\n\" result;\n",
    "  flush stdout"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "de2bf61b",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val length : 'a list -> int = <fun>\n"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Length: 5\n"
     ]
    }
   ],
   "source": [
    "(* length using fold *)\n",
    "\n",
    "let length lst =\n",
    "  List.fold_left (fun acc _ -> acc + 1) 0 lst\n",
    "\n",
    "let () =\n",
    "  let test_lst = [1; 2; 3; 4; 5] in\n",
    "  let result = length test_lst in\n",
    "  Printf.printf \"Length: %d\\n\" result;\n",
    "  flush stdout"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "id": "8927d672",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val append : 'a list -> 'a list -> 'a list = <fun>\n"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 2 3 4 5 6 \n"
     ]
    }
   ],
   "source": [
    "(* append using fold *)\n",
    "\n",
    "let append lst1 lst2 =\n",
    "  List.fold_right (fun x acc -> x :: acc) lst1 lst2\n",
    "\n",
    "let () =\n",
    "  let test_lst1 = [1; 2; 3] in\n",
    "  let test_lst2 = [4; 5; 6] in\n",
    "  let result = append test_lst1 test_lst2 in\n",
    "  List.iter (Printf.printf \"%d \") result;\n",
    "  print_newline ()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7fa9d5ed",
   "metadata": {},
   "source": [
    "## Unique List"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "id": "ee7202a8",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val insert_unique : 'a -> 'a list -> 'a list = <fun>\n"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 2 3 4 5 \n",
      "1 2 3 4 5 6 \n"
     ]
    }
   ],
   "source": [
    "(* insert *)\n",
    "\n",
    "let insert_unique x lst =\n",
    "  if List.mem x lst then lst else lst @ [x]\n",
    "\n",
    "let () =\n",
    "  let test_lst = [1; 2; 3; 4; 5] in\n",
    "  let result = insert_unique 3 test_lst in\n",
    "  List.iter (Printf.printf \"%d \") result;\n",
    "  print_newline ();\n",
    "  \n",
    "  let result = insert_unique 6 test_lst in\n",
    "  List.iter (Printf.printf \"%d \") result;\n",
    "  print_newline ()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "id": "ac4fd684",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val delete : 'a -> 'a list -> 'a list = <fun>\n"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 2 4 5 \n"
     ]
    }
   ],
   "source": [
    "(* delete *)\n",
    "\n",
    "let rec delete x lst =\n",
    "  match lst with\n",
    "  | [] -> []\n",
    "  | hd :: tl -> if hd = x then tl else hd :: delete x tl\n",
    "\n",
    "let () =\n",
    "  let test_lst = [1; 2; 3; 4; 5] in\n",
    "  let result = delete 3 test_lst in\n",
    "  List.iter (Printf.printf \"%d \") result;\n",
    "  print_newline ()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "id": "b9e2773b",
   "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 3 4 5 6 7 \n"
     ]
    }
   ],
   "source": [
    "(* remove the duplicates *)\n",
    "\n",
    "let remove_duplicates lst =\n",
    "  let rec remove_duplicates_aux set = function\n",
    "    | [] -> []\n",
    "    | hd :: tl ->\n",
    "      if List.mem hd set then\n",
    "        remove_duplicates_aux set tl\n",
    "      else\n",
    "        hd :: remove_duplicates_aux (hd :: set) tl\n",
    "  in\n",
    "  remove_duplicates_aux [] lst\n",
    "\n",
    "let () =\n",
    "  let test_lst = [1; 2; 3; 2; 4; 5; 4; 5; 6; 5; 7] in\n",
    "  let result = remove_duplicates test_lst in\n",
    "  List.iter (Printf.printf \"%d \") result;\n",
    "  print_newline ()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "id": "ef4e3f00",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val remove_adjacent_duplicates : 'a list -> 'a list = <fun>\n"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 2 3 4 5 \n"
     ]
    }
   ],
   "source": [
    "(* remove the adjacent duplicates *)\n",
    "\n",
    "let rec remove_adjacent_duplicates = function\n",
    "  | a :: (b :: _ as t) -> if a = b then remove_adjacent_duplicates t else a :: remove_adjacent_duplicates t\n",
    "  | smaller -> smaller\n",
    "\n",
    "let () =\n",
    "  let test_lst = [1; 2; 2; 3; 3; 3; 4; 5; 5; 5; 5] in\n",
    "  let result = remove_adjacent_duplicates test_lst in\n",
    "  List.iter (Printf.printf \"%d \") result;\n",
    "  print_newline ()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "id": "e590c1d5",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val range : 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"
     ]
    }
   ],
   "source": [
    "(* integer range *)\n",
    "\n",
    "let rec range a b =\n",
    "  if a > b then []\n",
    "  else a :: range (a + 1) b\n",
    "\n",
    "let () =\n",
    "  let result = range 1 5 in\n",
    "  List.iter (Printf.printf \"%d \") result;\n",
    "  print_newline ()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f6ecec03",
   "metadata": {},
   "source": [
    "## Strictly Sorted List"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "id": "1e2f5b7a",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val insert_sorted : '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 \n"
     ]
    }
   ],
   "source": [
    "(* insert *)\n",
    "\n",
    "let rec insert_sorted x lst =\n",
    "  match lst with\n",
    "  | [] -> [x]\n",
    "  | hd :: tl -> if x <= hd then x :: lst else hd :: insert_sorted x tl\n",
    "\n",
    "let () =\n",
    "  let test_lst = [1; 2; 4; 5] in\n",
    "  let result = insert_sorted 3 test_lst in\n",
    "  List.iter (Printf.printf \"%d \") result;\n",
    "  print_newline ()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "id": "1635e2f7",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val delete_sorted : 'a -> 'a list -> 'a list = <fun>\n"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 2 4 5 \n"
     ]
    }
   ],
   "source": [
    "(* delete *)\n",
    "\n",
    "let rec delete_sorted x lst =\n",
    "  match lst with\n",
    "  | [] -> []\n",
    "  | hd :: tl -> if x = hd then tl else hd :: delete_sorted x tl\n",
    "\n",
    "let () =\n",
    "  let test_lst = [1; 2; 3; 4; 5] in\n",
    "  let result = delete_sorted 3 test_lst in\n",
    "  List.iter (Printf.printf \"%d \") result;\n",
    "  print_newline ()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "id": "625ded76",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val intersect_sorted : 'a list -> 'a list -> 'a list = <fun>\n"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2 4 \n"
     ]
    }
   ],
   "source": [
    "(* intersect *)\n",
    "\n",
    "let rec intersect_sorted lst1 lst2 =\n",
    "  match lst1, lst2 with\n",
    "  | [], _ | _, [] -> []\n",
    "  | hd1 :: tl1, hd2 :: tl2 ->\n",
    "    if hd1 = hd2 then hd1 :: intersect_sorted tl1 tl2\n",
    "    else if hd1 < hd2 then intersect_sorted tl1 lst2\n",
    "    else intersect_sorted lst1 tl2\n",
    "\n",
    "let () =\n",
    "  let test_lst1 = [1; 2; 3; 4; 5] in\n",
    "  let test_lst2 = [2; 4; 6; 8] in\n",
    "  let result = intersect_sorted test_lst1 test_lst2 in\n",
    "  List.iter (Printf.printf \"%d \") result;\n",
    "  print_newline ()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1fe51ad2",
   "metadata": {},
   "source": [
    "## Sorting"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "id": "00e918a6",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val insert : 'a -> 'a list -> 'a list = <fun>\n"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val insertion_sort : '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 \n"
     ]
    }
   ],
   "source": [
    "(* insert(sorted) *)\n",
    "\n",
    "let rec insert x = function\n",
    "  | [] -> [x]\n",
    "  | y :: ys -> if x <= y then x :: y :: ys else y :: insert x ys\n",
    ";;\n",
    "\n",
    "let rec insertion_sort = function\n",
    "  | [] -> []\n",
    "  | x :: xs -> insert x (insertion_sort xs)\n",
    ";;\n",
    "\n",
    "let () =\n",
    "  let test_lst = [4; 2; 5; 1; 3] in\n",
    "  let result = insertion_sort test_lst in\n",
    "  List.iter (Printf.printf \"%d \") result;\n",
    "  print_newline ()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "id": "469380f5",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val insert : 'a -> 'a list -> 'a list = <fun>\n"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val insertion_sort : 'a list -> 'a list = <fun>\n"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 2 3 4 5 \n"
     ]
    }
   ],
   "source": [
    "(* insertion_sort *)\n",
    "\n",
    "let rec insert x = function\n",
    "  | [] -> [x]\n",
    "  | y :: ys -> if x <= y then x :: y :: ys else y :: insert x ys\n",
    ";;\n",
    "\n",
    "let rec insertion_sort = function\n",
    "  | [] -> []\n",
    "  | x :: xs -> insert x (insertion_sort xs)\n",
    ";;\n",
    "\n",
    "let () =\n",
    "  let test_lst = [4; 2; 5; 1; 3] in\n",
    "  let result = insertion_sort test_lst in\n",
    "  List.iter (Printf.printf \"%d \") result;\n",
    "  print_newline ()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "id": "b1ddbcc6",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val insert : 'a -> 'a list -> 'a list = <fun>\n"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val sort : '_weak1 list -> '_weak1 list = <fun>\n"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 2 3 4 5 \n"
     ]
    }
   ],
   "source": [
    "(* sort by folding *)\n",
    "\n",
    "let insert x ys =\n",
    "  let rec aux acc = function\n",
    "    | [] -> List.rev (x :: acc)\n",
    "    | y :: ys as l -> if x <= y then List.rev_append acc (x :: l) else aux (y :: acc) ys\n",
    "  in aux [] ys\n",
    ";;\n",
    "\n",
    "let sort = List.fold_left (fun acc x -> insert x acc) []\n",
    "\n",
    "let () =\n",
    "  let test_lst = [4; 2; 5; 1; 3] in\n",
    "  let result = sort test_lst in\n",
    "  List.iter (Printf.printf \"%d \") result;\n",
    "  print_newline ()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "id": "da3caa4f",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val min_element : 'a list -> 'a = <fun>\n"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val extract_min : 'a list -> 'a * 'a list = <fun>\n"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Min: 0\n",
      "Rest: 4 2 5 1 \n"
     ]
    }
   ],
   "source": [
    "(* extract minimum *)\n",
    "\n",
    "let min_element = function\n",
    "  | [] -> failwith \"Empty list has no minimum\"\n",
    "  | hd :: tl -> List.fold_left min hd tl\n",
    "\n",
    "let extract_min lst = \n",
    "  let min = min_element lst in\n",
    "  (min, List.filter ((<>) min) lst)\n",
    "\n",
    "let () =\n",
    "  let test_lst = [4; 2; 5; 1; 0] in\n",
    "  let (min, rest) = extract_min test_lst in\n",
    "  Printf.printf \"Min: %d\\n\" min;\n",
    "  Printf.printf \"Rest: \";\n",
    "  List.iter (Printf.printf \"%d \") rest;\n",
    "  print_newline ()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "id": "f7227a81",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val selection_sort : 'a list -> 'a list = <fun>\n"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val min_element : 'a list -> 'a = <fun>\n"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val extract_min : 'a list -> 'a * 'a list = <fun>\n"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 2 3 4 5 \n"
     ]
    }
   ],
   "source": [
    "(* selection sort *)\n",
    "\n",
    "let rec selection_sort lst =\n",
    "  match lst with\n",
    "  | [] -> []\n",
    "  | _ -> \n",
    "    let min, rest = extract_min lst in\n",
    "    min :: selection_sort rest\n",
    "\n",
    "let min_element = function\n",
    "  | [] -> failwith \"Empty list has no minimum\"\n",
    "  | hd :: tl -> List.fold_left min hd tl\n",
    "\n",
    "let extract_min lst = \n",
    "  let min = min_element lst in\n",
    "  (min, List.filter ((<>) min) lst)\n",
    "\n",
    "let () =\n",
    "  let test_lst = [4; 2; 5; 1; 3] in\n",
    "  let result = selection_sort test_lst in\n",
    "  List.iter (Printf.printf \"%d \") result;\n",
    "  print_newline ()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "de0f182c",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val split : 'a list -> 'a list * 'a list = <fun>\n"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "First half: 1 2 3 \n",
      "Second half: 4 5 6 7 \n"
     ]
    }
   ],
   "source": [
    "(* balanced split *)\n",
    "\n",
    "let split lst =\n",
    "  let rec aux i acc = function\n",
    "    | [] -> (List.rev acc, [])\n",
    "    | hd :: tl as l -> if i = 0 then (List.rev acc, l) else aux (i - 1) (hd :: acc) tl\n",
    "  in\n",
    "  aux (List.length lst / 2) [] lst\n",
    ";;\n",
    "\n",
    "let () =\n",
    "  let test_lst = [1; 2; 3; 4; 5; 6; 7] in\n",
    "  let (lst1, lst2) = split test_lst in\n",
    "  Printf.printf \"First half: \";\n",
    "  List.iter (Printf.printf \"%d \") lst1;\n",
    "  print_newline ();\n",
    "  Printf.printf \"Second half: \";\n",
    "  List.iter (Printf.printf \"%d \") lst2;\n",
    "  print_newline ()\n",
    ";;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "id": "75366f36",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val merge : 'a list -> 'a list -> 'a list = <fun>\n"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 2 3 4 5 6 \n"
     ]
    }
   ],
   "source": [
    "(* merge *)\n",
    "\n",
    "let rec merge l1 l2 =\n",
    "  match l1, l2 with\n",
    "  | [], l | l, [] -> l\n",
    "  | h1 :: t1, h2 :: t2 ->\n",
    "    if h1 <= h2 then h1 :: merge t1 l2 else h2 :: merge l1 t2\n",
    ";;\n",
    "\n",
    "let () =\n",
    "  let lst1 = [1; 3; 5]\n",
    "  and lst2 = [2; 4; 6] in\n",
    "  let result = merge lst1 lst2 in\n",
    "  List.iter (Printf.printf \"%d \") result;\n",
    "  print_newline ()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "id": "0271f813",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val merge_sort : 'a list -> 'a list = <fun>\n"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 2 3 4 5 \n"
     ]
    }
   ],
   "source": [
    "(* merge sort *)\n",
    "\n",
    "let rec merge_sort lst =\n",
    "  match lst with\n",
    "  | [] -> []\n",
    "  | [x] -> [x]\n",
    "  | _ ->\n",
    "    let left, right = split lst in\n",
    "    merge (merge_sort left) (merge_sort right)\n",
    "\n",
    "let () =\n",
    "  let test_lst = [4; 2; 5; 1; 3] in\n",
    "  let result = merge_sort test_lst in\n",
    "  List.iter (Printf.printf \"%d \") result;\n",
    "  print_newline ()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "id": "0896fe22",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val partition : ('a -> bool) -> 'a list -> 'a list * 'a list = <fun>\n"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Evens: 2 4 6 \n",
      "Odds: 1 3 5 \n"
     ]
    }
   ],
   "source": [
    "(* partition *)\n",
    "\n",
    "let partition pred lst =\n",
    "  let rec aux acc1 acc2 = function\n",
    "    | [] -> (List.rev acc1, List.rev acc2)\n",
    "    | hd :: tl ->\n",
    "      if pred hd then aux (hd :: acc1) acc2 tl\n",
    "      else aux acc1 (hd :: acc2) tl\n",
    "  in\n",
    "  aux [] [] lst\n",
    ";;\n",
    "\n",
    "let () =\n",
    "  let test_lst = [1; 2; 3; 4; 5; 6] in\n",
    "  let pred x = x mod 2 = 0 in\n",
    "  let (evens, odds) = partition pred test_lst in\n",
    "  Printf.printf \"Evens: \";\n",
    "  List.iter (Printf.printf \"%d \") evens;\n",
    "  print_newline ();\n",
    "  Printf.printf \"Odds: \";\n",
    "  List.iter (Printf.printf \"%d \") odds;\n",
    "  print_newline ()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "id": "394b3913",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val append_with_pivot : 'a list -> 'a -> 'a list -> 'a list = <fun>\n"
      ]
     },
     "execution_count": 38,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 2 3 4 5 6 7 \n"
     ]
    }
   ],
   "source": [
    "(* append with pivot *)\n",
    "\n",
    "let append_with_pivot l1 pivot l2 = l1 @ [pivot] @ l2\n",
    "\n",
    "let () =\n",
    "  let lst1 = [1; 2; 3]\n",
    "  and pivot = 4\n",
    "  and lst2 = [5; 6; 7] in\n",
    "  let result = append_with_pivot lst1 pivot lst2 in\n",
    "  List.iter (Printf.printf \"%d \") result;\n",
    "  print_newline ()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "id": "276eb6bd",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val partition : 'a -> 'a list -> 'a list * 'a list * 'a list = <fun>\n"
      ]
     },
     "execution_count": 39,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val quick_sort : 'a list -> 'a list = <fun>\n"
      ]
     },
     "execution_count": 39,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2 \n"
     ]
    }
   ],
   "source": [
    "(* quicksort *)\n",
    "\n",
    "(* Incorrect Code *)\n",
    "\n",
    "let partition pivot lst =\n",
    "  let rec aux less equal greater = function\n",
    "    | [] -> (List.rev less, List.rev equal, List.rev greater)\n",
    "    | hd :: tl ->\n",
    "      if hd < pivot then aux (hd :: less) equal greater tl\n",
    "      else if hd > pivot then aux less equal (hd :: greater) tl\n",
    "      else aux less (hd :: equal) greater tl\n",
    "  in\n",
    "  aux [] [] [] lst\n",
    ";;\n",
    "\n",
    "let rec quick_sort = function\n",
    "  | [] -> []\n",
    "  | pivot :: tl ->\n",
    "    let less, equal, greater = partition pivot tl in\n",
    "    quick_sort less @ equal @ quick_sort greater\n",
    ";;\n",
    "\n",
    "let () =\n",
    "  let test_lst = [4; 2; 5; 1; 3; 2] in\n",
    "  let result = quick_sort test_lst in\n",
    "  List.iter (Printf.printf \"%d \") result;\n",
    "  print_newline ()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "52047f01",
   "metadata": {},
   "source": [
    "## Trees"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "id": "248a105b",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "type binary_tree = Empty | Node of int * binary_tree * binary_tree\n"
      ]
     },
     "execution_count": 40,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "type binary_tree =\n",
    "  | Empty\n",
    "  | Node of int * binary_tree * binary_tree\n",
    ";;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "id": "f067b153",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val is_member : int -> binary_tree -> bool = <fun>\n"
      ]
     },
     "execution_count": 41,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "true\n",
      "false\n"
     ]
    }
   ],
   "source": [
    "(* is member *)\n",
    "\n",
    "let rec is_member x = function\n",
    "  | Empty -> false\n",
    "  | Node (y, left, right) ->\n",
    "    if x = y then true\n",
    "    else if x < y then is_member x left\n",
    "    else is_member x right\n",
    ";;\n",
    "\n",
    "let () =\n",
    "  let tree =\n",
    "    Node (4,\n",
    "      Node (2,\n",
    "        Node (1, Empty, Empty),\n",
    "        Node (3, Empty, Empty)),\n",
    "      Node (5, Empty, Empty))\n",
    "  in\n",
    "  Printf.printf \"%b\\n\" (is_member 3 tree);  (* Prints: true *)\n",
    "  Printf.printf \"%b\\n\" (is_member 6 tree);  (* Prints: false *)\n",
    "  flush stdout"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "id": "07c9ce11",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val node_count : binary_tree -> int = <fun>\n"
      ]
     },
     "execution_count": 42,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5\n"
     ]
    }
   ],
   "source": [
    "(* node count *)\n",
    "\n",
    "let rec node_count = function\n",
    "  | Empty -> 0\n",
    "  | Node (_, left, right) -> 1 + node_count left + node_count right\n",
    ";;\n",
    "\n",
    "let () =\n",
    "  let tree =\n",
    "    Node (4,\n",
    "      Node (2,\n",
    "        Node (1, Empty, Empty),\n",
    "        Node (3, Empty, Empty)),\n",
    "      Node (5, Empty, Empty))\n",
    "  in\n",
    "  Printf.printf \"%d\\n\" (node_count tree);  (* Prints: 5 *)\n",
    "  flush stdout"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "id": "54c91101",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val pre_order : binary_tree -> int list = <fun>\n"
      ]
     },
     "execution_count": 43,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4 2 1 3 5 \n"
     ]
    }
   ],
   "source": [
    "(* preorder *)\n",
    "\n",
    "let rec pre_order = function\n",
    "  | Empty -> []\n",
    "  | Node (value, left, right) -> [value] @ pre_order left @ pre_order right\n",
    ";;\n",
    "\n",
    "let () =\n",
    "  let tree =\n",
    "    Node (4,\n",
    "      Node (2,\n",
    "        Node (1, Empty, Empty),\n",
    "        Node (3, Empty, Empty)),\n",
    "      Node (5, Empty, Empty))\n",
    "  in\n",
    "  let result = pre_order tree in\n",
    "  List.iter (Printf.printf \"%d \") result;  (* Prints: 4 2 1 3 5 *)\n",
    "  print_newline ()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5ccf746a",
   "metadata": {},
   "source": [
    "## BST"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "id": "e33f3dee",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "type binary_tree = Empty | Node of int * binary_tree * binary_tree\n"
      ]
     },
     "execution_count": 44,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "type binary_tree =\n",
    "  | Empty\n",
    "  | Node of int * binary_tree * binary_tree\n",
    ";;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "id": "e2ebdcdf",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val is_member : int -> binary_tree -> bool = <fun>\n"
      ]
     },
     "execution_count": 45,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "true\n",
      "false\n"
     ]
    }
   ],
   "source": [
    "(* is member *)\n",
    "\n",
    "let rec is_member x = function\n",
    "  | Empty -> false\n",
    "  | Node (y, left, right) ->\n",
    "    if x = y then true\n",
    "    else if x < y then is_member x left\n",
    "    else is_member x right\n",
    ";;\n",
    "\n",
    "let () =\n",
    "  let tree =\n",
    "    Node (4,\n",
    "      Node (2,\n",
    "        Node (1, Empty, Empty),\n",
    "        Node (3, Empty, Empty)),\n",
    "      Node (5, Empty, Empty))\n",
    "  in\n",
    "  Printf.printf \"%b\\n\" (is_member 3 tree);  (* Prints: true *)\n",
    "  Printf.printf \"%b\\n\" (is_member 6 tree);  (* Prints: false *)\n",
    "  flush stdout"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "id": "5e769e5a",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val insert : int -> binary_tree -> binary_tree = <fun>\n"
      ]
     },
     "execution_count": 46,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val print_tree : binary_tree -> unit = <fun>\n"
      ]
     },
     "execution_count": 46,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 2 3 4 5 6 \n"
     ]
    }
   ],
   "source": [
    "(* insert *)\n",
    "\n",
    "let rec insert x = function\n",
    "  | Empty -> Node (x, Empty, Empty)\n",
    "  | Node (y, left, right) as node ->\n",
    "    if x = y then node  (* No duplicates *)\n",
    "    else if x < y then Node (y, insert x left, right)\n",
    "    else Node (y, left, insert x right)\n",
    ";;\n",
    "\n",
    "let rec print_tree = function\n",
    "  | Empty -> ()\n",
    "  | Node (value, left, right) ->\n",
    "    print_tree left;\n",
    "    Printf.printf \"%d \" value;\n",
    "    print_tree right\n",
    ";;\n",
    "\n",
    "let () =\n",
    "  let tree = \n",
    "    Node (4, \n",
    "      Node (2,\n",
    "        Node (1, Empty, Empty),\n",
    "        Node (3, Empty, Empty)),\n",
    "      Node (5, Empty, Empty))\n",
    "  in\n",
    "  let new_tree = insert 6 tree in\n",
    "  print_tree new_tree;  (* Should print: 1 2 3 4 5 6 *)\n",
    "  print_newline ()\n",
    ";;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "id": "20e82868",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val find_min : binary_tree -> int = <fun>\n"
      ]
     },
     "execution_count": 47,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val delete : int -> binary_tree -> binary_tree = <fun>\n"
      ]
     },
     "execution_count": 47,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 3 4 5 \n"
     ]
    }
   ],
   "source": [
    "(* delete *)\n",
    "\n",
    "let rec find_min = function\n",
    "  | Empty -> failwith \"Empty tree\"\n",
    "  | Node (x, Empty, _) -> x\n",
    "  | Node (_, left, _) -> find_min left\n",
    "\n",
    "let rec delete x = function\n",
    "  | Empty -> Empty\n",
    "  | Node (y, left, right) ->\n",
    "    if x < y then Node (y, delete x left, right)\n",
    "    else if x > y then Node (y, left, delete x right)\n",
    "    else match left, right with\n",
    "      | Empty, Empty -> Empty\n",
    "      | Empty, right -> right\n",
    "      | left, Empty -> left\n",
    "      | left, right ->\n",
    "        let min_right = find_min right in\n",
    "        Node (min_right, left, delete min_right right)\n",
    ";;\n",
    "\n",
    "let () =\n",
    "  let tree = \n",
    "    Node (4, \n",
    "      Node (2,\n",
    "        Node (1, Empty, Empty),\n",
    "        Node (3, Empty, Empty)),\n",
    "      Node (5, Empty, Empty))\n",
    "  in\n",
    "  let new_tree = delete 2 tree in\n",
    "  print_tree new_tree;  (* Should print: 1 3 4 5 *)\n",
    "  print_newline ()\n",
    ";;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "id": "e3e9989a",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val insert : int -> binary_tree -> binary_tree = <fun>\n"
      ]
     },
     "execution_count": 48,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val bst_sort : int list -> binary_tree = <fun>\n"
      ]
     },
     "execution_count": 48,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val in_order_traversal : binary_tree -> int list = <fun>\n"
      ]
     },
     "execution_count": 48,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 2 3 4 5 \n"
     ]
    }
   ],
   "source": [
    "(* bst sort *)\n",
    "\n",
    "let rec insert 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 x left, right)\n",
    "    else Node (y, left, insert x right)\n",
    ";;\n",
    "\n",
    "let rec bst_sort = function\n",
    "  | [] -> Empty\n",
    "  | hd :: tl -> insert hd (bst_sort tl)\n",
    ";;\n",
    "\n",
    "let rec in_order_traversal = function\n",
    "  | Empty -> []\n",
    "  | Node (value, left, right) -> in_order_traversal left @ [value] @ in_order_traversal right\n",
    ";;\n",
    "\n",
    "let () =\n",
    "  let input_list = [4; 2; 5; 1; 3] in\n",
    "  let sorted_tree = bst_sort input_list in\n",
    "  let sorted_list = in_order_traversal sorted_tree in\n",
    "  List.iter (Printf.printf \"%d \") sorted_list;  (* Prints: 1 2 3 4 5 *)\n",
    "  print_newline ()\n",
    ";;\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f690bed0",
   "metadata": {},
   "source": [
    "## Binary Heap"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "id": "b88d099b",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "type heap = { mutable size : int; mutable data : int array; }\n"
      ]
     },
     "execution_count": 49,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "type heap = {\n",
    "  mutable size: int;\n",
    "  mutable data: int array\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "f4db4dcf",
   "metadata": {},
   "outputs": [
    {
     "ename": "error",
     "evalue": "compile_error",
     "output_type": "error",
     "traceback": [
      "File \"[1]\", line 5, characters 17-21:\n5 |     if i >= heap.size then\n                     ^^^^\nError: Unbound record field size\n"
     ]
    }
   ],
   "source": [
    "(* is member *)\n",
    "\n",
    "let is_member heap x =\n",
    "  let rec dfs i =\n",
    "    if i >= heap.size then\n",
    "      false\n",
    "    else\n",
    "      heap.data.(i) = x || dfs (2 * i + 1) || dfs (2 * i + 2)\n",
    "  in\n",
    "  dfs 0\n",
    "\n",
    "let () =\n",
    "  let heap = create () in\n",
    "  insert heap 3;\n",
    "  insert heap 1;\n",
    "  insert heap 4;\n",
    "  insert heap 1;\n",
    "  insert heap 5;\n",
    "  insert heap 9;\n",
    "  print_endline (if is_member heap 5 then \"true\" else \"false\"); (* This should print \"true\" *)\n",
    "  print_endline (if is_member heap 10 then \"true\" else \"false\"); (* This should print \"false\" *)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "id": "848fb724",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val create : unit -> heap = <fun>\n"
      ]
     },
     "execution_count": 51,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val swap : heap -> int -> int -> unit = <fun>\n"
      ]
     },
     "execution_count": 51,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val resize : heap -> unit = <fun>\n"
      ]
     },
     "execution_count": 51,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val bubble_up : heap -> int -> unit = <fun>\n"
      ]
     },
     "execution_count": 51,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val insert : heap -> int -> unit = <fun>\n"
      ]
     },
     "execution_count": 51,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "6\n"
     ]
    }
   ],
   "source": [
    "(* insert *)\n",
    "\n",
    "let create () = { size = 0; data = Array.make 1 0 }\n",
    "\n",
    "let swap heap i j =\n",
    "  let tmp = heap.data.(i) in\n",
    "  heap.data.(i) <- heap.data.(j);\n",
    "  heap.data.(j) <- tmp\n",
    "\n",
    "let resize heap =\n",
    "  let data' = Array.make (2 * heap.size) 0 in\n",
    "  Array.blit heap.data 0 data' 0 heap.size;\n",
    "  heap.data <- data'\n",
    "\n",
    "let rec bubble_up heap i =\n",
    "  if i > 0 then\n",
    "    let parent = (i - 1) / 2 in\n",
    "    if heap.data.(i) < heap.data.(parent) then begin\n",
    "      swap heap i parent;\n",
    "      bubble_up heap parent\n",
    "    end\n",
    "\n",
    "let insert heap x =\n",
    "  if heap.size = Array.length heap.data then\n",
    "    resize heap;\n",
    "  heap.data.(heap.size) <- x;\n",
    "  bubble_up heap heap.size;\n",
    "  heap.size <- heap.size + 1\n",
    "\n",
    "\n",
    "let () =\n",
    "  let heap = create () in\n",
    "  insert heap 3;\n",
    "  insert heap 1;\n",
    "  insert heap 4;\n",
    "  insert heap 1;\n",
    "  insert heap 5;\n",
    "  insert heap 9;\n",
    "  print_int heap.data.(0); (* This should print 1, the smallest element *)\n",
    "  print_newline ();\n",
    "  print_int heap.size; (* This should print 6, the total number of elements in heap *)\n",
    "  print_newline ()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "id": "fa2d97af",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val create_with_one : int -> heap = <fun>\n"
      ]
     },
     "execution_count": 52,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3\n",
      "1\n"
     ]
    }
   ],
   "source": [
    "(* 1-element constructor *)\n",
    "\n",
    "let create_with_one x = \n",
    "  let heap = create () in\n",
    "  insert heap x;\n",
    "  heap\n",
    "\n",
    "let () =\n",
    "  let heap = create_with_one 3 in\n",
    "  print_int heap.data.(0); (* This should print 3 *)\n",
    "  print_newline ();\n",
    "  print_int heap.size; (* This should print 1 *)\n",
    "  print_newline ()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "id": "b2cf9df7",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val create_with_two : int -> int -> heap = <fun>\n"
      ]
     },
     "execution_count": 53,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "2\n"
     ]
    }
   ],
   "source": [
    "(* 2-element constructor *)\n",
    "\n",
    "let create_with_two x y = \n",
    "  let heap = create () in\n",
    "  insert heap x;\n",
    "  insert heap y;\n",
    "  heap\n",
    "\n",
    "let () =\n",
    "  let heap = create_with_two 3 1 in\n",
    "  print_int heap.data.(0); (* This should print 1, the smallest element *)\n",
    "  print_newline ();\n",
    "  print_int heap.size; (* This should print 2, the total number of elements in heap *)\n",
    "  print_newline ()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "id": "81aeab56",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val create_with_three : int -> int -> int -> heap = <fun>\n"
      ]
     },
     "execution_count": 54,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "3\n"
     ]
    }
   ],
   "source": [
    "(* 3-element constructor *)\n",
    "\n",
    "let create_with_three x y z = \n",
    "  let heap = create () in\n",
    "  insert heap x;\n",
    "  insert heap y;\n",
    "  insert heap z;\n",
    "  heap\n",
    "\n",
    "let () =\n",
    "  let heap = create_with_three 3 1 2 in\n",
    "  print_int heap.data.(0); (* This should print 1, the smallest element *)\n",
    "  print_newline ();\n",
    "  print_int heap.size; (* This should print 3, the total number of elements in heap *)\n",
    "  print_newline ()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f5bbe4b2",
   "metadata": {},
   "source": [
    "## AVL"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "id": "060f6902",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "type 'a avl_tree = Empty | Node of 'a * int * 'a avl_tree * 'a avl_tree\n"
      ]
     },
     "execution_count": 55,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "type 'a avl_tree =\n",
    "  | Empty\n",
    "  | Node of 'a * int * 'a avl_tree * 'a avl_tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "id": "63850e00",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val height : 'a avl_tree -> int = <fun>\n"
      ]
     },
     "execution_count": 56,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val rotate_left : 'a avl_tree -> 'a avl_tree = <fun>\n"
      ]
     },
     "execution_count": 56,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Original tree:\n",
      "10 (height: 2)\n",
      "5 (height: 1)\n",
      "20 (height: 1)\n",
      "Rotated tree:\n",
      "20 (height: 3)\n",
      "10 (height: 2)\n",
      "5 (height: 1)\n"
     ]
    }
   ],
   "source": [
    "(* rotate left *)\n",
    "\n",
    "let height = function\n",
    "  | Empty -> -1\n",
    "  | Node (_, h, _, _) -> h\n",
    "\n",
    "let rotate_left = function\n",
    "  | Empty -> Empty\n",
    "  | Node (k1, _, l1, Node (k2, _, l2, r2)) ->\n",
    "    let hl1 = height l1 in\n",
    "    let hl2 = height l2 in\n",
    "    let hr2 = height r2 in\n",
    "    let h1 = 1 + max hl1 hl2 in\n",
    "    let h2 = 1 + max h1 hr2 in\n",
    "    Node (k2, h2, Node (k1, h1, l1, l2), r2)\n",
    "  | _ -> failwith \"rotate_left: Invalid argument\"\n",
    "\n",
    "let () =\n",
    "  (* Create a small AVL tree *)\n",
    "  let tree = Node (10, 2, Node (5, 1, Empty, Empty), Node (20, 1, Empty, Empty)) in\n",
    "\n",
    "  (* Perform a left rotation on the tree *)\n",
    "  let rotated_tree = rotate_left tree in\n",
    "\n",
    "  (* Function to print a tree *)\n",
    "  let rec print_tree = function\n",
    "    | Empty -> ()\n",
    "    | Node (k, h, l, r) ->\n",
    "        print_int k; print_string \" (height: \"; print_int h; print_endline \")\";\n",
    "        print_tree l;\n",
    "        print_tree r\n",
    "  in\n",
    "\n",
    "  (* Print the original and rotated trees *)\n",
    "  print_endline \"Original tree:\";\n",
    "  print_tree tree;\n",
    "  print_endline \"Rotated tree:\";\n",
    "  print_tree rotated_tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "id": "b5c5dc10",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val rotate_right : 'a avl_tree -> 'a avl_tree = <fun>\n"
      ]
     },
     "execution_count": 57,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Original tree:\n",
      "20 (height: 2)\n",
      "10 (height: 1)\n",
      "30 (height: 1)\n",
      "Rotated tree:\n",
      "10 (height: 3)\n",
      "20 (height: 2)\n",
      "30 (height: 1)\n"
     ]
    }
   ],
   "source": [
    "(* rotate right *)\n",
    "\n",
    "let rotate_right = function\n",
    "  | Empty -> Empty\n",
    "  | Node (k1, _, Node (k2, _, l2, r2), r1) ->\n",
    "    let hr1 = height r1 in\n",
    "    let hl2 = height l2 in\n",
    "    let hr2 = height r2 in\n",
    "    let h1 = 1 + max hr1 hr2 in\n",
    "    let h2 = 1 + max hl2 h1 in\n",
    "    Node (k2, h2, l2, Node (k1, h1, r2, r1))\n",
    "  | _ -> failwith \"rotate_right: Invalid argument\"\n",
    "\n",
    "let () =\n",
    "  (* Create a small AVL tree *)\n",
    "  let tree = Node (20, 2, Node (10, 1, Empty, Empty), Node (30, 1, Empty, Empty)) in\n",
    "\n",
    "  (* Perform a right rotation on the tree *)\n",
    "  let rotated_tree = rotate_right tree in\n",
    "\n",
    "  (* Function to print a tree *)\n",
    "  let rec print_tree = function\n",
    "    | Empty -> ()\n",
    "    | Node (k, h, l, r) ->\n",
    "        print_int k; print_string \" (height: \"; print_int h; print_endline \")\";\n",
    "        print_tree l;\n",
    "        print_tree r\n",
    "  in\n",
    "\n",
    "  (* Print the original and rotated trees *)\n",
    "  print_endline \"Original tree:\";\n",
    "  print_tree tree;\n",
    "  print_endline \"Rotated tree:\";\n",
    "  print_tree rotated_tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "id": "98fe4626",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val balance : 'a avl_tree -> 'a avl_tree = <fun>\n"
      ]
     },
     "execution_count": 58,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Original tree:\n",
      "30 (height: 3)\n",
      "20 (height: 2)\n",
      "10 (height: 1)\n",
      "Balanced tree:\n",
      "20 (height: 2)\n",
      "10 (height: 1)\n",
      "30 (height: 0)\n"
     ]
    }
   ],
   "source": [
    "(* balance *)\n",
    "\n",
    "(* Something seems to be incorrect *)\n",
    "\n",
    "let balance = function\n",
    "  | Empty -> Empty\n",
    "  | Node (k, _, l, r) as node ->\n",
    "      let hl = height l in\n",
    "      let hr = height r in\n",
    "      if hl > hr + 1 then\n",
    "        match l with\n",
    "        | Node (lk, _, ll, lr) ->\n",
    "            if height ll >= height lr then rotate_right node\n",
    "            else rotate_right (Node (k, 0, rotate_left l, r))\n",
    "        | Empty -> failwith \"balance: Invalid argument\"\n",
    "      else if hr > hl + 1 then\n",
    "        match r with\n",
    "        | Node (rk, _, rl, rr) ->\n",
    "            if height rr >= height rl then rotate_left node\n",
    "            else rotate_left (Node (k, 0, l, rotate_right r))\n",
    "        | Empty -> failwith \"balance: Invalid argument\"\n",
    "      else\n",
    "        node\n",
    "\n",
    "let () =\n",
    "  (* Create an unbalanced AVL tree *)\n",
    "  let tree = Node (30, 3, Node (20, 2, Node (10, 1, Empty, Empty), Empty), Empty) in\n",
    "\n",
    "  (* Balance the tree *)\n",
    "  let balanced_tree = balance tree in\n",
    "\n",
    "  (* Function to print a tree *)\n",
    "  let rec print_tree = function\n",
    "    | Empty -> ()\n",
    "    | Node (k, h, l, r) ->\n",
    "        print_int k; print_string \" (height: \"; print_int h; print_endline \")\";\n",
    "        print_tree l;\n",
    "        print_tree r\n",
    "  in\n",
    "\n",
    "  (* Print the original and balanced trees *)\n",
    "  print_endline \"Original tree:\";\n",
    "  print_tree tree;\n",
    "  print_endline \"Balanced tree:\";\n",
    "  print_tree balanced_tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "id": "58e2a886",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val insert : 'a -> 'a avl_tree -> 'a avl_tree = <fun>\n"
      ]
     },
     "execution_count": 59,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Tree after insertions:\n",
      "20 (height: 2)\n",
      "5 (height: 1)\n",
      "10 (height: 0)\n",
      "30 (height: 0)\n"
     ]
    }
   ],
   "source": [
    "(* insert *)\n",
    "\n",
    "(* Incorrect Code *)\n",
    "\n",
    "let rec insert x = function\n",
    "  | Empty -> Node (x, 0, Empty, Empty)\n",
    "  | Node (k, _, l, r) as node ->\n",
    "    if x < k then\n",
    "      let new_l = insert x l in\n",
    "      balance (Node (k, 1 + max (height new_l) (height r), new_l, r))\n",
    "    else if x > k then\n",
    "      let new_r = insert x r in\n",
    "      balance (Node (k, 1 + max (height l) (height new_r), l, new_r))\n",
    "    else\n",
    "      node (* duplicate element, simply return the node *)\n",
    "\n",
    "let () =\n",
    "  (* Create an empty AVL tree *)\n",
    "  let tree = Empty in\n",
    "\n",
    "  (* Insert elements into the tree *)\n",
    "  let tree = List.fold_right insert [10; 20; 30; 5] tree in\n",
    "\n",
    "  (* Function to print a tree *)\n",
    "  let rec print_tree = function\n",
    "    | Empty -> ()\n",
    "    | Node (k, h, l, r) ->\n",
    "      print_int k; print_string \" (height: \"; print_int h; print_endline \")\";\n",
    "      print_tree l;\n",
    "      print_tree r\n",
    "  in\n",
    "\n",
    "  (* Print the tree *)\n",
    "  print_endline \"Tree after insertions:\";\n",
    "  print_tree tree;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "id": "ebfe73ff",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val find_min : 'a avl_tree -> 'a = <fun>\n"
      ]
     },
     "execution_count": 60,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val remove_min : 'a avl_tree -> 'a avl_tree = <fun>\n"
      ]
     },
     "execution_count": 60,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val extract_min : 'a avl_tree -> 'a * 'a avl_tree = <fun>\n"
      ]
     },
     "execution_count": 60,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Minimum:\n",
      "5\n",
      "Tree after extraction:\n",
      "20 (height: 2)\n",
      "10 (height: 0)\n",
      "30 (height: 0)\n"
     ]
    }
   ],
   "source": [
    "(* extract minimum *)\n",
    "\n",
    "(* Partially Incorrect *)\n",
    "\n",
    "let rec find_min = function\n",
    "  | Empty -> failwith \"find_min: tree is empty\"\n",
    "  | Node (k, _, Empty, _) -> k\n",
    "  | Node (_, _, l, _) -> find_min l\n",
    "\n",
    "let rec remove_min = function\n",
    "  | Empty -> failwith \"remove_min: tree is empty\"\n",
    "  | Node (_, _, Empty, r) -> r\n",
    "  | Node (k, h, l, r) -> balance (Node (k, h, remove_min l, r))\n",
    "\n",
    "let extract_min t =\n",
    "  let min = find_min t in\n",
    "  let t = remove_min t in\n",
    "  (min, t)\n",
    "\n",
    "let () =\n",
    "  (* Create an empty AVL tree *)\n",
    "  let tree = Empty in\n",
    "\n",
    "  (* Insert elements into the tree *)\n",
    "  let tree = List.fold_right insert [10; 20; 30; 5] tree in\n",
    "\n",
    "  (* Extract the minimum *)\n",
    "  let (min, tree) = extract_min tree in\n",
    "\n",
    "  (* Function to print a tree *)\n",
    "  let rec print_tree = function\n",
    "    | Empty -> ()\n",
    "    | Node (k, h, l, r) ->\n",
    "      print_int k; print_string \" (height: \"; print_int h; print_endline \")\";\n",
    "      print_tree l;\n",
    "      print_tree r\n",
    "  in\n",
    "\n",
    "  (* Print the minimum and the tree *)\n",
    "  print_endline \"Minimum:\";\n",
    "  print_int min; print_newline ();\n",
    "  print_endline \"Tree after extraction:\";\n",
    "  print_tree tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "id": "4007a90c",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val find_max : 'a avl_tree -> 'a = <fun>\n"
      ]
     },
     "execution_count": 61,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val remove_max : 'a avl_tree -> 'a avl_tree = <fun>\n"
      ]
     },
     "execution_count": 61,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "File \"[61]\", line 15, characters 4-29:\n",
      "15 |   | Node (k, h, l, r) as node ->\n",
      "         ^^^^^^^^^^^^^^^^^^^^^^^^^\n",
      "Warning 26 [unused-var]: unused variable node.\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "val delete : 'a -> 'a avl_tree -> 'a avl_tree = <fun>\n"
      ]
     },
     "execution_count": 61,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Tree after deletion:\n",
      "10 (height: 2)\n",
      "5 (height: 1)\n",
      "30 (height: 0)\n"
     ]
    }
   ],
   "source": [
    "(* delete *)\n",
    "\n",
    "(* Seems to be incorrect *)\n",
    "\n",
    "let rec find_max = function\n",
    "  | Empty -> failwith \"find_max: tree is empty\"\n",
    "  | Node (k, _, _, Empty) -> k\n",
    "  | Node (_, _, _, r) -> find_max r\n",
    "\n",
    "let rec remove_max = function\n",
    "  | Empty -> failwith \"remove_max: tree is empty\"\n",
    "  | Node (_, _, l, Empty) -> l\n",
    "  | Node (k, h, l, r) -> balance (Node (k, h, l, remove_max r))\n",
    "\n",
    "let rec delete x = function\n",
    "  | Empty -> Empty (* If the tree is empty, return an empty tree *)\n",
    "  | Node (k, h, l, r) as node ->\n",
    "    if x < k then \n",
    "      balance (Node (k, h, delete x l, r)) (* The element to delete is in the left subtree *)\n",
    "    else if x > k then \n",
    "      balance (Node (k, h, l, delete x r)) (* The element to delete is in the right subtree *)\n",
    "    else\n",
    "      match l, r with\n",
    "      | Empty, Empty -> Empty (* If the node is a leaf, simply remove it *)\n",
    "      | Empty, _ -> r (* If the node has only a right child, replace it with its right child *)\n",
    "      | _, Empty -> l (* If the node has only a left child, replace it with its left child *)\n",
    "      | _, _ -> (* If the node has two children *)\n",
    "        let pred = find_max l in\n",
    "        balance (Node (pred, h, remove_max l, r))\n",
    "\n",
    "let () =\n",
    "  (* Create an empty AVL tree *)\n",
    "  let tree = Empty in\n",
    "\n",
    "  (* Insert elements into the tree *)\n",
    "  let tree = List.fold_right insert [10; 20; 30; 5] tree in\n",
    "\n",
    "  (* Delete an element *)\n",
    "  let tree = delete 20 tree in\n",
    "\n",
    "  (* Function to print a tree *)\n",
    "  let rec print_tree = function\n",
    "    | Empty -> ()\n",
    "    | Node (k, h, l, r) ->\n",
    "      print_int k; print_string \" (height: \"; print_int h; print_endline \")\";\n",
    "      print_tree l;\n",
    "      print_tree r\n",
    "  in\n",
    "\n",
    "  (* Print the tree after deletion *)\n",
    "  print_endline \"Tree after deletion:\";\n",
    "  print_tree tree"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "81a23c9c",
   "metadata": {},
   "source": [
    "## RBT"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "id": "3703f14b",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "type color = Red | Black\n"
      ]
     },
     "execution_count": 62,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "type 'a rb_tree = Empty | Node of 'a * color * 'a rb_tree * 'a rb_tree\n"
      ]
     },
     "execution_count": 62,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "type color = Red | Black\n",
    "\n",
    "type 'a rb_tree =\n",
    "  | Empty\n",
    "  | Node of 'a * color * 'a rb_tree * 'a rb_tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "id": "4ca63156",
   "metadata": {},
   "outputs": [],
   "source": [
    "(* balance left *)\n",
    "\n",
    "(* Incorrect Code *)\n",
    "\n",
    "(* let balance_left = function\n",
    "  | Node (k1, Black, Node (lk1, Red, Node (llk1, Red, lll1, llr1), lr1), r1)\n",
    "  | Node (k2, Black, Node (lk2, Red, ll2, Node (lrk2, Red, lrl2, lrr2)), r2) ->\n",
    "    Node (lk1, Red, Node (llk1, Black, lll1, llr1), Node (k1, Black, lr1, r1))\n",
    "  | t -> t\n",
    "  \n",
    "let () =\n",
    "  (* Create a red-black tree that violates the properties *)\n",
    "  let tree = Node (3, Black, Node (2, Red, Node (1, Red, Empty, Empty), Empty), Empty) in\n",
    "\n",
    "  (* Print the tree before balancing *)\n",
    "  print_endline \"Tree before balancing:\";\n",
    "  print_tree tree;\n",
    "\n",
    "  (* Balance the tree *)\n",
    "  let balanced_tree = balance_left tree in\n",
    "\n",
    "  (* Print the tree after balancing *)\n",
    "  print_endline \"Tree after balancing:\";\n",
    "  print_tree balanced_tree *)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "id": "342ce08c",
   "metadata": {},
   "outputs": [],
   "source": [
    "(* balance right *)\n",
    "\n",
    "(* Incorrect Code *)\n",
    "\n",
    "(* let balance_right = function\n",
    "  | Node (k, Black, l, Node (rk, Red, Node (rlk, Red, rll, rlr), rr))\n",
    "  | Node (k, Black, l, Node (rk, Red, rl, Node (rrk, Red, rrl, rrr))) ->\n",
    "    Node (rk, Red, Node (k, Black, l, rl), Node (rrk, Black, rlr, rr))\n",
    "  | t -> t\n",
    "\n",
    "let () =\n",
    "  (* Create a red-black tree that violates the properties *)\n",
    "  let tree = Node (1, Black, Empty, Node (2, Red, Empty, Node (3, Red, Empty, Empty))) in\n",
    "\n",
    "  (* Print the tree before balancing *)\n",
    "  print_endline \"Tree before balancing:\";\n",
    "  print_tree tree;\n",
    "\n",
    "  (* Balance the tree *)\n",
    "  let balanced_tree = balance_right tree in\n",
    "\n",
    "  (* Print the tree after balancing *)\n",
    "  print_endline \"Tree after balancing:\";\n",
    "  print_tree balanced_tree *)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "id": "0df8d1a1",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val balance : 'a rb_tree -> 'a rb_tree = <fun>\n"
      ]
     },
     "execution_count": 65,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val insert : 'a -> 'a rb_tree -> 'a rb_tree = <fun>\n"
      ]
     },
     "execution_count": 65,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val insert_tree : 'a -> 'a rb_tree -> 'a rb_tree = <fun>\n"
      ]
     },
     "execution_count": 65,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val print_tree : int rb_tree -> unit = <fun>\n"
      ]
     },
     "execution_count": 65,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Tree after insertions:\n",
      "(20, Black, (5, Black, Empty\n",
      ", (10, Red, Empty\n",
      ", Empty\n",
      ")\n",
      ")\n",
      ", (30, Black, Empty\n",
      ", Empty\n",
      ")\n",
      ")\n"
     ]
    }
   ],
   "source": [
    "(* insert *)\n",
    "\n",
    "(* A function to rebalance the tree after an insert *)\n",
    "let balance = function\n",
    "  | Node (z, Black, Node (y, Red, Node (x, Red, a, b), c), d)\n",
    "  | Node (z, Black, Node (x, Red, a, Node (y, Red, b, c)), d)\n",
    "  | Node (x, Black, a, Node (z, Red, Node (y, Red, b, c), d))\n",
    "  | Node (x, Black, a, Node (y, Red, b, Node (z, Red, c, d))) ->\n",
    "    Node (y, Red, Node (x, Black, a, b), Node (z, Black, c, d))\n",
    "  | t -> t\n",
    "\n",
    "(* A function to insert a value into a red-black tree *)\n",
    "let rec insert x = function\n",
    "  | Empty -> Node (x, Red, Empty, Empty)\n",
    "  | Node (y, color, a, b) as node ->\n",
    "    if x < y then\n",
    "      balance (Node (y, color, insert x a, b))\n",
    "    else if x > y then\n",
    "      balance (Node (y, color, a, insert x b))\n",
    "    else\n",
    "      node\n",
    "\n",
    "(* A function to paint the root of a tree black *)\n",
    "let insert_tree x tree =\n",
    "  match insert x tree with\n",
    "  | Node (y, _, a, b) -> Node (y, Black, a, b)\n",
    "  | Empty -> Empty\n",
    "\n",
    "(* A helper function to print a tree *)\n",
    "let rec print_tree = function\n",
    "  | Empty -> print_endline \"Empty\"\n",
    "  | Node (k, color, l, r) ->\n",
    "    print_string \"(\";\n",
    "    print_int k;\n",
    "    print_string \", \";\n",
    "    (match color with Red -> print_string \"Red\" | Black -> print_string \"Black\");\n",
    "    print_string \", \";\n",
    "    print_tree l;\n",
    "    print_string \", \";\n",
    "    print_tree r;\n",
    "    print_endline \")\"\n",
    "\n",
    "let () =\n",
    "  (* Create an empty red-black tree *)\n",
    "  let tree = Empty in\n",
    "\n",
    "  (* Insert elements into the tree *)\n",
    "  let tree = List.fold_right insert_tree [10; 20; 30; 5] tree in\n",
    "\n",
    "  (* Print the tree after the insertions *)\n",
    "  print_endline \"Tree after insertions:\";\n",
    "  print_tree tree"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bc7be2d5",
   "metadata": {},
   "source": [
    "## User"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "id": "4bee00b6",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "type expr =\n",
       "    Var of string\n",
       "  | Const of int\n",
       "  | Add of expr * expr\n",
       "  | Let of string * expr * expr\n",
       "  | IfZero of expr * expr * expr\n"
      ]
     },
     "execution_count": 66,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val desugar : expr -> expr = <fun>\n"
      ]
     },
     "execution_count": 66,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val string_of_expr : expr -> string = <fun>\n"
      ]
     },
     "execution_count": 66,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Before desugar: if (0 == 0) then 1 else 2\n",
      "After desugar: let $$temp = 0 in if ($$temp == 0) then 1 else 2\n",
      "\n",
      "Before desugar: let x = 1 in if (x == 0) then 2 else 3\n",
      "After desugar: let x = 1 in let $$temp = x in if ($$temp == 0) then 2 else 3\n",
      "\n",
      "Before desugar: (if (0 == 0) then 1 else 2 + 3)\n",
      "After desugar: (let $$temp = 0 in if ($$temp == 0) then 1 else 2 + 3)\n",
      "\n"
     ]
    }
   ],
   "source": [
    "(* Desugar AST *)\n",
    "\n",
    "type expr =\n",
    "  | Var of string\n",
    "  | Const of int\n",
    "  | Add of expr * expr\n",
    "  | Let of string * expr * expr\n",
    "  | IfZero of expr * expr * expr\n",
    "\n",
    "let rec desugar = function\n",
    "  | Var _ as v -> v\n",
    "  | Const _ as c -> c\n",
    "  | Add(e1, e2) -> Add(desugar e1, desugar e2)\n",
    "  | Let(v, e1, e2) -> Let(v, desugar e1, desugar e2)\n",
    "  | IfZero(e1, e2, e3) -> Let(\"$$temp\", desugar e1, IfZero(Var(\"$$temp\"), desugar e2, desugar e3))\n",
    "\n",
    "let rec string_of_expr = function\n",
    "  | Var v -> v\n",
    "  | Const c -> string_of_int c\n",
    "  | Add(e1, e2) -> \"(\" ^ string_of_expr e1 ^ \" + \" ^ string_of_expr e2 ^ \")\"\n",
    "  | Let(v, e1, e2) -> \"let \" ^ v ^ \" = \" ^ string_of_expr e1 ^ \" in \" ^ string_of_expr e2\n",
    "  | IfZero(e1, e2, e3) -> \"if (\" ^ string_of_expr e1 ^ \" == 0) then \" ^ string_of_expr e2 ^ \" else \" ^ string_of_expr e3\n",
    "\n",
    "let () =\n",
    "  let test expr =\n",
    "    let result = desugar expr in\n",
    "    print_endline (\"Before desugar: \" ^ string_of_expr expr);\n",
    "    print_endline (\"After desugar: \" ^ string_of_expr result);\n",
    "    print_endline \"\" in\n",
    "\n",
    "  test (IfZero(Const 0, Const 1, Const 2));\n",
    "  test (Let(\"x\", Const 1, IfZero(Var \"x\", Const 2, Const 3)));\n",
    "  test (Add(IfZero(Const 0, Const 1, Const 2), Const 3))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "id": "1286dcec",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "type address_book = (string * string) list\n"
      ]
     },
     "execution_count": 67,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val make_address_book : 'a -> 'a = <fun>\n"
      ]
     },
     "execution_count": 67,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val add_entry : 'a -> 'b -> ('a * 'b) list -> ('a * 'b) list = <fun>\n"
      ]
     },
     "execution_count": 67,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val find_phone : 'a -> ('a * 'b) list -> 'b option = <fun>\n"
      ]
     },
     "execution_count": 67,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Alice's phone number is 123-4567\n"
     ]
    }
   ],
   "source": [
    "(* make address book *)\n",
    "\n",
    "type address_book = (string * string) list\n",
    "\n",
    "let make_address_book entries = entries\n",
    "\n",
    "let add_entry name phone book = (name, phone) :: book\n",
    "\n",
    "let find_phone name book = \n",
    "  try \n",
    "    Some (List.assoc name book) \n",
    "  with Not_found -> None\n",
    "\n",
    "let () =\n",
    "  (* Create an address book *)\n",
    "  let book = make_address_book [(\"Alice\", \"123-4567\"); (\"Bob\", \"234-5678\")] in\n",
    "\n",
    "  (* Add an entry to the book *)\n",
    "  let book = add_entry \"Charlie\" \"345-6789\" book in\n",
    "\n",
    "  (* Look up a phone number *)\n",
    "  let phone = find_phone \"Alice\" book in\n",
    "\n",
    "  (* Print the result *)\n",
    "  match phone with\n",
    "  | Some number -> print_endline (\"Alice's phone number is \" ^ number)\n",
    "  | None -> print_endline \"Alice not found in address book\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 68,
   "id": "d59a5d0c",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "type address_book = (string * string) list\n"
      ]
     },
     "execution_count": 68,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val merge_address_books : ('a * 'b) list -> ('a * 'b) list -> ('a * 'b) list =\n",
       "  <fun>\n"
      ]
     },
     "execution_count": 68,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val print_address_book : (string * string) list -> unit = <fun>\n"
      ]
     },
     "execution_count": 68,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Name: Charlie, Phone: 345-6789\n",
      "Name: Alice, Phone: 123-4567\n",
      "Name: Bob, Phone: 987-6543\n",
      "Name: David, Phone: 876-5432\n"
     ]
    }
   ],
   "source": [
    "(* merge address books *)\n",
    "\n",
    "type address_book = (string * string) list\n",
    "\n",
    "let merge_address_books book1 book2 =\n",
    "  let merge_entry acc (name, phone) =\n",
    "    if List.mem_assoc name acc then\n",
    "      acc\n",
    "    else\n",
    "      (name, phone) :: acc\n",
    "  in\n",
    "  List.fold_left merge_entry book2 book1\n",
    "\n",
    "let print_address_book book =\n",
    "  List.iter (fun (name, phone) -> Printf.printf \"Name: %s, Phone: %s\\n\" name phone) book\n",
    "  \n",
    "let () =\n",
    "  (* Create two address books *)\n",
    "  let book1 = [(\"Alice\", \"123-4567\"); (\"Bob\", \"234-5678\"); (\"Charlie\", \"345-6789\")] in\n",
    "  let book2 = [(\"Bob\", \"987-6543\"); (\"David\", \"876-5432\")] in\n",
    "\n",
    "  (* Merge the address books *)\n",
    "  let merged_book = merge_address_books book1 book2 in\n",
    "\n",
    "  (* Print the merged address book *)\n",
    "  print_address_book merged_book;\n",
    "  flush stdout"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b0bfc0a6",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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
}