commit 559120bedfb894798fbd06be8f7958824dbf1ed3
parent 41b99f434a06ebf1f03e2a7a0025ff7fb416c209
Author: Andrew Laack <andrew@laack.co>
Date: Mon, 17 Aug 2026 14:41:31 -0500
Self-learning via notebooks
Diffstat:
5 files changed, 2298 insertions(+), 0 deletions(-)
diff --git a/ch1_self_learning/better_fizzbuzz.ipynb b/ch1_self_learning/better_fizzbuzz.ipynb
@@ -0,0 +1,112 @@
+{
+ "cells": [
+ {
+ "cell_type": "code",
+ "execution_count": 4,
+ "id": "f39de10b-caca-47ca-8510-b373729e957c",
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "val as_str : int -> string = <fun>\n"
+ ]
+ },
+ "execution_count": 4,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "let as_str idx = \n",
+ " let x = (if idx mod 3 = 0 then \"Fizz\" else \"\")\n",
+ " ^ \n",
+ " (if idx mod 5 = 0 then \"Buzz\" else \"\")\n",
+ " in if x = \"\" then string_of_int idx else x"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 5,
+ "id": "8f03e107-c163-4e93-896d-2daa6a443b28",
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "val print_fizz_buzz : int -> unit = <fun>\n"
+ ]
+ },
+ "execution_count": 5,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "let print_fizz_buzz n = for i = 1 to n do \n",
+ " print_endline (as_str i)\n",
+ "done"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 6,
+ "id": "d46ba613-0fb0-46b2-ba3c-3c3a7b892efd",
+ "metadata": {},
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "1\n",
+ "2\n",
+ "Fizz\n",
+ "4\n",
+ "Buzz\n",
+ "Fizz\n",
+ "7\n",
+ "8\n",
+ "Fizz\n",
+ "Buzz\n",
+ "11\n",
+ "Fizz\n",
+ "13\n",
+ "14\n",
+ "FizzBuzz\n"
+ ]
+ },
+ {
+ "data": {
+ "text/plain": [
+ "- : unit = ()\n"
+ ]
+ },
+ "execution_count": 6,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "print_fizz_buzz 15"
+ ]
+ }
+ ],
+ "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
+}
diff --git a/ch1_self_learning/exercises_unit_1.ipynb b/ch1_self_learning/exercises_unit_1.ipynb
@@ -0,0 +1,1939 @@
+{
+ "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
+}
diff --git a/ch1_self_learning/factorial.ipynb b/ch1_self_learning/factorial.ipynb
@@ -0,0 +1,66 @@
+{
+ "cells": [
+ {
+ "cell_type": "code",
+ "execution_count": 32,
+ "id": "90212f01-2e8f-4533-b643-38c453ca87ba",
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "val factorial : int -> int = <fun>\n"
+ ]
+ },
+ "execution_count": 32,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "let rec factorial x = if x <= 1 then \n",
+ " if x < 0 then raise (Failure \"Factorial undefined for negative integers\") else 1 \n",
+ " else (factorial (x - 1)) * x;;"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 35,
+ "id": "9e7b075f-f95f-4a85-95df-753c9161ccbb",
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "- : int = 1\n"
+ ]
+ },
+ "execution_count": 35,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "factorial (0)"
+ ]
+ }
+ ],
+ "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
+}
diff --git a/ch1_self_learning/fib.ipynb b/ch1_self_learning/fib.ipynb
@@ -0,0 +1,66 @@
+{
+ "cells": [
+ {
+ "cell_type": "code",
+ "execution_count": 16,
+ "id": "99cfd687-6196-48c4-a786-2b433d7967e4",
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "val fib : int -> int = <fun>\n"
+ ]
+ },
+ "execution_count": 16,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "let rec fib x = \n",
+ " if x <= 1 then x \n",
+ " else fib (x - 1) + fib (x - 2)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 17,
+ "id": "3a625d9d-7843-4db0-ba67-74ddbe28dce3",
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "- : int = 0\n"
+ ]
+ },
+ "execution_count": 17,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "fib 0"
+ ]
+ }
+ ],
+ "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
+}
diff --git a/ch1_self_learning/fizzbuzz.ipynb b/ch1_self_learning/fizzbuzz.ipynb
@@ -0,0 +1,115 @@
+{
+ "cells": [
+ {
+ "cell_type": "code",
+ "execution_count": 51,
+ "id": "f39de10b-caca-47ca-8510-b373729e957c",
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "val as_str : int -> string = <fun>\n"
+ ]
+ },
+ "execution_count": 51,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "let as_str idx = \n",
+ " if idx mod 3 = 0\n",
+ " then if idx mod 5 = 0\n",
+ " then \"FizzBuzz\"\n",
+ " else \"Fizz\"\n",
+ " else if idx mod 5 = 0\n",
+ " then \"Buzz\"\n",
+ " else string_of_int idx"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 52,
+ "id": "8f03e107-c163-4e93-896d-2daa6a443b28",
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "val print_fizz_buzz : int -> unit = <fun>\n"
+ ]
+ },
+ "execution_count": 52,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "let print_fizz_buzz n = for i = 1 to n do \n",
+ " print_endline (as_str i)\n",
+ "done"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 53,
+ "id": "d46ba613-0fb0-46b2-ba3c-3c3a7b892efd",
+ "metadata": {},
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "1\n",
+ "2\n",
+ "Fizz\n",
+ "4\n",
+ "Buzz\n",
+ "Fizz\n",
+ "7\n",
+ "8\n",
+ "Fizz\n",
+ "Buzz\n",
+ "11\n",
+ "Fizz\n",
+ "13\n",
+ "14\n",
+ "FizzBuzz\n"
+ ]
+ },
+ {
+ "data": {
+ "text/plain": [
+ "- : unit = ()\n"
+ ]
+ },
+ "execution_count": 53,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "print_fizz_buzz 15"
+ ]
+ }
+ ],
+ "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
+}
