Benchmarks for Lambda Square.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "a3a93162",
   "metadata": {},
   "source": [
    "## Lists"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "8adf758e",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val add_to_each : int -> int list -> int list = <fun>\n"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val numbers : int list = [1; 2; 3; 4; 5]\n"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(* add *)\n",
    "\n",
    "let rec add_to_each num lst = \n",
    "    match lst with\n",
    "    | [] -> []\n",
    "    | h::t -> (h + num) :: (add_to_each num t);;\n",
    "\n",
    "let numbers = [1; 2; 3; 4; 5];;\n",
    "let result = add_to_each 10 numbers;;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "da3dd3d1",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val result : int list = [1; 2; 3; 4; 5; 6]\n"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(* append *)\n",
    "\n",
    "let append_elem elem lst = lst @ [elem];;\n",
    "\n",
    "let numbers = [1; 2; 3; 4; 5];;\n",
    "let result = append_elem 6 numbers;;\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "24b8e456",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val concat_lists : 'a list -> 'a list -> 'a list = <fun>\n"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val numbers1 : int list = [1; 2; 3]\n"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val numbers2 : int list = [4; 5; 6]\n"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val result : int list = [1; 2; 3; 4; 5; 6]\n"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(* concat *)\n",
    "\n",
    "let concat_lists lst1 lst2 = lst1 @ lst2;;\n",
    "\n",
    "let numbers1 = [1; 2; 3];;\n",
    "let numbers2 = [4; 5; 6];;\n",
    "let result = concat_lists numbers1 numbers2;;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "09696084",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "module IntSet :\n",
       "  sig\n",
       "    type elt = Int.t\n",
       "    type t = Set.Make(Int).t\n",
       "    val empty : t\n",
       "    val is_empty : t -> bool\n",
       "    val mem : elt -> t -> bool\n",
       "    val add : elt -> t -> t\n",
       "    val singleton : elt -> t\n",
       "    val remove : elt -> t -> t\n",
       "    val union : t -> t -> t\n",
       "    val inter : t -> t -> t\n",
       "    val disjoint : t -> t -> bool\n",
       "    val diff : t -> t -> t\n",
       "    val compare : t -> t -> int\n",
       "    val equal : t -> t -> bool\n",
       "    val subset : t -> t -> bool\n",
       "    val iter : (elt -> unit) -> t -> unit\n",
       "    val map : (elt -> elt) -> t -> t\n",
       "    val fold : (elt -> 'a -> 'a) -> t -> 'a -> 'a\n",
       "    val for_all : (elt -> bool) -> t -> bool\n",
       "    val exists : (elt -> bool) -> t -> bool\n",
       "    val filter : (elt -> bool) -> t -> t\n",
       "    val filter_map : (elt -> elt option) -> t -> t\n",
       "    val partition : (elt -> bool) -> t -> t * t\n",
       "    val cardinal : t -> int\n",
       "    val elements : t -> elt list\n",
       "    val min_elt : t -> elt\n",
       "    val min_elt_opt : t -> elt option\n",
       "    val max_elt : t -> elt\n",
       "    val max_elt_opt : t -> elt option\n",
       "    val choose : t -> elt\n",
       "    val choose_opt : t -> elt option\n",
       "    val split : elt -> t -> t * bool * t\n",
       "    val find : elt -> t -> elt\n",
       "    val find_opt : elt -> t -> elt option\n",
       "    val find_first : (elt -> bool) -> t -> elt\n",
       "    val find_first_opt : (elt -> bool) -> t -> elt option\n",
       "    val find_last : (elt -> bool) -> t -> elt\n",
       "    val find_last_opt : (elt -> bool) -> t -> elt option\n",
       "    val of_list : elt list -> t\n",
       "    val to_seq_from : elt -> t -> elt Seq.t\n",
       "    val to_seq : t -> elt Seq.t\n",
       "    val to_rev_seq : t -> elt Seq.t\n",
       "    val add_seq : elt Seq.t -> t -> t\n",
       "    val of_seq : elt Seq.t -> t\n",
       "  end\n"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val remove_duplicates : IntSet.elt list -> IntSet.elt list = <fun>\n"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val numbers : int list = [1; 2; 2; 3; 4; 4; 5; 5; 6]\n"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val result : IntSet.elt list = [1; 2; 3; 4; 5; 6]\n"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(* dedup *)\n",
    "\n",
    "module IntSet = Set.Make(Int);;\n",
    "\n",
    "let remove_duplicates lst =\n",
    "  let rec aux set lst =\n",
    "    match lst with\n",
    "    | [] -> []\n",
    "    | h :: t -> if IntSet.mem h set then aux set t\n",
    "                else h :: aux (IntSet.add h set) t\n",
    "  in aux IntSet.empty lst;;\n",
    "\n",
    "let numbers = [1; 2; 2; 3; 4; 4; 5; 5; 6];;\n",
    "let result = remove_duplicates numbers;;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "80c63ccc",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val drop_last : 'a list -> 'a list = <fun>\n"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val numbers : int list = [1; 2; 3; 4; 5]\n"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val result : int list = [1; 2; 3; 4]\n"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(* droplast *)\n",
    "\n",
    "let rec drop_last lst =\n",
    "  match lst with\n",
    "  | [] -> failwith \"Can't drop from an empty list\"\n",
    "  | [_] -> []\n",
    "  | h::t -> h :: drop_last t;;\n",
    "\n",
    "let numbers = [1; 2; 3; 4; 5];;\n",
    "let result = drop_last numbers;;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "4a6d5b7a",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val drop_largest : int list -> int list = <fun>\n"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val numbers : int list = [1; 2; 3; 4; 5; 4; 3; 2; 1; 5]\n"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val result : int list = [1; 2; 3; 4; 4; 3; 2; 1]\n"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(* dropmax *)\n",
    "\n",
    "let drop_largest lst =\n",
    "  let max_val = List.fold_left max min_int lst in\n",
    "  List.filter (fun x -> x <> max_val) lst;;\n",
    "\n",
    "let numbers = [1; 2; 3; 4; 5; 4; 3; 2; 1; 5];;\n",
    "let result = drop_largest numbers;;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "3ff93441",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val duplicate_each : 'a list -> 'a list = <fun>\n"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val numbers : int list = [1; 2; 3; 4; 5]\n"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val result : int list = [1; 1; 2; 2; 3; 3; 4; 4; 5; 5]\n"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(* dupli *)\n",
    "\n",
    "let duplicate_each lst = \n",
    "  let duplicate x = [x; x] in\n",
    "  List.flatten (List.map duplicate lst);;\n",
    "\n",
    "let numbers = [1; 2; 3; 4; 5];;\n",
    "let result = duplicate_each numbers;;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "05b1b12d",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val remove_odds : int list -> int list = <fun>\n"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val numbers : int list = [1; 2; 3; 4; 5; 6; 7; 8; 9; 10]\n"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val result : int list = [2; 4; 6; 8; 10]\n"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(* evens *)\n",
    "\n",
    "let remove_odds lst = List.filter (fun x -> x mod 2 = 0) lst;;\n",
    "\n",
    "let numbers = [1; 2; 3; 4; 5; 6; 7; 8; 9; 10];;\n",
    "let result = remove_odds numbers;;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "50e5e9f0",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val last_element : 'a list -> 'a = <fun>\n"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val numbers : int list = [1; 2; 3; 4; 5]\n"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val result : int = 5\n"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(* last *)\n",
    "\n",
    "let rec last_element lst =\n",
    "  match lst with\n",
    "  | [] -> failwith \"Empty list has no last element\"\n",
    "  | [x] -> x\n",
    "  | _::t -> last_element t;;\n",
    "\n",
    "let numbers = [1; 2; 3; 4; 5];;\n",
    "let result = last_element numbers;;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "ef62fdc9",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val list_length : 'a list -> int = <fun>\n"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val numbers : int list = [1; 2; 3; 4; 5]\n"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val length : int = 5\n"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(* length *)\n",
    "\n",
    "let list_length lst = List.length lst;;\n",
    "\n",
    "let numbers = [1; 2; 3; 4; 5];;\n",
    "let length = list_length numbers;;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "a3832c97",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val largest : 'a list -> 'a = <fun>\n"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val numbers : int list = [1; 2; 3; 4; 5]\n"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val max_value : int = 5\n"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(* max *)\n",
    "\n",
    "let largest lst =\n",
    "  match lst with\n",
    "  | [] -> failwith \"Empty list has no largest element\"\n",
    "  | h::t -> List.fold_left max h t;;\n",
    "\n",
    "let numbers = [1; 2; 3; 4; 5];;\n",
    "let max_value = largest numbers;;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "47e4a66a",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val is_member : 'a -> 'a list -> bool = <fun>\n"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val numbers : int list = [1; 2; 3; 4; 5]\n"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val is_3_member : bool = true\n"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val is_6_member : bool = false\n"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(* member *)\n",
    "\n",
    "let is_member item lst = List.mem item lst;;\n",
    "\n",
    "let numbers = [1; 2; 3; 4; 5];;\n",
    "let is_3_member = is_member 3 numbers;;\n",
    "let is_6_member = is_member 6 numbers;;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "790ca4b8",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val replace_with_first : 'a list -> 'a list = <fun>\n"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val numbers : int list = [1; 2; 3; 4; 5]\n"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val result : int list = [1; 1; 1; 1; 1]\n"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(* multfirst *)\n",
    "\n",
    "let replace_with_first lst =\n",
    "  match lst with\n",
    "  | [] -> []\n",
    "  | h::_ -> List.init (List.length lst) (fun _ -> h);;\n",
    "\n",
    "let numbers = [1; 2; 3; 4; 5];;\n",
    "let result = replace_with_first numbers;;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "743d7ed1",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val last_element : 'a list -> 'a = <fun>\n"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val replace_with_last : 'a list -> 'a list = <fun>\n"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val numbers : int list = [1; 2; 3; 4; 5]\n"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val result : int list = [5; 5; 5; 5; 5]\n"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(* multlast *)\n",
    "\n",
    "let rec last_element lst =\n",
    "  match lst with\n",
    "  | [] -> failwith \"Empty list has no last element\"\n",
    "  | [x] -> x\n",
    "  | _::t -> last_element t;;\n",
    "\n",
    "let replace_with_last lst =\n",
    "  match lst with\n",
    "  | [] -> []\n",
    "  | _ -> let last = last_element lst in\n",
    "         List.init (List.length lst) (fun _ -> last);;\n",
    "\n",
    "let numbers = [1; 2; 3; 4; 5];;\n",
    "let result = replace_with_last numbers;;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "c56e09f4",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val reverse_list : 'a list -> 'a list = <fun>\n"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val numbers : int list = [1; 2; 3; 4; 5]\n"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val reversed : int list = [5; 4; 3; 2; 1]\n"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(* reverse *)\n",
    "\n",
    "let reverse_list lst = List.rev lst;;\n",
    "\n",
    "let numbers = [1; 2; 3; 4; 5];;\n",
    "let reversed = reverse_list numbers;;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "09f36511",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val shift_left : 'a list -> 'a -> 'a list = <fun>\n"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val numbers : int list = [1; 2; 3; 4; 5]\n"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val shifted : int list = [2; 3; 4; 5; 0]\n"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(* shiftl *)\n",
    "\n",
    "let shift_left lst default_val =\n",
    "  match lst with\n",
    "  | [] -> []\n",
    "  | _ -> List.append (List.tl lst) [default_val];;\n",
    "\n",
    "let numbers = [1; 2; 3; 4; 5];;\n",
    "let shifted = shift_left numbers 0;;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "7a382cf4",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val remove_last : 'a list -> 'a list = <fun>\n"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val shift_right : 'a list -> 'a -> 'a list = <fun>\n"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val numbers : int list = [1; 2; 3; 4; 5]\n"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val shifted : int list = [0; 1; 2; 3; 4]\n"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(* shiftr *)\n",
    "\n",
    "let rec remove_last = function\n",
    "  | [] -> failwith \"Cannot remove last element of empty list\"\n",
    "  | [_] -> []\n",
    "  | h :: t -> h :: remove_last t;;\n",
    "\n",
    "let shift_right lst default_val =\n",
    "  match lst with\n",
    "  | [] -> []\n",
    "  | _ -> default_val :: remove_last lst;;\n",
    "\n",
    "let numbers = [1; 2; 3; 4; 5];;\n",
    "let shifted = shift_right numbers 0;;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "e58d98ff",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val sum_list : int list -> int = <fun>\n"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val numbers : int list = [1; 2; 3; 4; 5]\n"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val sum : int = 15\n"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(* sum *)\n",
    "\n",
    "let sum_list lst = List.fold_left (+) 0 lst;;\n",
    "\n",
    "let numbers = [1; 2; 3; 4; 5];;\n",
    "let sum = sum_list numbers;;"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f3c292d3",
   "metadata": {},
   "source": [
    "## Trees"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "955a6aea",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "type 'a tree = Empty | Node of 'a * 'a tree * 'a tree\n"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "type 'a tree =\n",
    "  | Empty\n",
    "  | Node of 'a * 'a tree * 'a tree;;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "id": "99031b81",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val count_leaves : 'a tree -> int = <fun>\n"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val t : int tree = Node (1, Node (2, Empty, Empty), Node (3, Empty, Empty))\n"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val num_leaves : int = 2\n"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(* count_leaves *)\n",
    "\n",
    "let rec count_leaves = function\n",
    "  | Empty -> 0\n",
    "  | Node (_, Empty, Empty) -> 1\n",
    "  | Node (_, left, right) -> count_leaves left + count_leaves right;;\n",
    "\n",
    "let t = Node (1, Node (2, Empty, Empty), Node (3, Empty, Empty));;\n",
    "let num_leaves = count_leaves t;;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "id": "5bdee860",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val count_nodes : 'a tree -> int = <fun>\n"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val t : int tree = Node (1, Node (2, Empty, Empty), Node (3, Empty, Empty))\n"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val num_nodes : int = 3\n"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(* count_nodes *)\n",
    "\n",
    "let rec count_nodes = function\n",
    "  | Empty -> 0\n",
    "  | Node (_, left, right) -> 1 + count_nodes left + count_nodes right;;\n",
    "\n",
    "let t = Node (1, Node (2, Empty, Empty), Node (3, Empty, Empty));;\n",
    "let num_nodes = count_nodes t;;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "id": "147d776e",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val flatten_tree : 'a tree -> 'a list = <fun>\n"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val t : int tree = Node (1, Node (2, Empty, Empty), Node (3, Empty, Empty))\n"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val flattened : int list = [2; 1; 3]\n"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(* flatten *)\n",
    "\n",
    "let rec flatten_tree = function\n",
    "  | Empty -> []\n",
    "  | Node (value, left, right) -> flatten_tree left @ [value] @ flatten_tree right;;\n",
    "\n",
    "let t = Node (1, Node (2, Empty, Empty), Node (3, Empty, Empty));;\n",
    "let flattened = flatten_tree t;;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "id": "420dabad",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val height : 'a tree -> int = <fun>\n"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val t : int tree =\n",
       "  Node (1, Node (2, Empty, Empty), Node (3, Empty, Node (4, Empty, Empty)))\n"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val h : int = 3\n"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(* height *)\n",
    "\n",
    "let rec height = function\n",
    "  | Empty -> 0\n",
    "  | Node (_, left, right) -> 1 + max (height left) (height right);;\n",
    "\n",
    "let t = Node (1, Node (2, Empty, Empty), Node (3, Empty, Node (4, Empty, Empty)));;\n",
    "let h = height t;;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "id": "f187b44d",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val increment_tree : int tree -> int tree = <fun>\n"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val t : int tree = Node (1, Node (2, Empty, Empty), Node (3, Empty, Empty))\n"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val incremented : int tree =\n",
       "  Node (2, Node (3, Empty, Empty), Node (4, Empty, Empty))\n"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(* incrt *)\n",
    "\n",
    "let rec increment_tree = function\n",
    "  | Empty -> Empty\n",
    "  | Node (value, left, right) -> Node (value + 1, increment_tree left, increment_tree right);;\n",
    "\n",
    "let t = Node (1, Node (2, Empty, Empty), Node (3, Empty, Empty));;\n",
    "let incremented = increment_tree t;;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "id": "1e767593",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val leaves : 'a tree -> 'a list = <fun>\n"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val t : int tree =\n",
       "  Node (1, Node (2, Empty, Empty), Node (3, Empty, Node (4, Empty, Empty)))\n"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val leaf_list : int list = [2; 4]\n"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(* leaves *)\n",
    "\n",
    "let rec leaves = function\n",
    "  | Empty -> []\n",
    "  | Node (value, Empty, Empty) -> [value]\n",
    "  | Node (_, left, right) -> leaves left @ leaves right;;\n",
    "\n",
    "let t = Node (1, Node (2, Empty, Empty), Node (3, Empty, Node (4, Empty, Empty)));;\n",
    "let leaf_list = leaves t;;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "id": "3e723262",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val max_in_tree : 'a tree -> 'a = <fun>\n"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val t : int tree =\n",
       "  Node (1, Node (2, Empty, Empty), Node (3, Empty, Node (4, Empty, Empty)))\n"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val max_val : int = 4\n"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(* maxt *)\n",
    "\n",
    "let rec max_in_tree = function\n",
    "  | Empty -> failwith \"Cannot find maximum in empty tree\"\n",
    "  | Node (value, left, right) ->\n",
    "    let max_left = if left = Empty then value else max_in_tree left in\n",
    "    let max_right = if right = Empty then value else max_in_tree right in\n",
    "    max value (max max_left max_right);;\n",
    "\n",
    "let t = Node (1, Node (2, Empty, Empty), Node (3, Empty, Node (4, Empty, Empty)));;\n",
    "let max_val = max_in_tree t;;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "id": "c273446e",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val is_element_in_tree : 'a -> 'a tree -> bool = <fun>\n"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val t : int tree =\n",
       "  Node (1, Node (2, Empty, Empty), Node (3, Empty, Node (4, Empty, Empty)))\n"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val is_in_tree : bool = true\n"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(* membert *)\n",
    "\n",
    "let rec is_element_in_tree element = function\n",
    "  | Empty -> false\n",
    "  | Node (value, left, right) ->\n",
    "    value = element || is_element_in_tree element left || is_element_in_tree element right;;\n",
    "    \n",
    "let t = Node (1, Node (2, Empty, Empty), Node (3, Empty, Node (4, Empty, Empty)));;\n",
    "let is_in_tree = is_element_in_tree 3 t;;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "id": "8e3c4022",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val nodes_matching_predicate : ('a -> bool) -> 'a tree -> 'a list = <fun>\n"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val t : int tree =\n",
       "  Node (1, Node (2, Empty, Empty), Node (3, Empty, Node (4, Empty, Empty)))\n"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val is_even : int -> bool = <fun>\n"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val matched_nodes : int list = [2; 4]\n"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(* selectnodes *)\n",
    "\n",
    "let rec nodes_matching_predicate pr = function\n",
    "  | Empty -> []\n",
    "  | Node (value, left, right) ->\n",
    "    if pr value then\n",
    "      value :: (nodes_matching_predicate pr left @ nodes_matching_predicate pr right)\n",
    "    else\n",
    "      nodes_matching_predicate pr left @ nodes_matching_predicate pr right;;\n",
    "\n",
    "let t = Node (1, Node (2, Empty, Empty), Node (3, Empty, Node (4, Empty, Empty)));;\n",
    "let is_even x = x mod 2 = 0;;\n",
    "let matched_nodes = nodes_matching_predicate is_even t;;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "id": "3631be93",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val sum_nodes : int tree -> int = <fun>\n"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val t : int tree =\n",
       "  Node (1, Node (2, Empty, Empty), Node (3, Empty, Node (4, Empty, Empty)))\n"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val node_sum : int = 10\n"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(* sumt *)\n",
    "\n",
    "let rec sum_nodes = function\n",
    "  | Empty -> 0\n",
    "  | Node (value, left, right) -> value + sum_nodes left + sum_nodes right;;\n",
    "\n",
    "let t = Node (1, Node (2, Empty, Empty), Node (3, Empty, Node (4, Empty, Empty)));;\n",
    "let node_sum = sum_nodes t;;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "id": "2ce1f09d",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val insert_tree_under_leaves : 'a tree -> 'a tree -> 'a tree = <fun>\n"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val original_tree : int tree =\n",
       "  Node (1, Node (2, Empty, Empty), Node (3, Empty, Empty))\n"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val subtree : int tree = Node (4, Empty, Empty)\n"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val result_tree : int tree =\n",
       "  Node (1, Node (2, Node (4, Empty, Empty), Node (4, Empty, Empty)),\n",
       "   Node (3, Node (4, Empty, Empty), Node (4, Empty, Empty)))\n"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(* tconcat *)\n",
    "\n",
    "let rec insert_tree_under_leaves original_tree subtree =\n",
    "  match original_tree with\n",
    "  | Empty -> Empty\n",
    "  | Node (value, Empty, Empty) -> Node (value, subtree, subtree)\n",
    "  | Node (value, left, right) ->\n",
    "      Node (value, insert_tree_under_leaves left subtree, insert_tree_under_leaves right subtree);;\n",
    "\n",
    "let original_tree = Node (1, Node (2, Empty, Empty), Node (3, Empty, Empty));;\n",
    "let subtree = Node (4, Empty, Empty);;\n",
    "let result_tree = insert_tree_under_leaves original_tree subtree;;"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e28addf9",
   "metadata": {},
   "source": [
    "## Nested Structures"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "id": "ee84f1f9",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "type 'a tree = Empty | Node of 'a list * 'a tree * 'a tree\n"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "type 'a tree =\n",
    "  | Empty\n",
    "  | Node of 'a list * 'a tree * 'a tree;;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "id": "254e41f0",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val append_to_each_node : 'a tree -> 'a -> 'a tree = <fun>\n"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val original_tree : int tree =\n",
       "  Node ([1; 2], Node ([3], Empty, Empty), Node ([4; 5], Empty, Empty))\n"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val element : int = 6\n"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val result_tree : int tree =\n",
       "  Node ([1; 2; 6], Node ([3; 6], Empty, Empty),\n",
       "   Node ([4; 5; 6], Empty, Empty))\n"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(* appendt *)\n",
    "\n",
    "let rec append_to_each_node original_tree element =\n",
    "  match original_tree with\n",
    "  | Empty -> Empty\n",
    "  | Node (lst, left, right) ->\n",
    "      let appended_lst = List.append lst [element] in\n",
    "      Node (appended_lst, append_to_each_node left element, append_to_each_node right element);;\n",
    "\n",
    "let original_tree = Node ([1; 2], Node ([3], Empty, Empty), Node ([4; 5], Empty, Empty));;\n",
    "let element = 6;;\n",
    "let result_tree = append_to_each_node original_tree element;;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "id": "dd10276a",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val cartesian_product : 'a list list -> 'a list list = <fun>\n"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val lists : int list list = [[1; 2]; [3; 4]; [5; 6]]\n"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val result : int list list =\n",
       "  [[1; 3; 5]; [1; 3; 6]; [1; 4; 5]; [1; 4; 6]; [2; 3; 5]; [2; 3; 6];\n",
       "   [2; 4; 5]; [2; 4; 6]]\n"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(* cprod *)\n",
    "\n",
    "let rec cartesian_product lists =\n",
    "  match lists with\n",
    "  | [] -> [[]]\n",
    "  | hd_list :: tl_lists ->\n",
    "      let rest_product = cartesian_product tl_lists in\n",
    "      List.concat (\n",
    "        List.map (fun x -> List.map (fun y -> x :: y) rest_product) hd_list\n",
    "      );;\n",
    "\n",
    "let lists = [[1; 2]; [3; 4]; [5; 6]];;\n",
    "let result = cartesian_product lists;;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "id": "91141e2e",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val drop_smallest : int list list -> int list list = <fun>\n"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val lists : int list list = [[3; 1; 4]; [2; 5; 1]; [6; 4; 2]; [1; 7; 3]]\n"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val result : int list list = [[3; 4]; [2; 5]; [6; 4]; [7; 3]]\n"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(* dropmins *)\n",
    "\n",
    "let rec drop_smallest lists =\n",
    "  let rec find_smallest acc = function\n",
    "    | [] -> acc\n",
    "    | hd :: tl -> find_smallest (min acc hd) tl\n",
    "  in\n",
    "  match lists with\n",
    "  | [] -> []\n",
    "  | lst :: tl ->\n",
    "      let smallest = find_smallest max_int lst in\n",
    "      let updated_lst = List.filter (fun x -> x <> smallest) lst in\n",
    "      updated_lst :: drop_smallest tl;;\n",
    "\n",
    "let lists = [[3; 1; 4]; [2; 5; 1]; [6; 4; 2]; [1; 7; 3]];;\n",
    "let result = drop_smallest lists;;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "id": "4288f72a",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val flatten_tree : 'a tree -> 'a list = <fun>\n"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val t : int tree =\n",
       "  Node ([1; 2], Node ([3], Empty, Empty), Node ([4; 5], Empty, Empty))\n"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val flattened : int list = [1; 2; 3; 4; 5]\n"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(* flattenl *)\n",
    "\n",
    "let rec flatten_tree = function\n",
    "  | Empty -> []\n",
    "  | Node (lst, left, right) ->\n",
    "      lst @ (flatten_tree left) @ (flatten_tree right);;\n",
    "\n",
    "let t = Node ([1; 2], Node ([3], Empty, Empty), Node ([4; 5], Empty, Empty));;\n",
    "let flattened = flatten_tree t;;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "id": "6550f436",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val increment_lists : int list list -> int -> int list list = <fun>\n"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val lists : int list list = [[1; 2; 3]; [4; 5; 6]; [7; 8; 9]]\n"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val increment_value : int = 2\n"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val result : int list list = [[3; 4; 5]; [6; 7; 8]; [9; 10; 11]]\n"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(* incrs *)\n",
    "\n",
    "let rec increment_lists lists increment_value =\n",
    "  List.map (fun lst -> List.map (fun x -> x + increment_value) lst) lists;;\n",
    "\n",
    "let lists = [[1; 2; 3]; [4; 5; 6]; [7; 8; 9]];;\n",
    "let increment_value = 2;;\n",
    "let result = increment_lists lists increment_value;;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "id": "e709f5fb",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val concatenate_lists : 'a list list -> 'a list = <fun>\n"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val lists : int list list = [[1; 2; 3]; [4; 5]; [6; 7; 8]]\n"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val result : int list = [1; 2; 3; 4; 5; 6; 7; 8]\n"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(* join *)\n",
    "\n",
    "let concatenate_lists lists =\n",
    "  List.concat lists;;\n",
    "\n",
    "let lists = [[1; 2; 3]; [4; 5]; [6; 7; 8]];;\n",
    "let result = concatenate_lists lists;;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "id": "534df9a4",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val prepend_to_each_list : 'a tree -> 'a -> 'a tree = <fun>\n"
      ]
     },
     "execution_count": 38,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val original_tree : int tree =\n",
       "  Node ([1; 2], Node ([3], Empty, Empty), Node ([4; 5], Empty, Empty))\n"
      ]
     },
     "execution_count": 38,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val element : int = 0\n"
      ]
     },
     "execution_count": 38,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val result_tree : int tree =\n",
       "  Node ([0; 1; 2], Node ([0; 3], Empty, Empty),\n",
       "   Node ([0; 4; 5], Empty, Empty))\n"
      ]
     },
     "execution_count": 38,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(* prependt *)\n",
    "\n",
    "let rec prepend_to_each_list original_tree element =\n",
    "  match original_tree with\n",
    "  | Empty -> Empty\n",
    "  | Node (lst, left, right) ->\n",
    "      let updated_lst = element :: lst in\n",
    "      Node (updated_lst, prepend_to_each_list left element, prepend_to_each_list right element);;\n",
    "\n",
    "let original_tree = Node ([1; 2], Node ([3], Empty, Empty), Node ([4; 5], Empty, Empty));;\n",
    "let element = 0;;\n",
    "let result_tree = prepend_to_each_list original_tree element;;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "id": "858b66b4",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val replace_in_each_list : 'a tree -> 'a -> 'a -> 'a tree = <fun>\n"
      ]
     },
     "execution_count": 39,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val original_tree : int tree =\n",
       "  Node ([1; 2; 3], Node ([4], Empty, Empty), Node ([3; 5], Empty, Empty))\n"
      ]
     },
     "execution_count": 39,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val old_element : int = 3\n"
      ]
     },
     "execution_count": 39,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val new_element : int = 6\n"
      ]
     },
     "execution_count": 39,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val result_tree : int tree =\n",
       "  Node ([1; 2; 6], Node ([4], Empty, Empty), Node ([6; 5], Empty, Empty))\n"
      ]
     },
     "execution_count": 39,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(* replacet *)\n",
    "\n",
    "let rec replace_in_each_list original_tree old_element new_element =\n",
    "  match original_tree with\n",
    "  | Empty -> Empty\n",
    "  | Node (lst, left, right) ->\n",
    "      let updated_lst = List.map (fun x -> if x = old_element then new_element else x) lst in\n",
    "      Node (updated_lst, replace_in_each_list left old_element new_element, replace_in_each_list right old_element new_element);;\n",
    "\n",
    "let original_tree = Node ([1; 2; 3], Node ([4], Empty, Empty), Node ([3; 5], Empty, Empty));;\n",
    "let old_element = 3;;\n",
    "let new_element = 6;;\n",
    "let result_tree = replace_in_each_list original_tree old_element new_element;;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "id": "9b7a234c",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val is_element_in_tree_lists : 'a -> 'a tree -> bool = <fun>\n"
      ]
     },
     "execution_count": 40,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val tree : int tree = Node ([5; 6], Node ([8; 9], Empty, Empty), Empty)\n"
      ]
     },
     "execution_count": 40,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val element : int = 6\n"
      ]
     },
     "execution_count": 40,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val result : bool = true\n"
      ]
     },
     "execution_count": 40,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(* searchnodes *)\n",
    "\n",
    "let rec is_element_in_tree_lists element tree =\n",
    "  match tree with\n",
    "  | Empty -> false\n",
    "  | Node (lst, left, right) ->\n",
    "      List.exists (fun x -> x = element) lst ||\n",
    "      is_element_in_tree_lists element left ||\n",
    "      is_element_in_tree_lists element right;;\n",
    "\n",
    "let tree = Node ([5; 6], Node ([8; 9], Empty, Empty), Empty);;\n",
    "let element = 6;;\n",
    "let result = is_element_in_tree_lists element tree;;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "id": "77cce152",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "type 'a tree = Empty | Node of 'a list * 'a tree * 'a tree\n"
      ]
     },
     "execution_count": 41,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val sum_lists : int list -> int = <fun>\n"
      ]
     },
     "execution_count": 41,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val replace_with_sum : int tree -> int tree = <fun>\n"
      ]
     },
     "execution_count": 41,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val original_tree : int tree =\n",
       "  Node ([5; 6], Node ([8; 9], Empty, Empty), Empty)\n"
      ]
     },
     "execution_count": 41,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val result_tree : int tree = Node ([11], Node ([17], Empty, Empty), Empty)\n"
      ]
     },
     "execution_count": 41,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(* sumnodes *)\n",
    "\n",
    "type 'a tree =\n",
    "  | Empty\n",
    "  | Node of 'a list * 'a tree * 'a tree;;\n",
    "\n",
    "let rec sum_lists lst =\n",
    "  List.fold_left (+) 0 lst;;\n",
    "\n",
    "let rec replace_with_sum original_tree =\n",
    "  match original_tree with\n",
    "  | Empty -> Empty\n",
    "  | Node (lst, left, right) ->\n",
    "      let sum = sum_lists lst in\n",
    "      Node ([sum], replace_with_sum left, replace_with_sum right);;\n",
    "\n",
    "let original_tree = Node ([5; 6], Node ([8; 9], Empty, Empty), Empty);;\n",
    "let result_tree = replace_with_sum original_tree;;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "id": "84b39296",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val sum_lists : int list list -> int list = <fun>\n"
      ]
     },
     "execution_count": 42,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val lists : int list list = [[1; 2; 3]; [4; 5]; [6; 7; 8]]\n"
      ]
     },
     "execution_count": 42,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val result : int list = [6; 9; 21]\n"
      ]
     },
     "execution_count": 42,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(* sums *)\n",
    "\n",
    "let sum_lists lists =\n",
    "  List.map (List.fold_left (+) 0) lists;;\n",
    "\n",
    "let lists = [[1; 2; 3]; [4; 5]; [6; 7; 8]];;\n",
    "let result = sum_lists lists;;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "id": "be246732",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "type 'a tree = Empty | Node of 'a * 'a tree * 'a tree\n"
      ]
     },
     "execution_count": 43,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val sum_tree : int tree -> int = <fun>\n"
      ]
     },
     "execution_count": 43,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val sum_trees : int tree list -> int list = <fun>\n"
      ]
     },
     "execution_count": 43,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val trees : int tree list =\n",
       "  [Node (1, Node (2, Empty, Empty), Node (3, Empty, Node (4, Empty, Empty)));\n",
       "   Node (5, Empty, Node (6, Empty, Empty))]\n"
      ]
     },
     "execution_count": 43,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val result : int list = [10; 11]\n"
      ]
     },
     "execution_count": 43,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(* sumtrees *)\n",
    "\n",
    "type 'a tree =\n",
    "  | Empty\n",
    "  | Node of 'a * 'a tree * 'a tree;;\n",
    "\n",
    "let rec sum_tree tree =\n",
    "  match tree with\n",
    "  | Empty -> 0\n",
    "  | Node (value, left, right) ->\n",
    "      value + sum_tree left + sum_tree right;;\n",
    "\n",
    "let sum_trees trees =\n",
    "  List.map sum_tree trees;;\n",
    "\n",
    "let trees = [Node (1, Node (2, Empty, Empty), Node (3, Empty, Node (4, Empty, Empty))); Node (5, Empty, Node (6, Empty, Empty))];;\n",
    "let result = sum_trees trees;;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ac5a8f3c",
   "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
}