{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 44,
   "id": "cfcd61f9-65ba-40bd-a068-16e920e5ed56",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val add : int -> int -> int = <fun>\n"
      ]
     },
     "execution_count": 44,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let add x y = x + y"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "id": "9d1233cb-0159-4ac3-83e0-9d1278373f84",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "add is now traced.\n"
      ]
     },
     "execution_count": 45,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#trace add"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "id": "a5f18212-6bad-482e-9427-d2a407efad2a",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "add <-- 1\n",
       "add --> <fun>\n",
       "add* <-- 2\n",
       "add* --> 3\n",
       "- : int = 3\n"
      ]
     },
     "execution_count": 46,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "add 1 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "id": "2a3c4fbc-bca1-4392-8416-08a9e2afbc4f",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "type seq = Nil | Cons of int * (unit -> seq)\n"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "type seq =\n",
    "| Nil\n",
    "| Cons of int * (unit -> seq)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "id": "82ed6947-9a7f-46dd-be76-2bd72eda434a",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val from : int -> seq = <fun>\n"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let rec from k = Cons (k, fun () -> from (k+1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "id": "4686571c-094d-4ac3-ae3f-d0387a464cd7",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val interleave : seq * seq -> seq = <fun>\n"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let rec interleave (xq, yq) =\n",
    "  match xq with\n",
    "  | Nil -> yq\n",
    "  | Cons (x, xf) ->\n",
    "      Cons (x, fun () -> interleave (yq, (xf ())))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "id": "f159f90b-369d-4f49-bbe4-23cbb6dee499",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val get : int * seq -> int list = <fun>\n"
      ]
     },
     "execution_count": 43,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let rec get (n, s) = \n",
    "  if n = 0 then []\n",
    "  else\n",
    "    match s with\n",
    "    | Nil -> []\n",
    "    | Cons (x, xf) -> x :: get (n-1, xf ())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "id": "419ac101-c863-4317-bd3b-3a66690dcaa4",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "interleave is now traced.\n"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "from is now traced.\n"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "get is now traced.\n"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#trace interleave\n",
    "#trace from\n",
    "#trace get"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "id": "979a3c92-5d98-4cad-a839-551a1d272e52",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "from <-- 1\n",
       "from --> Cons (1, <fun>)\n",
       "val x : seq = Cons (1, <fun>)\n"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "from <-- 100\n",
       "from --> Cons (100, <fun>)\n",
       "val y : seq = Cons (100, <fun>)\n"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "interleave <-- (Cons (1, <fun>), Cons (100, <fun>))\n",
       "interleave --> Cons (1, <fun>)\n",
       "val z : seq = Cons (1, <fun>)\n"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "get <-- (10, Cons (1, <fun>))\n",
       "from <-- 2\n",
       "from --> Cons (2, <fun>)\n",
       "interleave <-- (Cons (100, <fun>), Cons (2, <fun>))\n",
       "interleave --> Cons (100, <fun>)\n",
       "get <-- (9, Cons (100, <fun>))\n",
       "from <-- 101\n",
       "from --> Cons (101, <fun>)\n",
       "interleave <-- (Cons (2, <fun>), Cons (101, <fun>))\n",
       "interleave --> Cons (2, <fun>)\n",
       "get <-- (8, Cons (2, <fun>))\n",
       "from <-- 3\n",
       "from --> Cons (3, <fun>)\n",
       "interleave <-- (Cons (101, <fun>), Cons (3, <fun>))\n",
       "interleave --> Cons (101, <fun>)\n",
       "get <-- (7, Cons (101, <fun>))\n",
       "from <-- 102\n",
       "from --> Cons (102, <fun>)\n",
       "interleave <-- (Cons (3, <fun>), Cons (102, <fun>))\n",
       "interleave --> Cons (3, <fun>)\n",
       "get <-- (6, Cons (3, <fun>))\n",
       "from <-- 4\n",
       "from --> Cons (4, <fun>)\n",
       "interleave <-- (Cons (102, <fun>), Cons (4, <fun>))\n",
       "interleave --> Cons (102, <fun>)\n",
       "get <-- (5, Cons (102, <fun>))\n",
       "from <-- 103\n",
       "from --> Cons (103, <fun>)\n",
       "interleave <-- (Cons (4, <fun>), Cons (103, <fun>))\n",
       "interleave --> Cons (4, <fun>)\n",
       "get <-- (4, Cons (4, <fun>))\n",
       "from <-- 5\n",
       "from --> Cons (5, <fun>)\n",
       "interleave <-- (Cons (103, <fun>), Cons (5, <fun>))\n",
       "interleave --> Cons (103, <fun>)\n",
       "get <-- (3, Cons (103, <fun>))\n",
       "from <-- 104\n",
       "from --> Cons (104, <fun>)\n",
       "interleave <-- (Cons (5, <fun>), Cons (104, <fun>))\n",
       "interleave --> Cons (5, <fun>)\n",
       "get <-- (2, Cons (5, <fun>))\n",
       "from <-- 6\n",
       "from --> Cons (6, <fun>)\n",
       "interleave <-- (Cons (104, <fun>), Cons (6, <fun>))\n",
       "interleave --> Cons (104, <fun>)\n",
       "get <-- (1, Cons (104, <fun>))\n",
       "from <-- 105\n",
       "from --> Cons (105, <fun>)\n",
       "interleave <-- (Cons (6, <fun>), Cons (105, <fun>))\n",
       "interleave --> Cons (6, <fun>)\n",
       "get <-- (0, Cons (6, <fun>))\n",
       "get --> []\n",
       "get --> [104]\n",
       "get --> [5; 104]\n",
       "get --> [103; 5; 104]\n",
       "get --> [4; 103; 5; 104]\n",
       "get --> [102; 4; 103; 5; 104]\n",
       "get --> [3; 102; 4; 103; 5; 104]\n",
       "get --> [101; 3; 102; 4; 103; 5; 104]\n",
       "get --> [2; 101; 3; 102; 4; 103; 5; 104]\n",
       "get --> [100; 2; 101; 3; 102; 4; 103; 5; 104]\n",
       "get --> [1; 100; 2; 101; 3; 102; 4; 103; 5; 104]\n",
       "- : int list = [1; 100; 2; 101; 3; 102; 4; 103; 5; 104]\n"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let x = from 1\n",
    "let y = from 100\n",
    "let z = interleave (x, y);;\n",
    "get (10, z)\n"
   ]
  }
 ],
 "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
}