Benchmarks for Escher.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "0fad9c36",
   "metadata": {},
   "source": [
    "## Tree Programs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "68f6e0f7",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "type 'a binary_tree = Empty | Node of 'a * 'a binary_tree * 'a binary_tree\n"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "type 'a binary_tree =\n",
    "  | Empty\n",
    "  | Node of 'a * 'a binary_tree * 'a binary_tree;;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "c7ee3df1",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val collect_leaves : 'a binary_tree -> 'a list = <fun>\n"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val test_tree : int binary_tree =\n",
       "  Node (1, Node (2, Node (4, Empty, Empty), Node (5, Empty, Empty)),\n",
       "   Node (3, Node (6, Empty, Empty), Empty))\n"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val leaves : int list = [4; 5; 6]\n"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(* collect_leaves *)\n",
    "\n",
    "let rec collect_leaves tree = \n",
    "  match tree with\n",
    "  | Empty -> []\n",
    "  | Node(v, Empty, Empty) -> [v] (* If it is a leaf node, return a list with the value *)\n",
    "  | Node(_, left, right) -> (collect_leaves left) @ (collect_leaves right);; (* Recursively collect leaves from left and right subtree *)\n",
    "\n",
    "let test_tree = \n",
    "  Node(1, \n",
    "       Node(2, \n",
    "            Node(4, Empty, Empty), \n",
    "            Node(5, Empty, Empty)), \n",
    "       Node(3, \n",
    "            Node(6, Empty, Empty), \n",
    "            Empty));;\n",
    "\n",
    "let leaves = collect_leaves test_tree;;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "31562a1e",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val count_leaves : 'a binary_tree -> int = <fun>\n"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val test_tree : int binary_tree =\n",
       "  Node (1, Node (2, Node (4, Empty, Empty), Node (5, Empty, Empty)),\n",
       "   Node (3, Node (6, Empty, Empty), Empty))\n"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val leaf_count : int = 3\n"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(* count_leaves *)\n",
    "\n",
    "let rec count_leaves tree = \n",
    "  match tree with\n",
    "  | Empty -> 0\n",
    "  | Node(_, Empty, Empty) -> 1\n",
    "  | Node(_, left, right) -> (count_leaves left) + (count_leaves right);;\n",
    "\n",
    "let test_tree = \n",
    "  Node(1, \n",
    "       Node(2, \n",
    "            Node(4, Empty, Empty), \n",
    "            Node(5, Empty, Empty)), \n",
    "       Node(3, \n",
    "            Node(6, Empty, Empty), \n",
    "            Empty));;\n",
    "\n",
    "let leaf_count = count_leaves test_tree;;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "6af48622",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "type 'a binary_tree = Empty | Node of 'a * 'a binary_tree * 'a binary_tree\n"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val hbal_tree : int -> char binary_tree list = <fun>\n"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val trees : char binary_tree list =\n",
       "  [Node ('x', Node ('x', Node ('x', Empty, Empty), Node ('x', Empty, Empty)),\n",
       "    Node ('x', Node ('x', Empty, Empty), Node ('x', Empty, Empty)));\n",
       "   Node ('x', Node ('x', Node ('x', Empty, Empty), Node ('x', Empty, Empty)),\n",
       "    Node ('x', Empty, Node ('x', Empty, Empty)));\n",
       "   Node ('x', Node ('x', Node ('x', Empty, Empty), Node ('x', Empty, Empty)),\n",
       "    Node ('x', Node ('x', Empty, Empty), Empty));\n",
       "   Node ('x', Node ('x', Empty, Node ('x', Empty, Empty)),\n",
       "    Node ('x', Node ('x', Empty, Empty), Node ('x', Empty, Empty)));\n",
       "   Node ('x', Node ('x', Empty, Node ('x', Empty, Empty)),\n",
       "    Node ('x', Empty, Node ('x', Empty, Empty)));\n",
       "   Node ('x', Node ('x', Empty, Node ('x', Empty, Empty)),\n",
       "    Node ('x', Node ('x', Empty, Empty), Empty));\n",
       "   Node ('x', Node ('x', Node ('x', Empty, Empty), Empty),\n",
       "    Node ('x', Node ('x', Empty, Empty), Node ('x', Empty, Empty)));\n",
       "   Node ('x', Node ('x', Node ('x', Empty, Empty), Empty),\n",
       "    Node ('x', Empty, Node ('x', Empty, Empty)));\n",
       "   Node ('x', Node ('x', Node ('x', Empty, Empty), Empty),\n",
       "    Node ('x', Node ('x', Empty, Empty), Empty));\n",
       "   Node ('x', Node ('x', Empty, Empty),\n",
       "    Node ('x', Node ('x', Empty, Empty), Node ('x', Empty, Empty)));\n",
       "   Node ('x', Node ('x', Empty, Empty),\n",
       "    Node ('x', Empty, Node ('x', Empty, Empty)));\n",
       "   Node ('x', Node ('x', Empty, Empty),\n",
       "    Node ('x', Node ('x', Empty, Empty), Empty));\n",
       "   Node ('x', Node ('x', Node ('x', Empty, Empty), Node ('x', Empty, Empty)),\n",
       "    Node ('x', Empty, Empty));\n",
       "   Node ('x', Node ('x', Empty, Node ('x', Empty, Empty)),\n",
       "    Node ('x', Empty, Empty));\n",
       "   Node ('x', Node ('x', Node ('x', Empty, Empty), Empty),\n",
       "    Node ('x', Empty, Empty))]\n"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val tree_count : int = 15\n"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "- : unit = ()\n"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(* hbal_tree -> The hbal_tree function generates all height-balanced binary trees of a given height *)\n",
    "\n",
    "type 'a binary_tree =\n",
    "  | Empty\n",
    "  | Node of 'a * 'a binary_tree * 'a binary_tree;;\n",
    "\n",
    "let rec hbal_tree h =\n",
    "  if h = 0 then [Empty]\n",
    "  else if h = 1 then [Node('x', Empty, Empty)]\n",
    "  else \n",
    "    let t_minus_1 = hbal_tree (h - 1)\n",
    "    and t_minus_2 = hbal_tree (h - 2) in\n",
    "    let with_t_minus_1 = List.concat (List.map (fun l -> List.map (fun r -> Node('x', l, r)) t_minus_1) t_minus_1)\n",
    "    and with_t_minus_2 = List.concat (List.map (fun l -> List.map (fun r -> Node('x', l, r)) t_minus_1) t_minus_2)\n",
    "                       @ List.concat (List.map (fun l -> List.map (fun r -> Node('x', l, r)) t_minus_2) t_minus_1)\n",
    "    in\n",
    "    with_t_minus_1 @ with_t_minus_2;;\n",
    "\n",
    "let trees = hbal_tree 3;;\n",
    "\n",
    "let tree_count = List.length trees;;\n",
    "Printf.printf \"Number of height-balanced binary trees of height 3: %d\\n\" tree_count;;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "ba9d52e9",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val nodes_at_level : 'a binary_tree -> int -> 'a list = <fun>\n"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val test_tree : int binary_tree =\n",
       "  Node (1, Node (2, Node (4, Empty, Empty), Node (5, Empty, Empty)),\n",
       "   Node (3, Node (6, Empty, Empty), Empty))\n"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val level_2_nodes : int list = [2; 3]\n"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(* nodes_at_level *)\n",
    "\n",
    "let rec nodes_at_level tree level = \n",
    "  match tree, level with\n",
    "  | Empty, _ -> []\n",
    "  | Node(v, _, _), 1 -> [v]\n",
    "  | Node(_, left, right), _ -> (nodes_at_level left (level - 1)) @ (nodes_at_level right (level - 1));;\n",
    "\n",
    "let test_tree = \n",
    "  Node(1, \n",
    "       Node(2, \n",
    "            Node(4, Empty, Empty), \n",
    "            Node(5, Empty, Empty)), \n",
    "       Node(3, \n",
    "            Node(6, Empty, Empty), \n",
    "            Empty));;\n",
    "\n",
    "let level_2_nodes = nodes_at_level test_tree 2;;"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "48b1fb1e",
   "metadata": {},
   "source": [
    "## List Programs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "7b48243e",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val compress : 'a list -> 'a list = <fun>\n"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val test_list : int list = [1; 2; 2; 3; 3; 3; 4; 1; 1; 2; 2; 2; 5; 6; 6]\n"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val compressed_list : int list = [1; 2; 3; 4; 1; 2; 5; 6]\n"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(* compress -> removes consecutive duplicates from a list *)\n",
    "\n",
    "let rec compress = function\n",
    "  | a :: (b :: _ as t) -> if a = b then compress t else a :: compress t\n",
    "  | smaller -> smaller;;\n",
    "\n",
    "let test_list = [1; 2; 2; 3; 3; 3; 4; 1; 1; 2; 2; 2; 5; 6; 6];;\n",
    "let compressed_list = compress test_list;;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "7b92b71d",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val concat : 'a list list -> 'a list = <fun>\n"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val test_lists : int list list = [[1; 2; 3]; [4; 5; 6]; [7; 8; 9]]\n"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val concatenated_list : int list = [1; 2; 3; 4; 5; 6; 7; 8; 9]\n"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(* concat -> flatten a list of lists *)\n",
    "\n",
    "let rec concat = function\n",
    "  | [] -> []\n",
    "  | h::t -> h @ concat t;;\n",
    "\n",
    "let test_lists = [[1; 2; 3]; [4; 5; 6]; [7; 8; 9]];;\n",
    "let concatenated_list = concat test_lists;;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "d7e02a29",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val drop : 'a list -> int -> 'a list = <fun>\n"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val test_list : 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 dropped_list : int list = [1; 2; 4; 5; 7; 8; 10]\n"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(* drop *)\n",
    "\n",
    "let drop list n =\n",
    "  let rec drop_helper i = function\n",
    "    | [] -> []\n",
    "    | h :: t -> if i = n then drop_helper 1 t else h :: drop_helper (i + 1) t\n",
    "  in\n",
    "  drop_helper 1 list;;\n",
    "\n",
    "let test_list = [1; 2; 3; 4; 5; 6; 7; 8; 9; 10];;\n",
    "let dropped_list = drop test_list 3;;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "d2120a6a",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val insert : 'a -> 'a list -> 'a list = <fun>\n"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val test_list : int list = [1; 3; 4; 5; 7; 9; 10]\n"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val inserted_list : int list = [1; 3; 4; 5; 6; 7; 9; 10]\n"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(* insert -> insert an element into a sorted list at the correct position to maintain sorted order *)\n",
    "\n",
    "let rec insert x = function\n",
    "  | [] -> [x]\n",
    "  | h :: t as l -> if x <= h then x :: l else h :: insert x t;;\n",
    "\n",
    "let test_list = [1; 3; 4; 5; 7; 9; 10];;\n",
    "let inserted_list = insert 6 test_list;;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "b35b49f1",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val last : 'a list -> 'a option = <fun>\n"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val test_list : int list = [1; 2; 3; 4; 5; 6]\n"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Number of height-balanced binary trees of height 3: 15\n",
      "The last element of the list is: 6\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "- : unit = ()\n"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(* last *)\n",
    "\n",
    "let rec last = function\n",
    "  | [] -> None\n",
    "  | [x] -> Some x\n",
    "  | _ :: t -> last t;;\n",
    "\n",
    "let test_list = [1; 2; 3; 4; 5; 6];;\n",
    "let last_element = last test_list in\n",
    "\n",
    "match last_element with\n",
    "  | None -> Printf.printf \"The list is empty.\\n\"\n",
    "  | Some x -> Printf.printf \"The last element of the list is: %d\\n\" x;\n",
    "flush stdout;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "d5e8f6c0",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val length : 'a list -> int = <fun>\n"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val test_list : int list = [1; 2; 3; 4; 5; 6]\n"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val list_length : int = 6\n"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(* length *)\n",
    "\n",
    "let rec length = function\n",
    "  | [] -> 0\n",
    "  | _ :: t -> 1 + length t;;\n",
    "\n",
    "let test_list = [1; 2; 3; 4; 5; 6];;\n",
    "let list_length = length test_list;;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "23b0daab",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val reverse : 'a list -> 'a list = <fun>\n"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val test_list : int list = [1; 2; 3; 4; 5; 6]\n"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val reversed_list : int list = [6; 5; 4; 3; 2; 1]\n"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(* reverse *)\n",
    "\n",
    "let reverse list =\n",
    "  let rec rev acc = function\n",
    "    | [] -> acc\n",
    "    | h :: t -> rev (h :: acc) t\n",
    "  in\n",
    "  rev [] list;;\n",
    "\n",
    "let test_list = [1; 2; 3; 4; 5; 6];;\n",
    "let reversed_list = reverse test_list;;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "9ff6554d",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val stutter : 'a list -> 'a list = <fun>\n"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val test_list : int list = [1; 2; 3; 4; 5]\n"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val stuttered_list : int list = [1; 1; 2; 2; 3; 3; 4; 4; 5; 5]\n"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(* stutter *)\n",
    "\n",
    "let rec stutter = function\n",
    "  | [] -> []\n",
    "  | h :: t -> h :: h :: stutter t;;\n",
    "\n",
    "let test_list = [1; 2; 3; 4; 5];;\n",
    "let stuttered_list = stutter test_list;;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "48664626",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val sum : int list -> int = <fun>\n"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val test_list : int list = [1; 2; 3; 4; 5]\n"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val list_sum : int = 15\n"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(* sum *)\n",
    "\n",
    "let rec sum = function\n",
    "  | [] -> 0\n",
    "  | h :: t -> h + sum t;;\n",
    "\n",
    "let test_list = [1; 2; 3; 4; 5];;\n",
    "let list_sum = sum test_list;;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "e1452e57",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val take : int -> 'a list -> 'a list = <fun>\n"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val test_list : int list = [1; 2; 3; 4; 5; 6]\n"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val taken_elements : int list = [1; 2; 3]\n"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(* take *)\n",
    "\n",
    "let rec take n = function\n",
    "  | [] -> []\n",
    "  | h :: t -> if n = 0 then [] else h :: take (n-1) t;;\n",
    "\n",
    "let test_list = [1; 2; 3; 4; 5; 6];;\n",
    "let taken_elements = take 3 test_list;;"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cfcfb372",
   "metadata": {},
   "source": [
    "## Integer Programs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "cc79a884",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val fib : int -> int = <fun>\n"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val fib_10 : int = 55\n"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(* fib *)\n",
    "\n",
    "let rec fib = function\n",
    "  | 0 -> 0\n",
    "  | 1 -> 1\n",
    "  | n -> fib (n-1) + fib (n-2);;\n",
    "\n",
    "let fib_10 = fib 10;;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "ebd17e99",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val gcd : int -> int -> int = <fun>\n"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val gcd_value : int = 6\n"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(* gcd *)\n",
    "\n",
    "let rec gcd a b =\n",
    "  if b = 0 then a else gcd b (a mod b);;\n",
    "\n",
    "let gcd_value = gcd 48 18;;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "2dbfb769",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val iseven : int -> bool = <fun>\n"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val is_4_even : bool = true\n"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val is_5_even : bool = false\n"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(* iseven *)\n",
    "\n",
    "let iseven n = n mod 2 = 0;;\n",
    "\n",
    "let is_4_even = iseven 4;;\n",
    "let is_5_even = iseven 5;;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "ec0d9b53",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val isodd : int -> bool = <fun>\n"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val is_4_odd : bool = false\n"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val is_5_odd : bool = true\n"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(* isodd *)\n",
    "\n",
    "let isodd n = n mod 2 <> 0;;\n",
    "\n",
    "let is_4_odd = isodd 4;;\n",
    "let is_5_odd = isodd 5;;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "id": "7ca49683",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val modulo : int -> int -> int = <fun>\n"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val mod_value : int = 1\n"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(* modulo *)\n",
    "\n",
    "let modulo a b = a mod b;;\n",
    "\n",
    "let mod_value = modulo 10 3;;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "id": "6eb72432",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val mult : int -> int -> int = <fun>\n"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val mult_value : int = 30\n"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(* mult *)\n",
    "\n",
    "let mult a b = a * b;;\n",
    "\n",
    "let mult_value = mult 10 3;;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "id": "e677e27f",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val square : int -> int = <fun>\n"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val square_4 : int = 16\n"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val square_5 : int = 25\n"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(* square *)\n",
    "\n",
    "let square n = n * n;;\n",
    "\n",
    "let square_4 = square 4;;\n",
    "let square_5 = square 5;;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "id": "f4ff23ad",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val sum_under : int -> int = <fun>\n"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val sum_5 : int = 15\n"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(* sum_under -> function that takes a number n and returns the sum of all integers from 1 to n *)\n",
    "\n",
    "let rec sum_under n =\n",
    "  if n <= 0 then 0 else n + sum_under (n - 1);;\n",
    "\n",
    "let sum_5 = sum_under 5;;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "deb203e7",
   "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
}