ocaml-programming

exercises_unit_1.ipynb (40808B)

---

 {
  "cells": [
   {
    "cell_type": "code",
    "execution_count": 1,
    "id": "e3d34281-2d39-48ec-8bc3-a257d071bd82",
    "metadata": {},
    "outputs": [
     {
      "data": {
       "text/plain": [
        "- : int = 0\n"
       ]
      },
      "execution_count": 1,
      "metadata": {},
      "output_type": "execute_result"
     }
    ],
    "source": [
     "Sys.command \"opam install -y qcheck > /tmp/opam.log 2>&1\";;"
    ]
   },
   {
    "cell_type": "code",
    "execution_count": 2,
    "id": "3fc0418a-4ca6-475a-b32a-7faa5527fbae",
    "metadata": {},
    "outputs": [
     {
      "data": {
       "text/plain": [
        "val cube : int -> int = <fun>\n"
       ]
      },
      "execution_count": 2,
      "metadata": {},
      "output_type": "execute_result"
     }
    ],
    "source": [
     "let cube n = n*n*n"
    ]
   },
   {
    "cell_type": "code",
    "execution_count": 3,
    "id": "a4db5988-0b39-4b2d-8bc9-952b16d54ad0",
    "metadata": {},
    "outputs": [
     {
      "data": {
       "text/plain": [
        "val fahrenheit_of_celsius : float -> float = <fun>\n"
       ]
      },
      "execution_count": 3,
      "metadata": {},
      "output_type": "execute_result"
     }
    ],
    "source": [
     "let fahrenheit_of_celsius (c : float) = (c *. (9. /. 5.)) +. 32."
    ]
   },
   {
    "cell_type": "code",
    "execution_count": 4,
    "id": "4dc8ee72-86ad-49dc-8d87-f11f129ea38d",
    "metadata": {},
    "outputs": [
     {
      "data": {
       "text/plain": [
        "- : float = 41.\n"
       ]
      },
      "execution_count": 4,
      "metadata": {},
      "output_type": "execute_result"
     }
    ],
    "source": [
     "fahrenheit_of_celsius 5."
    ]
   },
   {
    "cell_type": "code",
    "execution_count": 5,
    "id": "5b3adb38-ed81-4b18-abeb-97790f1bfee7",
    "metadata": {},
    "outputs": [],
    "source": [
     " (*  `sign n` returns -1 if n is negative, 0 if zero, 1 if positive.\n",
     "   Use nested if/then/else expressions and notice that every branch must\n",
     "   produce an int.\n",
     "*)"
    ]
   },
   {
    "cell_type": "code",
    "execution_count": 6,
    "id": "4ced9283-2066-4f6e-b14b-555a0271fb1b",
    "metadata": {},
    "outputs": [
     {
      "data": {
       "text/plain": [
        "val sign : int -> int = <fun>\n"
       ]
      },
      "execution_count": 6,
      "metadata": {},
      "output_type": "execute_result"
     }
    ],
    "source": [
     "let sign n = if n < 0 then -1\n",
     "    else if n = 0\n",
     "        then 0\n",
     "        else 1"
    ]
   },
   {
    "cell_type": "code",
    "execution_count": 7,
    "id": "4a78286a-4406-42f8-a103-1558a7b98e7c",
    "metadata": {},
    "outputs": [
     {
      "data": {
       "text/plain": [
        "- : int = 0\n"
       ]
      },
      "execution_count": 7,
      "metadata": {},
      "output_type": "execute_result"
     },
     {
      "data": {
       "text/plain": [
        "- : int = -1\n"
       ]
      },
      "execution_count": 7,
      "metadata": {},
      "output_type": "execute_result"
     },
     {
      "data": {
       "text/plain": [
        "- : int = 1\n"
       ]
      },
      "execution_count": 7,
      "metadata": {},
      "output_type": "execute_result"
     },
     {
      "data": {
       "text/plain": [
        "- : int = -1\n"
       ]
      },
      "execution_count": 7,
      "metadata": {},
      "output_type": "execute_result"
     },
     {
      "data": {
       "text/plain": [
        "- : int = 1\n"
       ]
      },
      "execution_count": 7,
      "metadata": {},
      "output_type": "execute_result"
     }
    ],
    "source": [
     "sign 0;;\n",
     "sign (-1);;\n",
     "sign 1;;\n",
     "sign (-1000);;\n",
     "sign 100000;;"
    ]
   },
   {
    "cell_type": "code",
    "execution_count": 8,
    "id": "ad9ac3d1-1f21-4764-95ad-06706a5043ab",
    "metadata": {},
    "outputs": [
     {
      "data": {
       "text/plain": [
        "val fib : int -> int = <fun>\n"
       ]
      },
      "execution_count": 8,
      "metadata": {},
      "output_type": "execute_result"
     }
    ],
    "source": [
     "let rec fib n = if n <= 1 then n else fib (n - 1) + fib (n - 2)\n"
    ]
   },
   {
    "cell_type": "code",
    "execution_count": 9,
    "id": "32f0fbe4-4a4a-44d5-9f71-4affc1bdec98",
    "metadata": {},
    "outputs": [
     {
      "data": {
       "text/plain": [
        "- : int = 0\n"
       ]
      },
      "execution_count": 9,
      "metadata": {},
      "output_type": "execute_result"
     },
     {
      "data": {
       "text/plain": [
        "- : int = 1\n"
       ]
      },
      "execution_count": 9,
      "metadata": {},
      "output_type": "execute_result"
     },
     {
      "data": {
       "text/plain": [
        "- : int = 1\n"
       ]
      },
      "execution_count": 9,
      "metadata": {},
      "output_type": "execute_result"
     },
     {
      "data": {
       "text/plain": [
        "- : int = 2\n"
       ]
      },
      "execution_count": 9,
      "metadata": {},
      "output_type": "execute_result"
     },
     {
      "data": {
       "text/plain": [
        "- : int = 3\n"
       ]
      },
      "execution_count": 9,
      "metadata": {},
      "output_type": "execute_result"
     }
    ],
    "source": [
     "fib 0;;\n",
     "fib 1;;\n",
     "fib 2;;\n",
     "fib 3;;\n",
     "fib 4;;"
    ]
   },
   {
    "cell_type": "code",
    "execution_count": 10,
    "id": "8808ba7e-f3ec-4f10-bd90-56c784c01f72",
    "metadata": {},
    "outputs": [
     {
      "data": {
       "text/plain": [
        "- : bool = true\n"
       ]
      },
      "execution_count": 10,
      "metadata": {},
      "output_type": "execute_result"
     },
     {
      "data": {
       "text/plain": [
        "- : bool = false\n"
       ]
      },
      "execution_count": 10,
      "metadata": {},
      "output_type": "execute_result"
     }
    ],
    "source": [
     "1.0 = 1.0;;\n",
     "1.0 == 1.0;;"
    ]
   },
   {
    "cell_type": "code",
    "execution_count": 11,
    "id": "be0aa1f3-2f8a-4ccb-93bd-5889ccb19fd1",
    "metadata": {},
    "outputs": [],
    "source": [
     "(* count digits non-tail recursive *)"
    ]
   },
   {
    "cell_type": "code",
    "execution_count": 12,
    "id": "0143fdea-b247-4af2-9311-6bcd955d6160",
    "metadata": {},
    "outputs": [
     {
      "data": {
       "text/plain": [
        "val count_digits : int -> int = <fun>\n"
       ]
      },
      "execution_count": 12,
      "metadata": {},
      "output_type": "execute_result"
     }
    ],
    "source": [
     "let rec count_digits n = if n < 0 then count_digits (n * (-1))\n",
     "    else if n > 9 \n",
     "        then count_digits (n / 10) + 1\n",
     "        else 1"
    ]
   },
   {
    "cell_type": "code",
    "execution_count": 13,
    "id": "319f2854-0d2d-466a-8e12-80cd5c14b5a0",
    "metadata": {},
    "outputs": [
     {
      "data": {
       "text/plain": [
        "- : int = 1\n"
       ]
      },
      "execution_count": 13,
      "metadata": {},
      "output_type": "execute_result"
     },
     {
      "data": {
       "text/plain": [
        "- : int = 3\n"
       ]
      },
      "execution_count": 13,
      "metadata": {},
      "output_type": "execute_result"
     },
     {
      "data": {
       "text/plain": [
        "- : int = 2\n"
       ]
      },
      "execution_count": 13,
      "metadata": {},
      "output_type": "execute_result"
     },
     {
      "data": {
       "text/plain": [
        "- : int = 1\n"
       ]
      },
      "execution_count": 13,
      "metadata": {},
      "output_type": "execute_result"
     },
     {
      "data": {
       "text/plain": [
        "- : int = 3\n"
       ]
      },
      "execution_count": 13,
      "metadata": {},
      "output_type": "execute_result"
     },
     {
      "data": {
       "text/plain": [
        "- : int = 4\n"
       ]
      },
      "execution_count": 13,
      "metadata": {},
      "output_type": "execute_result"
     },
     {
      "data": {
       "text/plain": [
        "- : int = 1\n"
       ]
      },
      "execution_count": 13,
      "metadata": {},
      "output_type": "execute_result"
     }
    ],
    "source": [
     "count_digits 0;;\n",
     "count_digits 100;;\n",
     "count_digits 10;;\n",
     "count_digits 9;;\n",
     "count_digits (-102);;\n",
     "count_digits (-1002);;\n",
     "count_digits (-1);;"
    ]
   },
   {
    "cell_type": "code",
    "execution_count": 14,
    "id": "a2ec41ef-f24f-485a-9ee6-ab04fcbe301a",
    "metadata": {},
    "outputs": [],
    "source": [
     "(* count digits tail recursive *)"
    ]
   },
   {
    "cell_type": "code",
    "execution_count": 15,
    "id": "880519a5-6abe-4622-9d00-cd8d6f7a0b71",
    "metadata": {},
    "outputs": [
     {
      "data": {
       "text/plain": [
        "val cnt : int -> int -> int = <fun>\n"
       ]
      },
      "execution_count": 15,
      "metadata": {},
      "output_type": "execute_result"
     },
     {
      "data": {
       "text/plain": [
        "val count_digits : int -> int = <fun>\n"
       ]
      },
      "execution_count": 15,
      "metadata": {},
      "output_type": "execute_result"
     }
    ],
    "source": [
     "let rec cnt acc n = \n",
     "    if n < 0 then cnt 0 (n * (-1))\n",
     "    else if n > 9 \n",
     "        then cnt (acc + 1) (n / 10)\n",
     "        else (acc + 1)\n",
     "\n",
     "let count_digits = cnt 0"
    ]
   },
   {
    "cell_type": "code",
    "execution_count": 16,
    "id": "63a70c83-ff18-4d95-82e2-89d4b1b05d95",
    "metadata": {},
    "outputs": [
     {
      "data": {
       "text/plain": [
        "- : int = 1\n"
       ]
      },
      "execution_count": 16,
      "metadata": {},
      "output_type": "execute_result"
     },
     {
      "data": {
       "text/plain": [
        "- : int = 3\n"
       ]
      },
      "execution_count": 16,
      "metadata": {},
      "output_type": "execute_result"
     },
     {
      "data": {
       "text/plain": [
        "- : int = 2\n"
       ]
      },
      "execution_count": 16,
      "metadata": {},
      "output_type": "execute_result"
     },
     {
      "data": {
       "text/plain": [
        "- : int = 1\n"
       ]
      },
      "execution_count": 16,
      "metadata": {},
      "output_type": "execute_result"
     },
     {
      "data": {
       "text/plain": [
        "- : int = 3\n"
       ]
      },
      "execution_count": 16,
      "metadata": {},
      "output_type": "execute_result"
     },
     {
      "data": {
       "text/plain": [
        "- : int = 4\n"
       ]
      },
      "execution_count": 16,
      "metadata": {},
      "output_type": "execute_result"
     },
     {
      "data": {
       "text/plain": [
        "- : int = 1\n"
       ]
      },
      "execution_count": 16,
      "metadata": {},
      "output_type": "execute_result"
     }
    ],
    "source": [
     "count_digits 0;;\n",
     "count_digits 100;;\n",
     "count_digits 10;;\n",
     "count_digits 9;;\n",
     "count_digits (-102);;\n",
     "count_digits (-1002);;\n",
     "count_digits (-1);;"
    ]
   },
   {
    "cell_type": "code",
    "execution_count": 17,
    "id": "581edd75-6dac-4cc3-937c-e16797b9fd9e",
    "metadata": {},
    "outputs": [],
    "source": [
     " (*  `fib_fast n` computes the same thing but must be *tail recursive* and run\n",
     "   in linear time. Use an inner `let rec go ... in` helper carrying two\n",
     "   accumulators (the previous two Fibonacci numbers).\n",
     "   It must handle fib_fast 1_000_000 without overflowing the stack (the\n",
     "   number itself will wrap around, that is fine, we only care about space). *)"
    ]
   },
   {
    "cell_type": "code",
    "execution_count": 18,
    "id": "01137212-a52f-4100-9398-989af9a70387",
    "metadata": {},
    "outputs": [
     {
      "data": {
       "text/plain": [
        "val fib_fast : int -> int = <fun>\n"
       ]
      },
      "execution_count": 18,
      "metadata": {},
      "output_type": "execute_result"
     }
    ],
    "source": [
     "let fib_fast m = \n",
     "    let rec go n min_one min_two  = \n",
     "        if n >= m\n",
     "            then \n",
     "                if n = 1 then m\n",
     "                else min_one + min_two\n",
     "            else go (n + 1) min_two (min_one + min_two) in\n",
     "    go 1 1 0"
    ]
   },
   {
    "cell_type": "code",
    "execution_count": 19,
    "id": "7286b831-9e71-4861-b062-ede92b0405aa",
    "metadata": {},
    "outputs": [
     {
      "data": {
       "text/plain": [
        "- : int = 0\n"
       ]
      },
      "execution_count": 19,
      "metadata": {},
      "output_type": "execute_result"
     },
     {
      "data": {
       "text/plain": [
        "- : int = 1\n"
       ]
      },
      "execution_count": 19,
      "metadata": {},
      "output_type": "execute_result"
     },
     {
      "data": {
       "text/plain": [
        "- : int = 1\n"
       ]
      },
      "execution_count": 19,
      "metadata": {},
      "output_type": "execute_result"
     },
     {
      "data": {
       "text/plain": [
        "- : int = 2\n"
       ]
      },
      "execution_count": 19,
      "metadata": {},
      "output_type": "execute_result"
     },
     {
      "data": {
       "text/plain": [
        "- : int = 3\n"
       ]
      },
      "execution_count": 19,
      "metadata": {},
      "output_type": "execute_result"
     },
     {
      "data": {
       "text/plain": [
        "- : int = 5\n"
       ]
      },
      "execution_count": 19,
      "metadata": {},
      "output_type": "execute_result"
     },
     {
      "data": {
       "text/plain": [
        "- : int = 8\n"
       ]
      },
      "execution_count": 19,
      "metadata": {},
      "output_type": "execute_result"
     },
     {
      "data": {
       "text/plain": [
        "- : int = 13\n"
       ]
      },
      "execution_count": 19,
      "metadata": {},
      "output_type": "execute_result"
     },
     {
      "data": {
       "text/plain": [
        "- : int = 21\n"
       ]
      },
      "execution_count": 19,
      "metadata": {},
      "output_type": "execute_result"
     },
     {
      "data": {
       "text/plain": [
        "- : int = 34\n"
       ]
      },
      "execution_count": 19,
      "metadata": {},
      "output_type": "execute_result"
     },
     {
      "data": {
       "text/plain": [
        "- : int = 55\n"
       ]
      },
      "execution_count": 19,
      "metadata": {},
      "output_type": "execute_result"
     }
    ],
    "source": [
     "fib_fast 0;;\n",
     "fib_fast 1;;\n",
     "fib_fast 2;;\n",
     "fib_fast 3;;\n",
     "fib_fast 4;;\n",
     "fib_fast 5;;\n",
     "fib_fast 6;;\n",
     "fib_fast 7;;\n",
     "fib_fast 8;;\n",
     "fib_fast 9;;\n",
     "fib_fast 10;;"
    ]
   },
   {
    "cell_type": "code",
    "execution_count": 20,
    "id": "c3ebcf22-4a49-48a8-8fb7-b9635c305647",
    "metadata": {},
    "outputs": [
     {
      "data": {
       "text/plain": [
        "val power : int -> int -> int = <fun>\n"
       ]
      },
      "execution_count": 20,
      "metadata": {},
      "output_type": "execute_result"
     }
    ],
    "source": [
     "let power base exp = \n",
     "    let rec go acc exp = \n",
     "        if exp <= 0\n",
     "            then acc\n",
     "            else go (acc * base) (exp - 1) in\n",
     "        go 1 exp"
    ]
   },
   {
    "cell_type": "code",
    "execution_count": 21,
    "id": "5aa3f86f-5cc4-43ef-ba1b-ce7395c5fd45",
    "metadata": {},
    "outputs": [
     {
      "data": {
       "text/plain": [
        "- : int = 1\n"
       ]
      },
      "execution_count": 21,
      "metadata": {},
      "output_type": "execute_result"
     },
     {
      "data": {
       "text/plain": [
        "- : int = 2\n"
       ]
      },
      "execution_count": 21,
      "metadata": {},
      "output_type": "execute_result"
     },
     {
      "data": {
       "text/plain": [
        "- : int = 4\n"
       ]
      },
      "execution_count": 21,
      "metadata": {},
      "output_type": "execute_result"
     },
     {
      "data": {
       "text/plain": [
        "- : int = 8\n"
       ]
      },
      "execution_count": 21,
      "metadata": {},
      "output_type": "execute_result"
     },
     {
      "data": {
       "text/plain": [
        "- : int = 9\n"
       ]
      },
      "execution_count": 21,
      "metadata": {},
      "output_type": "execute_result"
     }
    ],
    "source": [
     "power 2 0;;\n",
     "power 2 1;;\n",
     "power 2 2;;\n",
     "power 2 3;;\n",
     "power 3 2;;"
    ]
   },
   {
    "cell_type": "code",
    "execution_count": 22,
    "id": "3ab5d14e-6518-4ecf-a4a7-a19902ca49ec",
    "metadata": {},
    "outputs": [],
    "source": [
     "(*   `compose f g` returns the function that applies g first, then f.\n",
     "   Write no type annotation. The inferred type should be\n",
     "     ('a -> 'b) -> ('c -> 'a) -> 'c -> 'b\n",
     "   which is your first taste of polymorphism falling out of inference. *)"
    ]
   },
   {
    "cell_type": "code",
    "execution_count": 23,
    "id": "69f16a49-d963-4f27-96ea-6180931a3ea9",
    "metadata": {},
    "outputs": [
     {
      "data": {
       "text/plain": [
        "val compose : ('a -> 'b) -> ('c -> 'a) -> 'c -> 'b = <fun>\n"
       ]
      },
      "execution_count": 23,
      "metadata": {},
      "output_type": "execute_result"
     }
    ],
    "source": [
     "let compose f g = fun x -> f (g x);;"
    ]
   },
   {
    "cell_type": "code",
    "execution_count": 24,
    "id": "e6a0ad52-5b27-4384-9d3e-c320eace2da2",
    "metadata": {},
    "outputs": [
     {
      "data": {
       "text/plain": [
        "- : int = 13\n"
       ]
      },
      "execution_count": 24,
      "metadata": {},
      "output_type": "execute_result"
     }
    ],
    "source": [
     "compose succ (( * ) 3) 4    (* = 13 *)"
    ]
   },
   {
    "cell_type": "code",
    "execution_count": 25,
    "id": "578a49bd-e885-4107-8cc7-553dc5c70a79",
    "metadata": {},
    "outputs": [
     {
      "data": {
       "text/plain": [
        "val gcd : int -> int -> int = <fun>\n"
       ]
      },
      "execution_count": 25,
      "metadata": {},
      "output_type": "execute_result"
     }
    ],
    "source": [
     "let rec gcd a b = \n",
     "    if b = 0 then a\n",
     "    else gcd b (a mod b)"
    ]
   },
   {
    "cell_type": "code",
    "execution_count": 26,
    "id": "dfce273a-8c44-49c0-9011-6db991bec36f",
    "metadata": {},
    "outputs": [
     {
      "data": {
       "text/plain": [
        "- : int = 6\n"
       ]
      },
      "execution_count": 26,
      "metadata": {},
      "output_type": "execute_result"
     },
     {
      "data": {
       "text/plain": [
        "- : int = 6\n"
       ]
      },
      "execution_count": 26,
      "metadata": {},
      "output_type": "execute_result"
     },
     {
      "data": {
       "text/plain": [
        "- : int = 1\n"
       ]
      },
      "execution_count": 26,
      "metadata": {},
      "output_type": "execute_result"
     },
     {
      "data": {
       "text/plain": [
        "- : int = 5\n"
       ]
      },
      "execution_count": 26,
      "metadata": {},
      "output_type": "execute_result"
     }
    ],
    "source": [
     "gcd 12 18;;\n",
     "gcd 270 192;;\n",
     "gcd 17 15;;\n",
     "gcd 0 5;;"
    ]
   },
   {
    "cell_type": "code",
    "execution_count": 27,
    "id": "71305179-f9ac-4684-8490-ba55e1aa5b96",
    "metadata": {},
    "outputs": [],
    "source": [
     "(* --- 17 ------------------------------------------------------------------\n",
     "   `repeat f n x` applies f to x exactly n times: repeat f 3 x = f (f (f x)).\n",
     "   repeat f 0 x = x. Must work for any type, so again no annotations.\n",
     "   This is your accumulator pattern with a *function* as the thing being\n",
     "   applied. *)"
    ]
   },
   {
    "cell_type": "code",
    "execution_count": 28,
    "id": "068252f8-1ae0-4bce-8c73-e1da077b268b",
    "metadata": {},
    "outputs": [
     {
      "data": {
       "text/plain": [
        "val repeat : ('a -> 'a) -> int -> 'a -> 'a = <fun>\n"
       ]
      },
      "execution_count": 28,
      "metadata": {},
      "output_type": "execute_result"
     }
    ],
    "source": [
     "let rec repeat f n x = \n",
     "    if n = 0\n",
     "        then x\n",
     "        else repeat f (n - 1) (f x)"
    ]
   },
   {
    "cell_type": "code",
    "execution_count": 29,
    "id": "cf8b242f-0a0b-4169-af6e-74370bbda435",
    "metadata": {},
    "outputs": [
     {
      "data": {
       "text/plain": [
        "val add_5 : int -> int = <fun>\n"
       ]
      },
      "execution_count": 29,
      "metadata": {},
      "output_type": "execute_result"
     },
     {
      "data": {
       "text/plain": [
        "- : int = 52\n"
       ]
      },
      "execution_count": 29,
      "metadata": {},
      "output_type": "execute_result"
     }
    ],
    "source": [
     "let add_5 x = x + 5;;\n",
     "\n",
     "repeat add_5 10 2;;"
    ]
   },
   {
    "cell_type": "code",
    "execution_count": 30,
    "id": "5b4f9d85-d6d6-4b9f-8bef-067b9df432cd",
    "metadata": {},
    "outputs": [],
    "source": [
     "(* --- 10 ------------------------------------------------------------------\n",
     "   NEW IDEA: an accumulator that *builds a value* rather than counting one.\n",
     "\n",
     "   `reverse_int n` reverses the decimal digits of n, for n >= 0. Leading\n",
     "   zeros simply disappear, since the result is a number, not text.\n",
     "\n",
     "       reverse_int 1234 = 4321    reverse_int 1200 = 21\n",
     "       reverse_int 7 = 7          reverse_int 0 = 0\n",
     "\n",
     "   Tail recursive. Each step peels one digit off n with `mod 10` and pushes\n",
     "   it onto the accumulator. Pushing a digit onto a number is the arithmetic\n",
     "   you have to work out.\n",
     "\n",
     "   Once this works, note that `reverse_int n = n` is a palindrome test. *)"
    ]
   },
   {
    "cell_type": "code",
    "execution_count": 31,
    "id": "12e04876-a113-4f9c-8ab5-b1c0065f058a",
    "metadata": {},
    "outputs": [
     {
      "data": {
       "text/plain": [
        "val reverse_int : int -> int = <fun>\n"
       ]
      },
      "execution_count": 31,
      "metadata": {},
      "output_type": "execute_result"
     }
    ],
    "source": [
     "let reverse_int n = \n",
     "    let rec go ret_val running =\n",
     "        if running = 0\n",
     "            then ret_val\n",
     "        else\n",
     "            go (ret_val * 10 + ((running mod 10))) (running / 10)\n",
     "        in\n",
     "    go 0 n"
    ]
   },
   {
    "cell_type": "code",
    "execution_count": 32,
    "id": "6bf2e53b-922f-4beb-a3d7-0e3b27887e7e",
    "metadata": {},
    "outputs": [
     {
      "data": {
       "text/plain": [
        "- : int = 7\n"
       ]
      },
      "execution_count": 32,
      "metadata": {},
      "output_type": "execute_result"
     },
     {
      "data": {
       "text/plain": [
        "- : int = 4321\n"
       ]
      },
      "execution_count": 32,
      "metadata": {},
      "output_type": "execute_result"
     },
     {
      "data": {
       "text/plain": [
        "- : int = 21\n"
       ]
      },
      "execution_count": 32,
      "metadata": {},
      "output_type": "execute_result"
     },
     {
      "data": {
       "text/plain": [
        "- : int = 0\n"
       ]
      },
      "execution_count": 32,
      "metadata": {},
      "output_type": "execute_result"
     },
     {
      "data": {
       "text/plain": [
        "- : int = 921\n"
       ]
      },
      "execution_count": 32,
      "metadata": {},
      "output_type": "execute_result"
     }
    ],
    "source": [
     "reverse_int 700;;\n",
     "reverse_int 1234;;\n",
     "reverse_int 1200;;\n",
     "reverse_int 0;;\n",
     "reverse_int 1290;;"
    ]
   },
   {
    "cell_type": "code",
    "execution_count": 33,
    "id": "36ad5f0c-0db0-4297-b7dc-92038a2d50f7",
    "metadata": {},
    "outputs": [
     {
      "data": {
       "text/plain": [
        "- : int = 11\n"
       ]
      },
      "execution_count": 33,
      "metadata": {},
      "output_type": "execute_result"
     }
    ],
    "source": [
     "let x = 5 in ((let x = 6 in x) + x)"
    ]
   },
   {
    "cell_type": "code",
    "execution_count": 34,
    "id": "3692ddcf-fc68-4657-9a46-991ab5d0f10d",
    "metadata": {},
    "outputs": [
     {
      "data": {
       "text/plain": [
        "- : int = 2\n"
       ]
      },
      "execution_count": 34,
      "metadata": {},
      "output_type": "execute_result"
     }
    ],
    "source": [
     "(fun x -> x + 1) 1;;"
    ]
   },
   {
    "cell_type": "code",
    "execution_count": 35,
    "id": "8d938958-ba4f-481a-9b48-08d81d75bd78",
    "metadata": {},
    "outputs": [
     {
      "data": {
       "text/plain": [
        "val add_2 : int -> int = <fun>\n"
       ]
      },
      "execution_count": 35,
      "metadata": {},
      "output_type": "execute_result"
     },
     {
      "data": {
       "text/plain": [
        "val sub_1 : int -> int = <fun>\n"
       ]
      },
      "execution_count": 35,
      "metadata": {},
      "output_type": "execute_result"
     },
     {
      "data": {
       "text/plain": [
        "val mul_2 : int -> int = <fun>\n"
       ]
      },
      "execution_count": 35,
      "metadata": {},
      "output_type": "execute_result"
     },
     {
      "data": {
       "text/plain": [
        "- : int = 6\n"
       ]
      },
      "execution_count": 35,
      "metadata": {},
      "output_type": "execute_result"
     }
    ],
    "source": [
     "let add_2 x = x + 2;;\n",
     "let sub_1 x = x - 1;;\n",
     "let mul_2 x = x * 2;;\n",
     "\n",
     "mul_2 (sub_1 (add_2 2));; \n",
     "\n",
     "(* Parenthesis needed above. *)"
    ]
   },
   {
    "cell_type": "code",
    "execution_count": 36,
    "id": "6b097ffd-fb7d-4694-b61a-9c7105c632e1",
    "metadata": {},
    "outputs": [],
    "source": [
     "(* 13\n",
     "\n",
     "NEW IDEA: the shape of the recursion changes the complexity class.\n",
     "\n",
     "power in 8 does exp multiplications. power_fast must do about log2(exp) of\n",
     "them, by squaring:\n",
     "\n",
     "    b^e = (b*b)^(e/2)          when e is even\n",
     "    b^e = b * (b*b)^(e/2)      when e is odd, using integer division\n",
     "\n",
     "Each step halves the exponent instead of decrementing it. Tail recursive, so\n",
     "carry the collected-so-far factor in an accumulator.\n",
     "\n",
     "power_fast 2 10 = 1024, power_fast 3 5 = 243, power_fast 7 0 = 1,\n",
     "power_fast 2 61 = 2305843009213693952.\n",
     "\n",
     "Then try power_fast 2 1_000_000_000. A linear version would still be running\n",
     "tomorrow; a logarithmic one finishes instantly. That difference is the test.\n",
     "\n",
     "*)"
    ]
   },
   {
    "cell_type": "code",
    "execution_count": 37,
    "id": "16b79160-9c4c-414f-9e06-475b088d02a4",
    "metadata": {},
    "outputs": [
     {
      "data": {
       "text/plain": [
        "val power_fast : int -> int -> int = <fun>\n"
       ]
      },
      "execution_count": 37,
      "metadata": {},
      "output_type": "execute_result"
     }
    ],
    "source": [
     "let power_fast base exp = \n",
     "    let rec go acc base exp =\n",
     "        if exp = 0\n",
     "            then\n",
     "                acc   \n",
     "            else\n",
     "                if exp mod 2 = 0\n",
     "                     then\n",
     "                        go acc (base * base) (exp / 2)\n",
     "                    else\n",
     "                        go (acc * base) (base * base) ((exp - 1) / 2)\n",
     "    in go 1 base exp\n",
     "        "
    ]
   },
   {
    "cell_type": "code",
    "execution_count": 38,
    "id": "2ebe0d8f-7740-440e-8dfb-51d851f91de9",
    "metadata": {},
    "outputs": [
     {
      "data": {
       "text/plain": [
        "- : int = 3125\n"
       ]
      },
      "execution_count": 38,
      "metadata": {},
      "output_type": "execute_result"
     },
     {
      "data": {
       "text/plain": [
        "- : int = 25\n"
       ]
      },
      "execution_count": 38,
      "metadata": {},
      "output_type": "execute_result"
     },
     {
      "data": {
       "text/plain": [
        "- : int = 1\n"
       ]
      },
      "execution_count": 38,
      "metadata": {},
      "output_type": "execute_result"
     },
     {
      "data": {
       "text/plain": [
        "- : int = 5\n"
       ]
      },
      "execution_count": 38,
      "metadata": {},
      "output_type": "execute_result"
     },
     {
      "data": {
       "text/plain": [
        "- : int = 1\n"
       ]
      },
      "execution_count": 38,
      "metadata": {},
      "output_type": "execute_result"
     },
     {
      "data": {
       "text/plain": [
        "- : int = 2\n"
       ]
      },
      "execution_count": 38,
      "metadata": {},
      "output_type": "execute_result"
     },
     {
      "data": {
       "text/plain": [
        "- : int = 4\n"
       ]
      },
      "execution_count": 38,
      "metadata": {},
      "output_type": "execute_result"
     },
     {
      "data": {
       "text/plain": [
        "- : int = 243\n"
       ]
      },
      "execution_count": 38,
      "metadata": {},
      "output_type": "execute_result"
     },
     {
      "data": {
       "text/plain": [
        "- : int = 243\n"
       ]
      },
      "execution_count": 38,
      "metadata": {},
      "output_type": "execute_result"
     },
     {
      "data": {
       "text/plain": [
        "- : int = 81\n"
       ]
      },
      "execution_count": 38,
      "metadata": {},
      "output_type": "execute_result"
     },
     {
      "data": {
       "text/plain": [
        "- : int = 243\n"
       ]
      },
      "execution_count": 38,
      "metadata": {},
      "output_type": "execute_result"
     }
    ],
    "source": [
     "power_fast 5 5;;\n",
     "power_fast 5 2;;\n",
     "power_fast 5 0;;\n",
     "power_fast 5 1;;\n",
     "\n",
     "power_fast 2 0;;\n",
     "power_fast 2 1;;\n",
     "power_fast 2 2;;\n",
     "\n",
     "power_fast 3 5;;\n",
     "\n",
     "27 * power_fast 3 2;;\n",
     "27 * 3;;\n",
     "81 * 3;;"
    ]
   },
   {
    "cell_type": "code",
    "execution_count": 39,
    "id": "bbe1a653-56d1-4d96-a13a-692e0d5296bf",
    "metadata": {},
    "outputs": [],
    "source": [
     "(* 12\n",
     "\n",
     "NEW IDEA: mutual recursion. Two functions that call each other are defined\n",
     "together, joined by and:\n",
     "\n",
     "    let rec f x = ... g ... and g x = ... f ...\n",
     "\n",
     "Define is_even and is_odd for n >= 0 without using mod, division, or each\n",
     "other's arithmetic, only by counting down and handing off to the other\n",
     "function. Both must be tail recursive, so is_even 1_000_000 must not overflow\n",
     "the stack.\n",
     "\n",
     "is_even 0 = true, is_odd 0 = false, is_even 7 = false, is_odd 7 = true.\n",
     "\n",
     "*)"
    ]
   },
   {
    "cell_type": "code",
    "execution_count": 40,
    "id": "71055e50-d3d3-4511-87c5-955f181dd788",
    "metadata": {},
    "outputs": [
     {
      "data": {
       "text/plain": [
        "val is_even : int -> bool = <fun>\n",
        "val is_odd : int -> bool = <fun>\n"
       ]
      },
      "execution_count": 40,
      "metadata": {},
      "output_type": "execute_result"
     }
    ],
    "source": [
     "let rec is_even n = \n",
     "    if n = 0 \n",
     "        then true\n",
     "        else is_odd (n - 1)\n",
     "and is_odd n = \n",
     "        if n = 0 \n",
     "        then false\n",
     "        else is_even (n - 1)\n",
     "(* \n",
     "This is tail recursive because no further computations are required\n",
     "once the invoked function returns to the caller\n",
     "*)"
    ]
   },
   {
    "cell_type": "code",
    "execution_count": 41,
    "id": "1d868719-1713-4448-9493-dd5e3063b242",
    "metadata": {},
    "outputs": [
     {
      "data": {
       "text/plain": [
        "- : bool = true\n"
       ]
      },
      "execution_count": 41,
      "metadata": {},
      "output_type": "execute_result"
     },
     {
      "data": {
       "text/plain": [
        "- : bool = false\n"
       ]
      },
      "execution_count": 41,
      "metadata": {},
      "output_type": "execute_result"
     },
     {
      "data": {
       "text/plain": [
        "- : bool = true\n"
       ]
      },
      "execution_count": 41,
      "metadata": {},
      "output_type": "execute_result"
     },
     {
      "data": {
       "text/plain": [
        "- : bool = false\n"
       ]
      },
      "execution_count": 41,
      "metadata": {},
      "output_type": "execute_result"
     },
     {
      "data": {
       "text/plain": [
        "- : bool = true\n"
       ]
      },
      "execution_count": 41,
      "metadata": {},
      "output_type": "execute_result"
     }
    ],
    "source": [
     "is_even 0;;\n",
     "is_even 1;;\n",
     "is_even 2;;\n",
     "is_even 3;;\n",
     "is_even 300000000;;"
    ]
   },
   {
    "cell_type": "code",
    "execution_count": 42,
    "id": "4a1fd467-9ff0-43d3-89ab-71772f42c611",
    "metadata": {},
    "outputs": [],
    "source": [
     "(* 11\n",
     "\n",
     "NEW IDEA: the accumulator can be a string.\n",
     "\n",
     "to_binary n returns the base-2 representation of n >= 0 as a string. Tail\n",
     "recursive. ^ concatenates strings and string_of_int turns a digit into one.\n",
     "Peeling with mod 2 produces the digits backwards, and the fix is a matter of\n",
     "which side you concatenate on. n = 0 needs thought, since the natural loop\n",
     "produces the empty string.\n",
     "\n",
     "to_binary 0 = \"0\", to_binary 1 = \"1\", to_binary 5 = \"101\",\n",
     "to_binary 10 = \"1010\", to_binary 255 = \"11111111\".\n",
     "\n",
     "*)"
    ]
   },
   {
    "cell_type": "code",
    "execution_count": 43,
    "id": "b337c48c-eda6-48b0-a2cb-d88436e0a39d",
    "metadata": {},
    "outputs": [
     {
      "data": {
       "text/plain": [
        "val to_binary : int -> string = <fun>\n"
       ]
      },
      "execution_count": 43,
      "metadata": {},
      "output_type": "execute_result"
     }
    ],
    "source": [
     "let to_binary n = \n",
     "    let rec go acc current =\n",
     "        if current <= 1\n",
     "            then string_of_int current ^ acc\n",
     "        else\n",
     "            if current mod 2 = 0\n",
     "                then go (\"0\" ^ acc) ((current) / 2)\n",
     "                else\n",
     "                    go (\"1\" ^ acc) ((current - 1) / 2)\n",
     "    in go \"\" n"
    ]
   },
   {
    "cell_type": "code",
    "execution_count": 44,
    "id": "5cb1a2ed-ac2b-4096-812f-eaf642455207",
    "metadata": {},
    "outputs": [
     {
      "data": {
       "text/plain": [
        "- : string = \"1010\"\n"
       ]
      },
      "execution_count": 44,
      "metadata": {},
      "output_type": "execute_result"
     },
     {
      "data": {
       "text/plain": [
        "- : string = \"10\"\n"
       ]
      },
      "execution_count": 44,
      "metadata": {},
      "output_type": "execute_result"
     },
     {
      "data": {
       "text/plain": [
        "- : string = \"1\"\n"
       ]
      },
      "execution_count": 44,
      "metadata": {},
      "output_type": "execute_result"
     }
    ],
    "source": [
     "to_binary 10;;\n",
     "to_binary 2;;\n",
     "to_binary 1;;"
    ]
   },
   {
    "cell_type": "code",
    "execution_count": 45,
    "id": "c234416c-be09-4265-84f8-473c684d5e13",
    "metadata": {},
    "outputs": [
     {
      "data": {
       "text/plain": [
        "- : int = 55\n"
       ]
      },
      "execution_count": 45,
      "metadata": {},
      "output_type": "execute_result"
     },
     {
      "data": {
       "text/plain": [
        "- : int = 55\n"
       ]
      },
      "execution_count": 45,
      "metadata": {},
      "output_type": "execute_result"
     }
    ],
    "source": [
     "fib 10;;\n",
     "fib_fast 10;;"
    ]
   },
   {
    "cell_type": "code",
    "execution_count": 46,
    "id": "831079e0-85d8-4799-9283-139e8b33af7c",
    "metadata": {},
    "outputs": [],
    "source": [
     "(* 14\n",
     "\n",
     "NEW IDEA: carrying a search interval rather than a value, and choosing an\n",
     "invariant you can state.\n",
     "\n",
     "int_sqrt n returns the largest k such that k*k <= n, for n >= 0, so it\n",
     "truncates. Do it by binary search, tail recursively, with an inner helper\n",
     "carrying lo and hi.\n",
     "\n",
     "Before writing it, decide the invariant in words: what must always be true of\n",
     "lo and hi? Getting that sentence right is most of the work, and off-by-one\n",
     "errors here are the norm rather than a failure.\n",
     "\n",
     "One trap worth knowing in advance: for n near 10^12, starting hi at n makes\n",
     "mid * mid overflow a 63-bit int silently. Either start hi somewhere smaller\n",
     "that is still definitely above the answer, or compare without multiplying.\n",
     "\n",
     "int_sqrt 0 = 0, int_sqrt 15 = 3, int_sqrt 16 = 4, int_sqrt 17 = 4,\n",
     "int_sqrt 1_000_000_000_000 = 1_000_000.\n",
     "\n",
     "*)"
    ]
   },
   {
    "cell_type": "code",
    "execution_count": 47,
    "id": "0ac0572b-66a4-4a18-aefa-7de3d02515ba",
    "metadata": {
     "deletable": true,
     "editable": true,
     "slideshow": {
      "slide_type": ""
     },
     "tags": []
    },
    "outputs": [
     {
      "data": {
       "text/plain": [
        "val int_sqrt : int -> int = <fun>\n"
       ]
      },
      "execution_count": 47,
      "metadata": {},
      "output_type": "execute_result"
     }
    ],
    "source": [
     "let int_sqrt n = \n",
     "    let rec go low hi =\n",
     "        if hi - low <= 1 \n",
     "            then \n",
     "            if hi = 0 then 0 else\n",
     "            if hi > n / hi then low else hi\n",
     "        else\n",
     "            let mid = hi - ((hi - low) / 2) in\n",
     "            if mid > n / mid\n",
     "            then\n",
     "                go low mid\n",
     "            else\n",
     "                go mid hi\n",
     "    in go 0 n"
    ]
   },
   {
    "cell_type": "code",
    "execution_count": 69,
    "id": "e13a3ee4-4bde-4a15-ae6f-62db9447c748",
    "metadata": {},
    "outputs": [
     {
      "data": {
       "text/plain": [
        "- : int = 4\n"
       ]
      },
      "execution_count": 69,
      "metadata": {},
      "output_type": "execute_result"
     },
     {
      "data": {
       "text/plain": [
        "- : int = 3\n"
       ]
      },
      "execution_count": 69,
      "metadata": {},
      "output_type": "execute_result"
     },
     {
      "data": {
       "text/plain": [
        "- : int = 4\n"
       ]
      },
      "execution_count": 69,
      "metadata": {},
      "output_type": "execute_result"
     },
     {
      "data": {
       "text/plain": [
        "- : int = 3\n"
       ]
      },
      "execution_count": 69,
      "metadata": {},
      "output_type": "execute_result"
     },
     {
      "data": {
       "text/plain": [
        "- : int = 3\n"
       ]
      },
      "execution_count": 69,
      "metadata": {},
      "output_type": "execute_result"
     },
     {
      "data": {
       "text/plain": [
        "- : int = 0\n"
       ]
      },
      "execution_count": 69,
      "metadata": {},
      "output_type": "execute_result"
     },
     {
      "data": {
       "text/plain": [
        "- : int = 1000000\n"
       ]
      },
      "execution_count": 69,
      "metadata": {},
      "output_type": "execute_result"
     }
    ],
    "source": [
     "int_sqrt 17;;\n",
     "int_sqrt 10;;\n",
     "int_sqrt 16;;\n",
     "int_sqrt 12;;\n",
     "int_sqrt 11;;\n",
     "int_sqrt 0;;\n",
     "int_sqrt 1000000000000;;"
    ]
   },
   {
    "cell_type": "code",
    "execution_count": 120,
    "id": "7415ca41-1c3a-4828-af4e-51736596bb3f",
    "metadata": {},
    "outputs": [
     {
      "name": "stdout",
      "output_type": "stream",
      "text": [
       "- : unit = ()\n",
       "Findlib has been successfully loaded. Additional directives:\n",
       "  #require \"package\";;      to load a package\n",
       "  #list;;                   to list the available packages\n",
       "  #camlp4o;;                to load camlp4 (standard syntax)\n",
       "  #camlp4r;;                to load camlp4 (revised syntax)\n",
       "  #predicates \"p,q,...\";;   to set these predicates\n",
       "  Topfind.reset();;         to force that packages will be reloaded\n",
       "  #thread;;                 to enable threads\n",
       "\n",
       "- : unit = ()\n"
      ]
     }
    ],
    "source": [
     "#use \"topfind\";;\n",
     "#require \"qcheck\";;"
    ]
   },
   {
    "cell_type": "code",
    "execution_count": 124,
    "id": "7bc3f682-7c8b-4520-aeb0-9bb33a802e22",
    "metadata": {},
    "outputs": [
     {
      "data": {
       "text/plain": [
        "val squared_invariant : QCheck.Test.t = QCheck2.Test.Test <abstr>\n"
       ]
      },
      "execution_count": 124,
      "metadata": {},
      "output_type": "execute_result"
     },
     {
      "name": "stdout",
      "output_type": "stream",
      "text": [
       "================================================================================\n",
       "\u001b[32;1msuccess\u001b[0m (ran 1 tests)\n"
      ]
     },
     {
      "data": {
       "text/plain": [
        "- : int = 0\n"
       ]
      },
      "execution_count": 124,
      "metadata": {},
      "output_type": "execute_result"
     }
    ],
    "source": [
     "let squared_invariant = QCheck.Test.make\n",
     "    (QCheck.int_range 0 212000)\n",
     "    (fun n -> n == int_sqrt (n * n));;\n",
     "\n",
     "QCheck_base_runner.run_tests [ squared_invariant ];;"
    ]
   }
  ],
  "metadata": {
   "kernelspec": {
    "display_name": "OCaml default",
    "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.14.2"
   }
  },
  "nbformat": 4,
  "nbformat_minor": 5
 }