Benchmarks for BURST & SYMTH.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "c4ec6ba3",
   "metadata": {},
   "source": [
    "## Boolean"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "aea2c8b3",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val bool_always_false : 'a -> bool = <fun>\n"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "false\n",
      "false\n"
     ]
    }
   ],
   "source": [
    "(* bool_always_false *)\n",
    "\n",
    "let bool_always_false _ = false\n",
    "\n",
    "let () =\n",
    "  print_endline (string_of_bool (bool_always_false true)); (* This will print 'false' *)\n",
    "  print_endline (string_of_bool (bool_always_false false)); (* This will print 'false' *)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "40df9a65",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val bool_always_true : 'a -> bool = <fun>\n"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "true\n",
      "true\n"
     ]
    }
   ],
   "source": [
    "(* bool_always_true *)\n",
    "\n",
    "let bool_always_true _ = true\n",
    "\n",
    "let () =\n",
    "  print_endline (string_of_bool (bool_always_true true)); (* This will print 'true' *)\n",
    "  print_endline (string_of_bool (bool_always_true false)); (* This will print 'true' *)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "01d840fc",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val bool_band : bool -> bool -> bool = <fun>\n"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "true\n",
      "false\n",
      "false\n",
      "false\n"
     ]
    }
   ],
   "source": [
    "(* bool_band *)\n",
    "\n",
    "let bool_band a b = a && b\n",
    "\n",
    "let () =\n",
    "  print_endline (string_of_bool (bool_band true true));   (* This will print 'true' *)\n",
    "  print_endline (string_of_bool (bool_band true false));  (* This will print 'false' *)\n",
    "  print_endline (string_of_bool (bool_band false true));  (* This will print 'false' *)\n",
    "  print_endline (string_of_bool (bool_band false false)); (* This will print 'false' *)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "60fb6426",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val bool_bor : bool -> bool -> bool = <fun>\n"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "true\n",
      "true\n",
      "true\n",
      "false\n"
     ]
    }
   ],
   "source": [
    "(* bool_bor *)\n",
    "\n",
    "let bool_bor a b = a || b\n",
    "\n",
    "let () =\n",
    "  print_endline (string_of_bool (bool_bor true true));   (* This will print 'true' *)\n",
    "  print_endline (string_of_bool (bool_bor true false));  (* This will print 'true' *)\n",
    "  print_endline (string_of_bool (bool_bor false true));  (* This will print 'true' *)\n",
    "  print_endline (string_of_bool (bool_bor false false)); (* This will print 'false' *)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "88cf68e8",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val bool_impl : bool -> bool -> bool = <fun>\n"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "true\n",
      "false\n",
      "true\n",
      "true\n"
     ]
    }
   ],
   "source": [
    "(* bool_impl *)\n",
    "\n",
    "let bool_impl a b = (not a) || b\n",
    "\n",
    "let () =\n",
    "  print_endline (string_of_bool (bool_impl true true));   (* This will print 'true' *)\n",
    "  print_endline (string_of_bool (bool_impl true false));  (* This will print 'false' *)\n",
    "  print_endline (string_of_bool (bool_impl false true));  (* This will print 'true' *)\n",
    "  print_endline (string_of_bool (bool_impl false false)); (* This will print 'true' *)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "216384cc",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val bool_neg : bool -> bool = <fun>\n"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "false\n",
      "true\n"
     ]
    }
   ],
   "source": [
    "(* bool_neg *)\n",
    "\n",
    "let bool_neg a = not a\n",
    "\n",
    "let () =\n",
    "  print_endline (string_of_bool (bool_neg true));  (* This will print 'false' *)\n",
    "  print_endline (string_of_bool (bool_neg false)); (* This will print 'true' *)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "6e4a9a19",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val bool_xor : bool -> bool -> bool = <fun>\n"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "false\n",
      "true\n",
      "true\n",
      "false\n"
     ]
    }
   ],
   "source": [
    "(* bool_xor *)\n",
    "\n",
    "let bool_xor a b = (a || b) && not (a && b)\n",
    "\n",
    "let () =\n",
    "  print_endline (string_of_bool (bool_xor true true));   (* This will print 'false' *)\n",
    "  print_endline (string_of_bool (bool_xor true false));  (* This will print 'true' *)\n",
    "  print_endline (string_of_bool (bool_xor false true));  (* This will print 'true' *)\n",
    "  print_endline (string_of_bool (bool_xor false false)); (* This will print 'false' *)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "34d15124",
   "metadata": {},
   "source": [
    "## Lists"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "bfd45d72",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val list_append : 'a list -> 'a list -> 'a list = <fun>\n"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 2 3 4 5 6 \n"
     ]
    }
   ],
   "source": [
    "(* list_append *)\n",
    "\n",
    "let list_append lst1 lst2 = lst1 @ lst2\n",
    "\n",
    "let () =\n",
    "  let list1 = [1; 2; 3] in\n",
    "  let list2 = [4; 5; 6] in\n",
    "  let result = list_append list1 list2 in\n",
    "  List.iter (fun x -> print_int x; print_string \" \") result;\n",
    "  print_endline \"\"; (* Move the cursor to the next line *)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "2a113a0a",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val list_compress : 'a list -> 'a list = <fun>\n"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 2 3 4 1 5 6 \n"
     ]
    }
   ],
   "source": [
    "(* list_compress *)\n",
    "\n",
    "let rec list_compress = function\n",
    "  | a :: (b :: _ as t) -> if a = b then list_compress t else a :: list_compress t\n",
    "  | smaller -> smaller\n",
    "\n",
    "let () =\n",
    "  let list = [1; 1; 2; 2; 2; 3; 3; 4; 1; 1; 5; 6; 6] in\n",
    "  let result = list_compress list in\n",
    "  List.iter (fun x -> print_int x; print_string \" \") result;\n",
    "  print_endline \"\"; (* Move the cursor to the next line *)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "e1341973",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val list_concat : 'a list list -> 'a list = <fun>\n"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 2 3 4 5 6 7 8 9 \n"
     ]
    }
   ],
   "source": [
    "(* list_concat *)\n",
    "\n",
    "let list_concat lst = List.concat lst\n",
    "\n",
    "let () =\n",
    "  let lists = [[1; 2; 3]; [4; 5; 6]; [7; 8; 9]] in\n",
    "  let result = list_concat lists in\n",
    "  List.iter (fun x -> print_int x; print_string \" \") result;\n",
    "  print_endline \"\"; (* Move the cursor to the next line *)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "85eed674",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val list_drop : int -> 'a list -> 'a list = <fun>\n"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4 5 6 7 8 9 \n"
     ]
    }
   ],
   "source": [
    "(* list_drop *)\n",
    "\n",
    "let rec list_drop n lst =\n",
    "  if n <= 0 then lst\n",
    "  else match lst with\n",
    "    | [] -> []\n",
    "    | _::t -> list_drop (n - 1) t\n",
    "\n",
    "let () =\n",
    "  let list = [1; 2; 3; 4; 5; 6; 7; 8; 9] in\n",
    "  let result = list_drop 3 list in\n",
    "  List.iter (fun x -> print_int x; print_string \" \") result;\n",
    "  print_endline \"\"; (* Move the cursor to the next line *)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "971d626a",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val list_even_parity : bool list -> bool = <fun>\n"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "true\n",
      "true\n",
      "false\n",
      "true\n",
      "false\n",
      "false\n",
      "true\n"
     ]
    }
   ],
   "source": [
    "(* list_even_parity *)\n",
    "\n",
    "let list_even_parity lst = List.fold_left (fun acc x -> if x then not acc else acc) true lst\n",
    "\n",
    "let () =\n",
    "  print_endline (string_of_bool (list_even_parity [])); (* This will print 'true' *)\n",
    "  print_endline (string_of_bool (list_even_parity [false])); (* This will print 'true' *)\n",
    "  print_endline (string_of_bool (list_even_parity [true])); (* This will print 'false' *)\n",
    "  print_endline (string_of_bool (list_even_parity [false; false])); (* This will print 'true' *)\n",
    "  print_endline (string_of_bool (list_even_parity [false; true])); (* This will print 'false' *)\n",
    "  print_endline (string_of_bool (list_even_parity [true; false])); (* This will print 'false' *)\n",
    "  print_endline (string_of_bool (list_even_parity [true; true])); (* This will print 'true' *)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "e9a991e4",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val is_even : int -> bool = <fun>\n"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val is_nonzero : int -> bool = <fun>\n"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val list_filter : ('a -> bool) -> 'a list -> 'a list = <fun>\n"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "2 \n",
      "0 0 \n",
      "0 \n",
      "\n"
     ]
    }
   ],
   "source": [
    "(* list_filter *)\n",
    "\n",
    "let is_even n = n mod 2 = 0\n",
    "let is_nonzero n = n <> 0\n",
    "\n",
    "let rec list_filter f = function\n",
    "  | [] -> []\n",
    "  | h :: t -> if f h then h :: list_filter f t else list_filter f t\n",
    "\n",
    "let () =\n",
    "let print_list lst =\n",
    "  let rec print_elements = function\n",
    "    | [] -> print_string \"\\n\"\n",
    "    | h :: t -> print_int h; print_string \" \"; print_elements t\n",
    "  in print_elements lst\n",
    "in\n",
    "print_list (list_filter is_even []); (* This will print nothing *)\n",
    "print_list (list_filter is_even [2]); (* This will print '2 ' *)\n",
    "print_list (list_filter is_even [0; 0]); (* This will print '0 0 ' *)\n",
    "print_list (list_filter is_even [1; 0; 1]); (* This will print '0 ' *)\n",
    "print_list (list_filter is_nonzero [0]); (* This will print nothing *)\n",
    "flush stdout"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "f19aa305",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val sum : int -> int -> int = <fun>\n"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val list_fold : ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a = <fun>\n"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0\n",
      "3\n",
      "6\n"
     ]
    }
   ],
   "source": [
    "(* list_fold *)\n",
    "let sum a b = a + b\n",
    "\n",
    "let list_fold f init lst = List.fold_left f init lst\n",
    "\n",
    "let () =\n",
    "  print_endline (string_of_int (list_fold sum 0 [])); (* This will print '0' *)\n",
    "  print_endline (string_of_int (list_fold sum 0 [2; 1])); (* This will print '3' *)\n",
    "  print_endline (string_of_int (list_fold sum 0 [3; 2; 1])); (* This will print '6' *)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "7b8be677",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val list_hd : 'a list -> 'a option = <fun>\n"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "None\n",
      "1\n",
      "10\n"
     ]
    }
   ],
   "source": [
    "(* list_hd *)\n",
    "\n",
    "let list_hd = function\n",
    "  | [] -> None\n",
    "  | h :: _ -> Some h\n",
    "\n",
    "let () =\n",
    "  let print_option = function\n",
    "    | None -> print_endline \"None\"\n",
    "    | Some x -> print_endline (string_of_int x)\n",
    "  in\n",
    "  print_option (list_hd []); (* This will print 'None' *)\n",
    "  print_option (list_hd [1; 2; 3; 4; 5]); (* This will print '1' *)\n",
    "  print_option (list_hd [10; 20; 30; 40; 50]); (* This will print '10' *)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "bb1c32a7",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val list_inc : int list -> int list = <fun>\n"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "2 3 \n",
      "1 1 \n",
      "4 5 6 \n"
     ]
    }
   ],
   "source": [
    "(* list_inc *)\n",
    "\n",
    "let rec list_inc = function\n",
    "  | [] -> []\n",
    "  | h :: t -> (h + 1) :: list_inc t\n",
    "\n",
    "let () =\n",
    "  let print_list lst =\n",
    "    let rec print_elements = function\n",
    "      | [] -> print_string \"\\n\"\n",
    "      | h :: t -> print_int h; print_string \" \"; print_elements t\n",
    "    in print_elements lst\n",
    "  in\n",
    "  print_list (list_inc []); (* This will print nothing *)\n",
    "  print_list (list_inc [1; 2]); (* This will print '2 3 ' *)\n",
    "  print_list (list_inc [0; 0]); (* This will print '1 1 ' *)\n",
    "  print_list (list_inc [3; 4; 5]); (* This will print '4 5 6 ' *)\n",
    "  flush stdout"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "5fc6af9c",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val list_last : 'a list -> 'a option = <fun>\n"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "None\n",
      "5\n",
      "50\n"
     ]
    }
   ],
   "source": [
    "(* list_last *)\n",
    "\n",
    "let rec list_last = function\n",
    "  | [] -> None\n",
    "  | [x] -> Some x\n",
    "  | _ :: t -> list_last t\n",
    "\n",
    "let () =\n",
    "  let print_option = function\n",
    "    | None -> print_endline \"None\"\n",
    "    | Some x -> print_endline (string_of_int x)\n",
    "  in\n",
    "  print_option (list_last []); (* This will print 'None' *)\n",
    "  print_option (list_last [1; 2; 3; 4; 5]); (* This will print '5' *)\n",
    "  print_option (list_last [10; 20; 30; 40; 50]); (* This will print '50' *)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "fbcf3517",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val list_length : 'a list -> int = <fun>\n"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0\n",
      "5\n",
      "5\n"
     ]
    }
   ],
   "source": [
    "(* list_length *)\n",
    "\n",
    "let rec list_length = function\n",
    "  | [] -> 0\n",
    "  | _ :: t -> 1 + list_length t\n",
    "\n",
    "let () =\n",
    "  print_endline (string_of_int (list_length [])); (* This will print '0' *)\n",
    "  print_endline (string_of_int (list_length [1; 2; 3; 4; 5])); (* This will print '5' *)\n",
    "  print_endline (string_of_int (list_length [10; 20; 30; 40; 50])) (* This will print '5' *)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "511483c0",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val inc : int -> int = <fun>\n"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val zero : 'a -> int = <fun>\n"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val list_map : ('a -> 'b) -> 'a list -> 'b list = <fun>\n"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "1 \n",
      "1 1 \n",
      "0 0 \n"
     ]
    }
   ],
   "source": [
    "(* list_map *)\n",
    "\n",
    "let inc x = x + 1\n",
    "let zero _ = 0\n",
    "\n",
    "let rec list_map f = function\n",
    "  | [] -> []\n",
    "  | h :: t -> (f h) :: list_map f t\n",
    "\n",
    "let () =\n",
    "  let print_list lst =\n",
    "    let rec print_elements = function\n",
    "      | [] -> print_string \"\\n\"\n",
    "      | h :: t -> print_int h; print_string \" \"; print_elements t\n",
    "    in print_elements lst\n",
    "  in\n",
    "  print_list (list_map inc []); (* This will print nothing *)\n",
    "  print_list (list_map inc [0]); (* This will print '1 ' *)\n",
    "  print_list (list_map inc [0; 0]); (* This will print '1 1 ' *)\n",
    "  print_list (list_map zero [1; 2]); (* This will print '0 0 ' *)\n",
    "  flush stdout"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "id": "f10f60c8",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val list_nth : 'a list -> int -> 'a option = <fun>\n"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "3\n",
      "0\n"
     ]
    }
   ],
   "source": [
    "(* list_map *)\n",
    "\n",
    "let rec list_nth lst n = \n",
    "  match lst with\n",
    "  | [] -> None\n",
    "  | h :: t -> if n = 0 then Some h else list_nth t (n - 1)\n",
    "\n",
    "let () =\n",
    "  let print_option = function\n",
    "    | None -> print_endline \"0\"\n",
    "    | Some x -> print_endline (string_of_int x)\n",
    "  in\n",
    "  print_option (list_nth [1; 2; 3; 4; 5] 0); (* This will print '1' *)\n",
    "  print_option (list_nth [1; 2; 3; 4; 5] 2); (* This will print '3' *)\n",
    "  print_option (list_nth [1; 2; 3; 4; 5] 5); (* This will print 'None' *)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "id": "d132f1b4",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val is_even : int -> bool = <fun>\n"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val length : 'a list -> int = <fun>\n"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val list_pairwise_swap : 'a list -> 'a list = <fun>\n"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "\n",
      "0 1 \n",
      "\n",
      "1 0 1 0 \n"
     ]
    }
   ],
   "source": [
    "(* list_pairwise_swap *)\n",
    "\n",
    "let is_even n = n mod 2 = 0\n",
    "\n",
    "let rec length = function\n",
    "  | [] -> 0\n",
    "  | _ :: t -> 1 + length t\n",
    "\n",
    "let rec list_pairwise_swap lst =\n",
    "  if is_even (length lst) then\n",
    "    match lst with\n",
    "    | [] -> []\n",
    "    | [_] -> []\n",
    "    | a :: b :: t -> b :: a :: list_pairwise_swap t\n",
    "  else\n",
    "    []\n",
    "\n",
    "let () =\n",
    "  let print_list lst =\n",
    "    let rec print_elements = function\n",
    "      | [] -> print_string \"\\n\"\n",
    "      | h :: t -> print_int h; print_string \" \"; print_elements t\n",
    "    in print_elements lst\n",
    "  in\n",
    "  print_list (list_pairwise_swap []); (* This will print nothing *)\n",
    "  print_list (list_pairwise_swap [1]); (* This will print nothing *)\n",
    "  print_list (list_pairwise_swap [1; 0]); (* This will print '0 1 ' *)\n",
    "  print_list (list_pairwise_swap [1; 0; 1]); (* This will print nothing *)\n",
    "  print_list (list_pairwise_swap [0; 1; 0; 1]); (* This will print '1 0 1 0 ' *)\n",
    "  flush stdout"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "id": "aacf5c31",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "type 'a mylist = Nil | Cons of 'a * 'a mylist\n"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val list_snoc : 'a mylist -> 'a -> 'a mylist = <fun>\n"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val print_list : int mylist -> unit = <fun>\n"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "- : unit = ()\n"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "- : unit = ()\n"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(* list_snoc *)\n",
    "\n",
    "type 'a mylist =\n",
    "  | Nil\n",
    "  | Cons of 'a * 'a mylist\n",
    "\n",
    "(* Function to append an element at the end of a list *)\n",
    "let rec list_snoc list x =\n",
    "  match list with\n",
    "  | Nil -> Cons (x, Nil)\n",
    "  | Cons (y, ys) -> Cons (y, list_snoc ys x)\n",
    "\n",
    "(* Test the function *)\n",
    "let rec print_list = function\n",
    "  | Nil -> print_string \"Nil\"\n",
    "  | Cons (x, xs) ->\n",
    "    print_string \"Cons (\"; print_int x; print_string \", \";\n",
    "    print_list xs; print_string \")\"\n",
    "\n",
    "let () =\n",
    "  let list1 = Nil in\n",
    "  let x1 = 0 in\n",
    "  let result1 = list_snoc list1 x1 in\n",
    "  print_string \"Expected: \"; print_list result1; \n",
    "  flush stdout;;\n",
    "\n",
    "  let list2 = Nil in\n",
    "  let x2 = 1 in\n",
    "  let result2 = list_snoc list2 x2 in\n",
    "  print_string \"Expected: \"; print_list result2; \n",
    "  flush stdout;;\n",
    "\n",
    "  let list3 = Cons (2, Cons (1, Cons (0, Nil))) in\n",
    "  let x3 = 1 in\n",
    "  let result3 = list_snoc list3 x3 in\n",
    "  print_string \"Expected: \"; print_list result3;\n",
    "  flush stdout;;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "id": "d3fd0a46",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "type 'a mylist = Nil | Cons of 'a * 'a mylist\n"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val list_rev_append : 'a mylist -> 'a mylist -> 'a mylist = <fun>\n"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val print_list : int mylist -> unit = <fun>\n"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Expected: Cons (0, Nil)Expected: Cons (1, Nil)Expected: Cons (2, Cons (1, Cons (0, Cons (1, Nil))))Expected: Nil\n",
      "Expected: Cons (0, Nil\n",
      ")Expected: Cons (1, Cons (0, Cons (0, Nil\n",
      ")))Expected: Cons (9, Cons (8, Cons (7, Cons (1, Cons (2, Cons (3, Nil\n"
     ]
    }
   ],
   "source": [
    "(* list_rev_append *)\n",
    "\n",
    "type 'a mylist =\n",
    "  | Nil\n",
    "  | Cons of 'a * 'a mylist\n",
    "\n",
    "(* Function to reverse a list and append it to another list *)\n",
    "let rec list_rev_append list1 list2 =\n",
    "  match list1 with\n",
    "  | Nil -> list2\n",
    "  | Cons (x, xs) -> list_rev_append xs (Cons (x, list2))\n",
    "\n",
    "(* Test the function *)\n",
    "let rec print_list = function\n",
    "  | Nil -> print_endline \"Nil\"\n",
    "  | Cons (x, xs) ->\n",
    "    print_string \"Cons (\"; print_int x; print_string \", \";\n",
    "    print_list xs; print_string \")\"\n",
    "\n",
    "let () =\n",
    "  let list1 = Nil in\n",
    "  let list2 = Nil in\n",
    "  let result1 = list_rev_append list1 list2 in\n",
    "  print_string \"Expected: \"; print_list result1;\n",
    "\n",
    "  let list3 = Cons (0, Nil) in\n",
    "  let list4 = Nil in\n",
    "  let result2 = list_rev_append list3 list4 in\n",
    "  print_string \"Expected: \"; print_list result2;\n",
    "\n",
    "  let list5 = Cons (0, Cons (0, Cons (1, Nil))) in\n",
    "  let list6 = Nil in\n",
    "  let result3 = list_rev_append list5 list6 in\n",
    "  print_string \"Expected: \"; print_list result3;\n",
    "  \n",
    "  let list7 = Cons (7, Cons (8, Cons (9, Nil))) in\n",
    "  let list8 = Cons (1, Cons (2, Cons (3, Nil))) in\n",
    "  let result4 = list_rev_append list7 list8 in\n",
    "  print_string \"Expected: \"; print_list result4\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "id": "5242e95f",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "type 'a mylist = Nil | Cons of 'a * 'a mylist\n"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val mylist_fold_left : ('a -> 'b -> 'a) -> 'a -> 'b mylist -> 'a = <fun>\n"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val list_rev_fold : 'a mylist -> 'a mylist = <fun>\n"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val print_list : int mylist -> unit = <fun>\n"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "))))))Expected: Cons (3, Cons (2, Cons (1, Nil\n",
      ")))Expected: Cons (0, Nil\n",
      ")Expected: Cons (1, Cons (0, Cons (0, Nil\n"
     ]
    }
   ],
   "source": [
    "(* list_rev_fold *)\n",
    "\n",
    "type 'a mylist =\n",
    "  | Nil\n",
    "  | Cons of 'a * 'a mylist\n",
    "\n",
    "(* Custom fold_left function for our list type *)\n",
    "let rec mylist_fold_left f acc list =\n",
    "  match list with\n",
    "  | Nil -> acc\n",
    "  | Cons (x, xs) -> mylist_fold_left f (f acc x) xs\n",
    "\n",
    "(* Function to reverse a list using our custom fold_left function *)\n",
    "let list_rev_fold list =\n",
    "  let folder acc x = Cons(x, acc) in\n",
    "  mylist_fold_left folder Nil list\n",
    "\n",
    "(* Test the function *)\n",
    "let rec print_list = function\n",
    "  | Nil -> print_endline \"Nil\"\n",
    "  | Cons (x, xs) ->\n",
    "    print_string \"Cons (\"; print_int x; print_string \", \";\n",
    "    print_list xs; print_string \")\"\n",
    "\n",
    "let () =\n",
    "  let list1 = Cons (1, Cons (2, Cons (3, Nil))) in\n",
    "  let result1 = list_rev_fold list1 in\n",
    "  print_string \"Expected: \"; print_list result1;\n",
    "\n",
    "  let list2 = Cons (0, Nil) in\n",
    "  let result2 = list_rev_fold list2 in\n",
    "  print_string \"Expected: \"; print_list result2;\n",
    "\n",
    "  let list3 = Cons (0, Cons (0, Cons (1, Nil))) in\n",
    "  let result3 = list_rev_fold list3 in\n",
    "  print_string \"Expected: \"; print_list result3\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "id": "7a57007a",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "type 'a mylist = Nil | Cons of 'a * 'a mylist\n"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val list_rev : 'a mylist -> 'a mylist = <fun>\n"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val list_rev_snoc : 'a mylist -> 'a -> 'a mylist = <fun>\n"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val print_list : int mylist -> unit = <fun>\n"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      ")))Expected: Cons (0, Nil\n",
      ")Expected: Cons (1, Nil\n",
      ")Expected: Cons (1, Cons (1, Cons (0, Cons (0, Nil\n"
     ]
    }
   ],
   "source": [
    "(* list_rev_snoc *)\n",
    "\n",
    "type 'a mylist =\n",
    "  | Nil\n",
    "  | Cons of 'a * 'a mylist\n",
    "\n",
    "(* Function to reverse a list *)\n",
    "let list_rev list =\n",
    "  let rec aux acc = function\n",
    "    | Nil -> acc\n",
    "    | Cons (x, xs) -> aux (Cons (x, acc)) xs\n",
    "  in\n",
    "  aux Nil list\n",
    "\n",
    "(* Function to reverse a list and append an element at the end *)\n",
    "let list_rev_snoc list x =\n",
    "  let reversed_list = list_rev list in\n",
    "  Cons (x, reversed_list)\n",
    "\n",
    "(* Test the function *)\n",
    "let rec print_list = function\n",
    "  | Nil -> print_endline \"Nil\"\n",
    "  | Cons (x, xs) ->\n",
    "    print_string \"Cons (\"; print_int x; print_string \", \";\n",
    "    print_list xs; print_string \")\"\n",
    "\n",
    "let () =\n",
    "  let list1 = Nil in\n",
    "  let x1 = 0 in\n",
    "  let result1 = list_rev_snoc list1 x1 in\n",
    "  print_string \"Expected: \"; print_list result1;\n",
    "\n",
    "  let list2 = Nil in\n",
    "  let x2 = 1 in\n",
    "  let result2 = list_rev_snoc list2 x2 in\n",
    "  print_string \"Expected: \"; print_list result2;\n",
    "\n",
    "  let list3 = Cons (0, Cons (0, Cons (1, Nil))) in\n",
    "  let x3 = 1 in\n",
    "  let result3 = list_rev_snoc list3 x3 in\n",
    "  print_string \"Expected: \"; print_list result3\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "id": "9427cca5",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "type 'a mylist = Nil | Cons of 'a * 'a mylist\n"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val list_rev_tailcall : 'a mylist -> 'a mylist = <fun>\n"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val print_list : int mylist -> unit = <fun>\n"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "))))Expected: Cons (3, Cons (2, Cons (1, Nil\n",
      ")))Expected: Cons (0, Nil\n",
      ")Expected: Cons (1, Cons (0, Cons (0, Nil\n"
     ]
    }
   ],
   "source": [
    "(* list_rev_tailcall *)\n",
    "\n",
    "type 'a mylist =\n",
    "  | Nil\n",
    "  | Cons of 'a * 'a mylist\n",
    "\n",
    "(* Function to reverse a list using tail recursion *)\n",
    "let list_rev_tailcall list =\n",
    "  let rec aux acc = function\n",
    "    | Nil -> acc\n",
    "    | Cons (x, xs) -> aux (Cons (x, acc)) xs\n",
    "  in\n",
    "  aux Nil list\n",
    "\n",
    "(* Test the function *)\n",
    "let rec print_list = function\n",
    "  | Nil -> print_endline \"Nil\"\n",
    "  | Cons (x, xs) ->\n",
    "    print_string \"Cons (\"; print_int x; print_string \", \";\n",
    "    print_list xs; print_string \")\"\n",
    "\n",
    "let () =\n",
    "  let list1 = Cons (1, Cons (2, Cons (3, Nil))) in\n",
    "  let result1 = list_rev_tailcall list1 in\n",
    "  print_string \"Expected: \"; print_list result1;\n",
    "\n",
    "  let list2 = Cons (0, Nil) in\n",
    "  let result2 = list_rev_tailcall list2 in\n",
    "  print_string \"Expected: \"; print_list result2;\n",
    "\n",
    "  let list3 = Cons (0, Cons (0, Cons (1, Nil))) in\n",
    "  let result3 = list_rev_tailcall list3 in\n",
    "  print_string \"Expected: \"; print_list result3\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "id": "5cba98fd",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val insert_unique : 'a list -> 'a -> 'a list = <fun>\n"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val sort : 'a list -> 'a list = <fun>\n"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val list_sort_sorted : 'a list -> 'a -> 'a list = <fun>\n"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      ")))1 2 3 4 5 6 \n",
      "1 2 3 4 5 \n",
      "1 2 3 4 5 \n",
      "0 \n"
     ]
    }
   ],
   "source": [
    "(* Insert a unique element into a list *)\n",
    "let insert_unique lst elem =\n",
    "  if List.mem elem lst then lst else elem :: lst\n",
    "\n",
    "(* Sort a list *)\n",
    "let sort lst = List.sort compare lst\n",
    "\n",
    "(* Combine insert_unique and sort *)\n",
    "let list_sort_sorted lst elem = \n",
    "  let updated_lst = insert_unique lst elem in\n",
    "  sort updated_lst\n",
    "\n",
    "(* Test the function *)\n",
    "let () =\n",
    "  let print_list lst =\n",
    "    let rec print_elements = function\n",
    "      | [] -> print_endline \"\"\n",
    "      | h :: t -> print_int h; print_string \" \"; print_elements t\n",
    "    in print_elements lst\n",
    "  in\n",
    "  print_list (list_sort_sorted [1; 2; 5; 3; 4] 6);\n",
    "  print_list (list_sort_sorted [1; 2; 5; 3; 4] 1);\n",
    "  print_list (list_sort_sorted [1; 2; 5; 3; 4] 4);\n",
    "  print_list (list_sort_sorted [] 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "id": "2e3caba6",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val list_stutter : 'a list -> 'a list = <fun>\n"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 1 2 2 3 3 4 4 5 5 \n"
     ]
    }
   ],
   "source": [
    "(* list_stutter *)\n",
    "\n",
    "let rec list_stutter lst = match lst with\n",
    "  | [] -> []\n",
    "  | h::t -> h :: h :: list_stutter t;;\n",
    "\n",
    "let () =\n",
    "let original_list = [1; 2; 3; 4; 5] in\n",
    "let stuttered_list = list_stutter original_list in\n",
    "List.iter (fun x -> print_int x; print_string \" \") stuttered_list;\n",
    "print_endline \"\"; (* Move the cursor to the next line *)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "id": "9e288994",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val list_sum : int list -> int = <fun>\n"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "15\n",
      "0\n",
      "60\n"
     ]
    }
   ],
   "source": [
    "(* list_sum *)\n",
    "\n",
    "(* Function to sum a list *)\n",
    "let rec list_sum = function\n",
    "  | [] -> 0\n",
    "  | h :: t -> h + list_sum t\n",
    "\n",
    "(* Test the function *)\n",
    "let () =\n",
    "  let print_sum lst =\n",
    "    let sum = list_sum lst in\n",
    "    print_int sum;\n",
    "    print_endline \"\"\n",
    "  in\n",
    "  print_sum [1; 2; 3; 4; 5]; (* This will print '15' *)\n",
    "  print_sum []; (* This will print '0' *)\n",
    "  print_sum [10; 20; 30] (* This will print '60' *)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "id": "926b0386",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val list_take : int -> 'a list -> 'a list = <fun>\n"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "\n",
      "1 \n",
      "0 \n",
      "1 0 \n"
     ]
    }
   ],
   "source": [
    "(* list_take *)\n",
    "\n",
    "(* Function to take the first n elements from a list *)\n",
    "let rec list_take n lst =\n",
    "  match n, lst with\n",
    "  | _, [] -> []\n",
    "  | 0, _ -> []\n",
    "  | n, h :: t -> h :: list_take (n-1) t\n",
    "\n",
    "(* Test the function *)\n",
    "let () =\n",
    "  let print_list lst =\n",
    "    let rec print_elements = function\n",
    "      | [] -> print_endline \"\"\n",
    "      | h :: t -> print_int h; print_string \" \"; print_elements t\n",
    "    in print_elements lst\n",
    "  in\n",
    "  print_list (list_take 0 []); (* This will print '' *)\n",
    "  print_list (list_take 0 [0; 1]); (* This will print '' *)\n",
    "  print_list (list_take 1 [1]); (* This will print '1 ' *)\n",
    "  print_list (list_take 1 [0; 1]); (* This will print '0 ' *)\n",
    "  print_list (list_take 2 [1; 0; 1]) (* This will print '1 0 ' *)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "id": "64d75ed0",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val list_tl : 'a list -> 'a list = <fun>\n"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "1 \n",
      "2 3 \n",
      "\n"
     ]
    }
   ],
   "source": [
    "(* list_tl *)\n",
    "\n",
    "(* Function to return the tail of a list *)\n",
    "let list_tl lst =\n",
    "  match lst with\n",
    "  | [] -> []\n",
    "  | _ :: t -> t\n",
    "\n",
    "(* Test the function *)\n",
    "let () =\n",
    "  let print_list lst =\n",
    "    let rec print_elements = function\n",
    "      | [] -> print_endline \"\"\n",
    "      | h :: t -> print_int h; print_string \" \"; print_elements t\n",
    "    in print_elements lst\n",
    "  in\n",
    "  print_list (list_tl []); (* This will print '' *)\n",
    "  print_list (list_tl [0; 1]); (* This will print '1 ' *)\n",
    "  print_list (list_tl [1; 2; 3]); (* This will print '2 3 ' *)\n",
    "  print_list (list_tl [10]) (* This will print '' *)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "66be6145",
   "metadata": {},
   "source": [
    "## Numbers (Nat)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "id": "0723a3b2",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "type nat = Zero | Succ of nat\n"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val nat_add : nat -> nat -> nat = <fun>\n"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val print_nat : nat -> unit = <fun>\n"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "m: Succ Succ 0\n",
      "n: Succ Succ Succ 0\n",
      "Sum: Succ Succ Succ Succ Succ 0\n"
     ]
    }
   ],
   "source": [
    "(* nat_add *)\n",
    "\n",
    "type nat = Zero | Succ of nat\n",
    "\n",
    "(* Function to add two nats *)\n",
    "let rec nat_add m n =\n",
    "  match m with\n",
    "  | Zero -> n\n",
    "  | Succ p -> Succ (nat_add p n)\n",
    "\n",
    "(* Test the function *)\n",
    "let rec print_nat = function\n",
    "  | Zero -> print_endline \"0\"\n",
    "  | Succ n -> print_string \"Succ \"; print_nat n\n",
    "\n",
    "let () =\n",
    "  let m = Succ (Succ Zero) in\n",
    "  let n = Succ (Succ (Succ Zero)) in\n",
    "  let sum = nat_add m n in\n",
    "  print_string \"m: \"; print_nat m;\n",
    "  print_string \"n: \"; print_nat n;\n",
    "  print_string \"Sum: \"; print_nat sum\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "id": "19cee2bb",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "type nat = Zero | Succ of nat\n"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val nat_iseven : nat -> bool = <fun>\n"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val print_nat : nat -> unit = <fun>\n"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "n1: Succ Succ 0\n",
      "Is n1 even? true\n",
      "n2: Succ Succ Succ 0\n",
      "Is n2 even? false\n"
     ]
    }
   ],
   "source": [
    "(* nat_iseven *)\n",
    "\n",
    "type nat = Zero | Succ of nat\n",
    "\n",
    "(* Function to check if a nat is even *)\n",
    "let rec nat_iseven n =\n",
    "  match n with\n",
    "  | Zero -> true\n",
    "  | Succ Zero -> false\n",
    "  | Succ (Succ p) -> nat_iseven p\n",
    "\n",
    "(* Test the function *)\n",
    "let rec print_nat = function\n",
    "  | Zero -> print_endline \"0\"\n",
    "  | Succ n -> print_string \"Succ \"; print_nat n\n",
    "\n",
    "let () =\n",
    "  let n1 = Succ (Succ Zero) in\n",
    "  let n2 = Succ (Succ (Succ Zero)) in\n",
    "  print_string \"n1: \"; print_nat n1;\n",
    "  print_string \"Is n1 even? \"; print_endline (string_of_bool (nat_iseven n1));\n",
    "  print_string \"n2: \"; print_nat n2;\n",
    "  print_string \"Is n2 even? \"; print_endline (string_of_bool (nat_iseven n2))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "id": "84c52dec",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "type nat = Zero | Succ of nat\n"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val nat_max : nat -> nat -> nat = <fun>\n"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val print_nat : nat -> unit = <fun>\n"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "n1: Succ Succ 0\n",
      "n2: Succ Succ Succ 0\n",
      "Max: Succ Succ Succ 0\n"
     ]
    }
   ],
   "source": [
    "(* nat_max *)\n",
    "\n",
    "type nat = Zero | Succ of nat\n",
    "\n",
    "(* Function to find the maximum of two nats *)\n",
    "let rec nat_max m n =\n",
    "  match m, n with\n",
    "  | Zero, _ -> n\n",
    "  | _, Zero -> m\n",
    "  | Succ p, Succ q -> Succ (nat_max p q)\n",
    "\n",
    "(* Test the function *)\n",
    "let rec print_nat = function\n",
    "  | Zero -> print_endline \"0\"\n",
    "  | Succ n -> print_string \"Succ \"; print_nat n\n",
    "\n",
    "let () =\n",
    "  let n1 = Succ (Succ Zero) in\n",
    "  let n2 = Succ (Succ (Succ Zero)) in\n",
    "  let max = nat_max n1 n2 in\n",
    "  print_string \"n1: \"; print_nat n1;\n",
    "  print_string \"n2: \"; print_nat n2;\n",
    "  print_string \"Max: \"; print_nat max\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "id": "90e0272d",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "type nat = Zero | Succ of nat\n"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val nat_pred : nat -> nat = <fun>\n"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val print_nat : nat -> unit = <fun>\n"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "n1: Succ Succ 0\n",
      "Predecessor of n1: Succ 0\n",
      "n2: Succ Succ Succ 0\n",
      "Predecessor of n2: Succ Succ 0\n"
     ]
    }
   ],
   "source": [
    "(* nat_pred *)\n",
    "\n",
    "type nat = Zero | Succ of nat\n",
    "\n",
    "(* Function to find the predecessor of a nat *)\n",
    "let rec nat_pred n =\n",
    "  match n with\n",
    "  | Zero -> Zero\n",
    "  | Succ p -> p\n",
    "\n",
    "(* Test the function *)\n",
    "let rec print_nat = function\n",
    "  | Zero -> print_endline \"0\"\n",
    "  | Succ n -> print_string \"Succ \"; print_nat n\n",
    "\n",
    "let () =\n",
    "  let n1 = Succ (Succ Zero) in\n",
    "  let n2 = Succ (Succ (Succ Zero)) in\n",
    "  let pred1 = nat_pred n1 in\n",
    "  let pred2 = nat_pred n2 in\n",
    "  print_string \"n1: \"; print_nat n1;\n",
    "  print_string \"Predecessor of n1: \"; print_nat pred1;\n",
    "  print_string \"n2: \"; print_nat n2;\n",
    "  print_string \"Predecessor of n2: \"; print_nat pred2\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "11d834e7",
   "metadata": {},
   "source": [
    "## Trees"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "id": "45097039",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "type 'a tree = Leaf | Node of 'a tree * 'a * 'a tree\n"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val tree_binsert : ('a -> 'a -> int) -> 'a -> 'a tree -> 'a tree = <fun>\n"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val cmp_int : 'a -> 'a -> int = <fun>\n"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val print_tree : int tree -> unit = <fun>\n"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Expected: Node (Node (Node (Leaf, 0, Leaf), 1, Leaf), 2, Leaf)\n"
     ]
    }
   ],
   "source": [
    "(* tree_binsert *)\n",
    "\n",
    "type 'a tree =\n",
    "  | Leaf\n",
    "  | Node of 'a tree * 'a * 'a tree\n",
    "\n",
    "(* Function to insert an element into a binary search tree *)\n",
    "let rec tree_binsert cmp elem tree =\n",
    "  match tree with\n",
    "  | Leaf -> Node (Leaf, elem, Leaf)\n",
    "  | Node (left, value, right) ->\n",
    "      let cmp_result = cmp elem value in\n",
    "      if cmp_result < 0 then\n",
    "        Node (tree_binsert cmp elem left, value, right)\n",
    "      else if cmp_result > 0 then\n",
    "        Node (left, value, tree_binsert cmp elem right)\n",
    "      else\n",
    "        tree\n",
    "\n",
    "(* Test the function *)\n",
    "let cmp_int a b = compare a b\n",
    "\n",
    "let rec print_tree = function\n",
    "  | Leaf -> print_string \"Leaf\"\n",
    "  | Node (left, value, right) ->\n",
    "      print_string \"Node (\";\n",
    "      print_tree left;\n",
    "      print_string \", \";\n",
    "      print_int value;\n",
    "      print_string \", \";\n",
    "      print_tree right;\n",
    "      print_string \")\"\n",
    "\n",
    "let () =\n",
    "  let test_tree = Node (Node (Leaf, 1, Leaf), 2, Leaf) in\n",
    "  let new_tree = tree_binsert cmp_int 0 test_tree in\n",
    "  print_string \"Expected: \";\n",
    "  print_tree new_tree;\n",
    "  print_endline \"\"\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "id": "05292355",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "type 'a tree = Leaf | Node of 'a tree * 'a * 'a tree\n"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val tree_collect_leaves : 'a tree -> 'a list = <fun>\n"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val print_list : bool list -> unit = <fun>\n"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Expected: Nil\n",
      "Expected: Cons(true, Nil)\n",
      "Expected: Cons(true, Nil)\n",
      "Expected: Cons(true, Cons(true, Nil))\n"
     ]
    }
   ],
   "source": [
    "(* tree_collect_leaves *)\n",
    "\n",
    "type 'a tree =\n",
    "  | Leaf\n",
    "  | Node of 'a tree * 'a * 'a tree\n",
    "\n",
    "(* Function to collect the leaf values from a tree *)\n",
    "let rec tree_collect_leaves = function\n",
    "  | Leaf -> []\n",
    "  | Node (left, value, right) ->\n",
    "      match (left, right) with\n",
    "      | (Leaf, Leaf) -> [value]\n",
    "      | _ -> tree_collect_leaves left @ tree_collect_leaves right\n",
    "\n",
    "(* Test the function *)\n",
    "let rec print_list = function\n",
    "  | [] -> print_string \"Nil\"\n",
    "  | [x] -> print_string \"Cons(\"; print_string (string_of_bool x); print_string \", Nil)\"\n",
    "  | h :: t ->\n",
    "      print_string \"Cons(\"; print_string (string_of_bool h); print_string \", \";\n",
    "      print_list t;\n",
    "      print_string \")\"\n",
    "\n",
    "let () =\n",
    "  let tree1 = Leaf in\n",
    "  let leaves1 = tree_collect_leaves tree1 in\n",
    "  print_string \"Expected: \";\n",
    "  print_list leaves1;\n",
    "  print_endline \"\";\n",
    "\n",
    "  let tree2 = Node (Node (Leaf, true, Leaf), false, Leaf) in\n",
    "  let leaves2 = tree_collect_leaves tree2 in\n",
    "  print_string \"Expected: \";\n",
    "  print_list leaves2;\n",
    "  print_endline \"\";\n",
    "\n",
    "  let tree3 = Node (Leaf, false, Node (Leaf, true, Leaf)) in\n",
    "  let leaves3 = tree_collect_leaves tree3 in\n",
    "  print_string \"Expected: \";\n",
    "  print_list leaves3;\n",
    "  print_endline \"\";\n",
    "\n",
    "  let tree4 = Node (Node (Leaf, true, Leaf), false, Node (Leaf, true, Leaf)) in\n",
    "  let leaves4 = tree_collect_leaves tree4 in\n",
    "  print_string \"Expected: \";\n",
    "  print_list leaves4;\n",
    "  print_endline \"\"\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "id": "124a21e6",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "type 'a tree = Leaf | Node of 'a tree * 'a * 'a tree\n"
      ]
     },
     "execution_count": 38,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val tree_count_leaves : 'a tree -> int = <fun>\n"
      ]
     },
     "execution_count": 38,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Expected: 1, Count: 1\n",
      "Expected: 3, Count: 3\n",
      "Expected: 4, Count: 4\n"
     ]
    }
   ],
   "source": [
    "(* tree_count_leaves *)\n",
    "\n",
    "type 'a tree =\n",
    "  | Leaf\n",
    "  | Node of 'a tree * 'a * 'a tree\n",
    "\n",
    "(* Function to count the number of leaf nodes in a tree *)\n",
    "let rec tree_count_leaves = function\n",
    "  | Leaf -> 1\n",
    "  | Node (left, _, right) ->\n",
    "      tree_count_leaves left + tree_count_leaves right\n",
    "\n",
    "(* Test the function *)\n",
    "let () =\n",
    "  let tree1 = Leaf in\n",
    "  let count1 = tree_count_leaves tree1 in\n",
    "  print_string \"Expected: 1, Count: \"; print_int count1; print_endline \"\";\n",
    "\n",
    "  let tree2 = Node (Node (Leaf, true, Leaf), true, Leaf) in\n",
    "  let count2 = tree_count_leaves tree2 in\n",
    "  print_string \"Expected: 3, Count: \"; print_int count2; print_endline \"\";\n",
    "\n",
    "  let tree3 = Node (Node (Leaf, true, Leaf), true, Node (Leaf, true, Leaf)) in\n",
    "  let count3 = tree_count_leaves tree3 in\n",
    "  print_string \"Expected: 4, Count: \"; print_int count3; print_endline \"\"\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "id": "c607091e",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "type 'a tree = Leaf | Node of 'a tree * 'a * 'a tree\n"
      ]
     },
     "execution_count": 39,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val tree_count_nodes : 'a tree -> int = <fun>\n"
      ]
     },
     "execution_count": 39,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Expected: 0, Count: 0\n",
      "Expected: 1, Count: 1\n",
      "Expected: 2, Count: 2\n",
      "Expected: 2, Count: 2\n",
      "Expected: 3, Count: 3\n",
      "Expected: 3, Count: 3\n"
     ]
    }
   ],
   "source": [
    "(* tree_count_nodes *)\n",
    "\n",
    "type 'a tree =\n",
    "  | Leaf\n",
    "  | Node of 'a tree * 'a * 'a tree\n",
    "\n",
    "(* Function to count the number of nodes in a tree *)\n",
    "let rec tree_count_nodes = function\n",
    "  | Leaf -> 0\n",
    "  | Node (left, _, right) ->\n",
    "      1 + tree_count_nodes left + tree_count_nodes right\n",
    "\n",
    "(* Test the function *)\n",
    "let () =\n",
    "  let tree1 = Leaf in\n",
    "  let count1 = tree_count_nodes tree1 in\n",
    "  print_string \"Expected: 0, Count: \"; print_int count1; print_endline \"\";\n",
    "\n",
    "  let tree2 = Node (Leaf, 0, Leaf) in\n",
    "  let count2 = tree_count_nodes tree2 in\n",
    "  print_string \"Expected: 1, Count: \"; print_int count2; print_endline \"\";\n",
    "\n",
    "  let tree3 = Node (Node (Leaf, 0, Leaf), 0, Leaf) in\n",
    "  let count3 = tree_count_nodes tree3 in\n",
    "  print_string \"Expected: 2, Count: \"; print_int count3; print_endline \"\";\n",
    "\n",
    "  let tree4 = Node (Leaf, 0, Node (Leaf, 0, Leaf)) in\n",
    "  let count4 = tree_count_nodes tree4 in\n",
    "  print_string \"Expected: 2, Count: \"; print_int count4; print_endline \"\";\n",
    "\n",
    "  let tree5 = Node (Node (Leaf, 0, Node (Leaf, 0, Leaf)), 0, Leaf) in\n",
    "  let count5 = tree_count_nodes tree5 in\n",
    "  print_string \"Expected: 3, Count: \"; print_int count5; print_endline \"\";\n",
    "\n",
    "  let tree6 = Node (Leaf, 0, Node (Leaf, 0, Node (Leaf, 0, Leaf))) in\n",
    "  let count6 = tree_count_nodes tree6 in\n",
    "  print_string \"Expected: 3, Count: \"; print_int count6; print_endline \"\"\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "id": "ffee59f1",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "type 'a tree = Leaf | Node of 'a tree * 'a * 'a tree\n"
      ]
     },
     "execution_count": 40,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val tree_inorder : 'a tree -> 'a list = <fun>\n"
      ]
     },
     "execution_count": 40,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val print_list : int list -> unit = <fun>\n"
      ]
     },
     "execution_count": 40,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Expected: Nil\n",
      "Expected: Cons(1, Nil)\n",
      "Expected: Cons(1, Cons(2, Nil))\n",
      "Expected: Cons(1, Cons(2, Nil))\n"
     ]
    }
   ],
   "source": [
    "(* tree_inorder *)\n",
    "\n",
    "type 'a tree =\n",
    "  | Leaf\n",
    "  | Node of 'a tree * 'a * 'a tree\n",
    "\n",
    "(* Function to perform an inorder traversal of a tree *)\n",
    "let rec tree_inorder = function\n",
    "  | Leaf -> []\n",
    "  | Node (left, value, right) ->\n",
    "      tree_inorder left @ [value] @ tree_inorder right\n",
    "\n",
    "(* Test the function *)\n",
    "let rec print_list = function\n",
    "  | [] -> print_string \"Nil\"\n",
    "  | h :: t -> print_string \"Cons(\"; print_int h; print_string \", \"; print_list t; print_string \")\"\n",
    "\n",
    "let () =\n",
    "  let tree1 = Leaf in\n",
    "  let inorder1 = tree_inorder tree1 in\n",
    "  print_string \"Expected: \"; \n",
    "  print_list inorder1;\n",
    "  print_endline \"\";\n",
    "\n",
    "  let tree2 = Node (Leaf, 1, Leaf) in\n",
    "  let inorder2 = tree_inorder tree2 in\n",
    "  print_string \"Expected: \"; \n",
    "  print_list inorder2;\n",
    "  print_endline \"\";\n",
    "\n",
    "  let tree3 = Node (Node (Leaf, 1, Leaf), 2, Leaf) in\n",
    "  let inorder3 = tree_inorder tree3 in\n",
    "  print_string \"Expected: \"; \n",
    "  print_list inorder3;\n",
    "  print_endline \"\";\n",
    "\n",
    "  let tree4 = Node (Leaf, 1, Node (Leaf, 2, Leaf)) in\n",
    "  let inorder4 = tree_inorder tree4 in\n",
    "  print_string \"Expected: \"; \n",
    "  print_list inorder4;\n",
    "  print_endline \"\"\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "id": "ef09d6eb",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "type 'a tree = Leaf | Node of 'a tree * 'a * 'a tree\n"
      ]
     },
     "execution_count": 41,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val tree_map : ('a -> 'b) -> 'a tree -> 'b tree = <fun>\n"
      ]
     },
     "execution_count": 41,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val div2 : int -> int = <fun>\n"
      ]
     },
     "execution_count": 41,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val inc : int -> int = <fun>\n"
      ]
     },
     "execution_count": 41,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val print_tree : int tree -> unit = <fun>\n"
      ]
     },
     "execution_count": 41,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Expected: Leaf\n",
      "Expected: Node (Node (Leaf, 1, Leaf), 1, Leaf)\n",
      "Expected: Node (Leaf, 0, Node (Leaf, 1, Leaf))\n",
      "Expected: Node (Leaf, 1, Leaf)\n"
     ]
    }
   ],
   "source": [
    "(* tree_map *)\n",
    "\n",
    "type 'a tree =\n",
    "  | Leaf\n",
    "  | Node of 'a tree * 'a * 'a tree\n",
    "\n",
    "(* Function to apply a function to each element of a tree *)\n",
    "let rec tree_map f = function\n",
    "  | Leaf -> Leaf\n",
    "  | Node (left, value, right) ->\n",
    "      Node (tree_map f left, f value, tree_map f right)\n",
    "\n",
    "(* Test the function *)\n",
    "let div2 x = x / 2\n",
    "let inc x = x + 1\n",
    "\n",
    "let rec print_tree = function\n",
    "  | Leaf -> print_string \"Leaf\"\n",
    "  | Node (left, value, right) ->\n",
    "      print_string \"Node (\";\n",
    "      print_tree left;\n",
    "      print_string \", \";\n",
    "      print_int value;\n",
    "      print_string \", \";\n",
    "      print_tree right;\n",
    "      print_string \")\"\n",
    "\n",
    "let () =\n",
    "  let tree1 = Leaf in\n",
    "  let mapped1 = tree_map div2 tree1 in\n",
    "  print_string \"Expected: \"; print_tree mapped1;\n",
    "  print_endline \"\";\n",
    "\n",
    "  let tree2 = Node (Node (Leaf, 2, Leaf), 2, Leaf) in\n",
    "  let mapped2 = tree_map div2 tree2 in\n",
    "  print_string \"Expected: \"; print_tree mapped2;\n",
    "  print_endline \"\";\n",
    "\n",
    "  let tree3 = Node (Leaf, 1, Node (Leaf, 2, Leaf)) in\n",
    "  let mapped3 = tree_map div2 tree3 in\n",
    "  print_string \"Expected: \"; print_tree mapped3;\n",
    "  print_endline \"\";\n",
    "\n",
    "  let tree4 = Node (Leaf, 0, Leaf) in\n",
    "  let mapped4 = tree_map inc tree4 in\n",
    "  print_string \"Expected: \"; print_tree mapped4;\n",
    "  print_endline \"\";\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "id": "0bb2557b",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "type 'a tree = Leaf | Node of 'a tree * 'a * 'a tree\n"
      ]
     },
     "execution_count": 42,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val tree_nodes_at_levels : int -> 'a tree -> int = <fun>\n"
      ]
     },
     "execution_count": 42,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val print_int_result : int -> int -> unit = <fun>\n"
      ]
     },
     "execution_count": 42,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Level 0: 1\n",
      "Level 1: 0\n",
      "Level 2: 0\n",
      "Level 3: 0\n",
      "Level 0: 1\n",
      "Level 1: 2\n",
      "Level 2: 0\n",
      "Level 3: 0\n",
      "Level 0: 1\n",
      "Level 1: 2\n",
      "Level 2: 2\n",
      "Level 3: 0\n"
     ]
    }
   ],
   "source": [
    "(* tree_nodes_at_levels *)\n",
    "type 'a tree =\n",
    "  | Leaf\n",
    "  | Node of 'a tree * 'a * 'a tree\n",
    "\n",
    "(* Function to count the number of nodes at a given level in a tree *)\n",
    "let rec tree_nodes_at_levels level = function\n",
    "  | Leaf -> if level = 0 then 1 else 0\n",
    "  | Node (left, _, right) ->\n",
    "      if level = 0 then 1\n",
    "      else tree_nodes_at_levels (level - 1) left + tree_nodes_at_levels (level - 1) right\n",
    "\n",
    "(* Test the function *)\n",
    "let rec print_int_result level result =\n",
    "  print_string \"Level \"; print_int level; print_string \": \"; print_int result; print_newline ()\n",
    "\n",
    "let () =\n",
    "  let tree1 = Leaf in\n",
    "  let level1 = 0 in\n",
    "  let result1 = tree_nodes_at_levels level1 tree1 in\n",
    "  print_int_result level1 result1;\n",
    "\n",
    "  let tree2 = Leaf in\n",
    "  let level2 = 1 in\n",
    "  let result2 = tree_nodes_at_levels level2 tree2 in\n",
    "  print_int_result level2 result2;\n",
    "\n",
    "  let tree3 = Leaf in\n",
    "  let level3 = 2 in\n",
    "  let result3 = tree_nodes_at_levels level3 tree3 in\n",
    "  print_int_result level3 result3;\n",
    "\n",
    "  let tree4 = Leaf in\n",
    "  let level4 = 3 in\n",
    "  let result4 = tree_nodes_at_levels level4 tree4 in\n",
    "  print_int_result level4 result4;\n",
    "\n",
    "  let tree5 = Node (Leaf, true, Leaf) in\n",
    "  let level5 = 0 in\n",
    "  let result5 = tree_nodes_at_levels level5 tree5 in\n",
    "  print_int_result level5 result5;\n",
    "\n",
    "  let tree6 = Node (Leaf, true, Leaf) in\n",
    "  let level6 = 1 in\n",
    "  let result6 = tree_nodes_at_levels level6 tree6 in\n",
    "  print_int_result level6 result6;\n",
    "\n",
    "  let tree7 = Node (Leaf, true, Leaf) in\n",
    "  let level7 = 2 in\n",
    "  let result7 = tree_nodes_at_levels level7 tree7 in\n",
    "  print_int_result level7 result7;\n",
    "\n",
    "  let tree8 = Node (Leaf, true, Leaf) in\n",
    "  let level8 = 3 in\n",
    "  let result8 = tree_nodes_at_levels level8 tree8 in\n",
    "  print_int_result level8 result8;\n",
    "\n",
    "  let tree9 = Node (Node (Leaf, true, Leaf), true, Leaf) in\n",
    "  let level9 = 0 in\n",
    "  let result9 = tree_nodes_at_levels level9 tree9 in\n",
    "  print_int_result level9 result9;\n",
    "\n",
    "  let tree10 = Node (Node (Leaf, true, Leaf), true, Leaf) in\n",
    "  let level10 = 1 in\n",
    "  let result10 = tree_nodes_at_levels level10 tree10 in\n",
    "  print_int_result level10 result10;\n",
    "\n",
    "  let tree11 = Node (Node (Leaf, true, Leaf), true, Leaf) in\n",
    "  let level11 = 2 in\n",
    "  let result11 = tree_nodes_at_levels level11 tree11 in\n",
    "  print_int_result level11 result11;\n",
    "\n",
    "  let tree12 = Node (Node (Leaf, true, Leaf), true, Leaf) in\n",
    "  let level12 = 3 in\n",
    "  let result12 = tree_nodes_at_levels level12 tree12 in\n",
    "  print_int_result level12 result12;\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "id": "54c85a62",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "type 'a tree = Leaf | Node of 'a tree * 'a * 'a tree\n"
      ]
     },
     "execution_count": 43,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val tree_inorder : 'a tree -> 'a list = <fun>\n"
      ]
     },
     "execution_count": 43,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val print_list : int list -> unit = <fun>\n"
      ]
     },
     "execution_count": 43,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Expected: Nil\n",
      "Expected: Cons(1, Nil)\n",
      "Expected: Cons(1, Cons(2, Nil))\n",
      "Expected: Cons(2, Cons(1, Nil))\n"
     ]
    }
   ],
   "source": [
    "(* tree_postorder *)\n",
    "\n",
    "type 'a tree =\n",
    "  | Leaf\n",
    "  | Node of 'a tree * 'a * 'a tree\n",
    "\n",
    "(* Function to perform an inorder traversal of a tree *)\n",
    "let rec tree_inorder = function\n",
    "  | Leaf -> []\n",
    "  | Node (left, value, right) ->\n",
    "      tree_inorder left @ tree_inorder right @ [value]\n",
    "\n",
    "(* Test the function *)\n",
    "let rec print_list = function\n",
    "  | [] -> print_string \"Nil\"\n",
    "  | h :: t -> print_string \"Cons(\"; print_int h; print_string \", \"; print_list t; print_string \")\"\n",
    "\n",
    "let () =\n",
    "  let tree1 = Leaf in\n",
    "  let inorder1 = tree_inorder tree1 in\n",
    "  print_string \"Expected: \"; \n",
    "  print_list inorder1;\n",
    "  print_endline \"\";\n",
    "\n",
    "  let tree2 = Node (Leaf, 1, Leaf) in\n",
    "  let inorder2 = tree_inorder tree2 in\n",
    "  print_string \"Expected: \"; \n",
    "  print_list inorder2;\n",
    "  print_endline \"\";\n",
    "\n",
    "  let tree3 = Node (Node (Leaf, 1, Leaf), 2, Leaf) in\n",
    "  let inorder3 = tree_inorder tree3 in\n",
    "  print_string \"Expected: \"; \n",
    "  print_list inorder3;\n",
    "  print_endline \"\";\n",
    "\n",
    "  let tree4 = Node (Leaf, 1, Node (Leaf, 2, Leaf)) in\n",
    "  let inorder4 = tree_inorder tree4 in\n",
    "  print_string \"Expected: \"; \n",
    "  print_list inorder4;\n",
    "  print_endline \"\"\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "id": "58dd4a0d",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "type 'a tree = Leaf | Node of 'a tree * 'a * 'a tree\n"
      ]
     },
     "execution_count": 44,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val tree_inorder : 'a tree -> 'a list = <fun>\n"
      ]
     },
     "execution_count": 44,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val print_list : int list -> unit = <fun>\n"
      ]
     },
     "execution_count": 44,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Expected: Nil\n",
      "Expected: Cons(1, Nil)\n",
      "Expected: Cons(2, Cons(1, Nil))\n",
      "Expected: Cons(1, Cons(2, Nil))\n"
     ]
    }
   ],
   "source": [
    "(* tree_preorder *)\n",
    "\n",
    "type 'a tree =\n",
    "  | Leaf\n",
    "  | Node of 'a tree * 'a * 'a tree\n",
    "\n",
    "(* Function to perform an inorder traversal of a tree *)\n",
    "let rec tree_inorder = function\n",
    "  | Leaf -> []\n",
    "  | Node (left, value, right) ->\n",
    "      [value] @ tree_inorder left @ tree_inorder right\n",
    "\n",
    "(* Test the function *)\n",
    "let rec print_list = function\n",
    "  | [] -> print_string \"Nil\"\n",
    "  | h :: t -> print_string \"Cons(\"; print_int h; print_string \", \"; print_list t; print_string \")\"\n",
    "\n",
    "let () =\n",
    "  let tree1 = Leaf in\n",
    "  let inorder1 = tree_inorder tree1 in\n",
    "  print_string \"Expected: \"; \n",
    "  print_list inorder1;\n",
    "  print_endline \"\";\n",
    "\n",
    "  let tree2 = Node (Leaf, 1, Leaf) in\n",
    "  let inorder2 = tree_inorder tree2 in\n",
    "  print_string \"Expected: \"; \n",
    "  print_list inorder2;\n",
    "  print_endline \"\";\n",
    "\n",
    "  let tree3 = Node (Node (Leaf, 1, Leaf), 2, Leaf) in\n",
    "  let inorder3 = tree_inorder tree3 in\n",
    "  print_string \"Expected: \"; \n",
    "  print_list inorder3;\n",
    "  print_endline \"\";\n",
    "\n",
    "  let tree4 = Node (Leaf, 1, Node (Leaf, 2, Leaf)) in\n",
    "  let inorder4 = tree_inorder tree4 in\n",
    "  print_string \"Expected: \"; \n",
    "  print_list inorder4;\n",
    "  print_endline \"\"\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4d9a8540",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4c83e2b5",
   "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
}