{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "60ba8eca-b36c-4261-9633-bbcdf2fa00c1",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "exception Change\n"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val change : int list * int -> int list = <fun>\n"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "exception Change\n",
    "let rec change (till, amt) =\n",
    "  if amt=0 then []\n",
    "  else\n",
    "    match till with\n",
    "    | [] -> raise Change\n",
    "    | c :: till ->\n",
    "       if amt < c then\n",
    "         change (till, amt)\n",
    "       else \n",
    "         try\n",
    "           c :: change (c :: till, amt - c)\n",
    "         with Change ->\n",
    "           change (till, amt)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "348f2cfa-0b76-4241-bdb2-7c7ab915dd8b",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "change is now traced.\n"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#trace change"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "ac0a298c-ca7c-414b-af3b-93989149bcad",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "change <-- ([5; 2], 16)\n",
       "change <-- ([5; 2], 11)\n",
       "change <-- ([5; 2], 6)\n",
       "change <-- ([5; 2], 1)\n",
       "change <-- ([2], 1)\n",
       "change <-- ([], 1)\n",
       "change raises Change\n",
       "change raises Change\n",
       "change raises Change\n",
       "change <-- ([2], 6)\n",
       "change <-- ([2], 4)\n",
       "change <-- ([2], 2)\n",
       "change <-- ([2], 0)\n",
       "change --> []\n",
       "change --> [2]\n",
       "change --> [2; 2]\n",
       "change --> [2; 2; 2]\n",
       "change --> [2; 2; 2]\n",
       "change --> [5; 2; 2; 2]\n",
       "change --> [5; 5; 2; 2; 2]\n",
       "- : int list = [5; 5; 2; 2; 2]\n"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "change ([5; 2], 16)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "OCaml 4.14",
   "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.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}