OCaml_lists.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In an effort to start learning some patterns in ML, I decided to go with small steps and reimplement some patterns in OCaml. Assumming the concept of `list` doesn't exist yet we will reimplement a similar concept known as `sequence`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "type 'a seq = End | Next of 'a * 'a seq\n"
      ]
     },
     "execution_count": 56,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "type 'a seq =\n",
    "  | End\n",
    "  | Next of 'a * 'a seq\n",
    ";;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can define a sequence of zero elements like this:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val no_elements : 'a seq = End\n"
      ]
     },
     "execution_count": 58,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let no_elements = End"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Or the count from 1 to 3 like this:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val sample : int seq = Next (1, Next (2, Next (3, End)))\n"
      ]
     },
     "execution_count": 59,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let sample = Next(1, Next(2, Next(3, End)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Implement basic operations\n",
    "\n",
    "Length, Head, Tail, Cons"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val length_seq : 'a seq -> int = <fun>\n"
      ]
     },
     "execution_count": 60,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "- : int = 3\n"
      ]
     },
     "execution_count": 60,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val head_seq : 'a seq -> 'a = <fun>\n"
      ]
     },
     "execution_count": 60,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "- : int = 1\n"
      ]
     },
     "execution_count": 60,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val tail_seq : 'a seq -> 'a seq = <fun>\n"
      ]
     },
     "execution_count": 60,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "- : int seq = Next (2, Next (3, End))\n"
      ]
     },
     "execution_count": 60,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val cons_seq : 'a -> 'a seq -> 'a seq = <fun>\n"
      ]
     },
     "execution_count": 60,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "- : int seq = Next (0, Next (1, Next (2, Next (3, End))))\n"
      ]
     },
     "execution_count": 60,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(* length operator *)\n",
    "let length_seq x =\n",
    "  let rec length' acc = function\n",
    "    | End -> acc\n",
    "    | Next (_, t) -> length' (acc + 1) t\n",
    "  in\n",
    "  length' 0 x\n",
    ";;\n",
    "\n",
    "length_seq sample;;\n",
    "\n",
    "(* head operator *)\n",
    "let head_seq = function\n",
    "  | End -> raise (Invalid_argument \"empty sequence\")\n",
    "  | Next (h, _) -> h\n",
    ";;\n",
    "\n",
    "head_seq sample;;\n",
    "\n",
    "(* tail operator *)\n",
    "let tail_seq = function\n",
    "  | End -> raise (Invalid_argument \"empty sequence\")\n",
    "  | Next (_, t) -> t\n",
    ";;\n",
    "\n",
    "tail_seq sample;;\n",
    "\n",
    "(* cons operator *)\n",
    "let cons_seq x l = Next(x, l) ;;\n",
    "cons_seq 0 sample ;;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we can start implementing even more complex operations, like `nth`, `rev`, `append`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val nth_seq : int -> 'a seq -> 'a = <fun>\n"
      ]
     },
     "execution_count": 61,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "- : int = 1\n"
      ]
     },
     "execution_count": 61,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "- : int = 3\n"
      ]
     },
     "execution_count": 61,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val rev_seq : 'a seq -> 'a seq = <fun>\n"
      ]
     },
     "execution_count": 61,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "- : int seq = Next (3, Next (2, Next (1, End)))\n"
      ]
     },
     "execution_count": 61,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "File \"[61]\", line 28, characters 29-60:\n",
      "Warning 51: expected tailcall\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "val append_seq : 'a seq -> 'a seq -> 'a seq = <fun>\n"
      ]
     },
     "execution_count": 61,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "- : int seq = Next (1, Next (2, Next (3, Next (4, Next (5, Next (6, End))))))\n"
      ]
     },
     "execution_count": 61,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val append_seq' : 'a seq -> 'b -> 'b = <fun>\n"
      ]
     },
     "execution_count": 61,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "- : int seq = Next (1, Next (2, Next (3, Next (4, Next (5, Next (6, End))))))\n"
      ]
     },
     "execution_count": 61,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val ( +: ) : 'a -> 'a seq -> 'a seq = <fun>\n"
      ]
     },
     "execution_count": 61,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "- : int seq = Next (0, Next (1, Next (2, Next (3, End))))\n"
      ]
     },
     "execution_count": 61,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(* nth operator *)\n",
    "let rec nth_seq n l = \n",
    "  if n < 0 then raise (Invalid_argument \"nth\") else\n",
    "  match l with\n",
    "    | End -> raise (Failure \"nth\")\n",
    "    | Next (x, tl) -> if n = 0 then x else nth_seq (n - 1) tl\n",
    ";;\n",
    "\n",
    "nth_seq 0 sample ;;\n",
    "nth_seq 2 sample ;;\n",
    "\n",
    "(* rev operator *)\n",
    "let rev_seq l =\n",
    "  let rec rev' acc = function\n",
    "    | End -> acc\n",
    "    | Next (x, tl) -> rev' (cons_seq x acc) tl\n",
    "  in\n",
    "  rev' End l\n",
    ";;\n",
    "\n",
    "rev_seq sample ;;\n",
    "\n",
    "(* append operator, this function is not tail recursive *)\n",
    "(* the original in OCaml neither *)\n",
    "let rec append_seq a b =\n",
    "  match a with\n",
    "   | End -> b\n",
    "   | Next (x, tl) -> Next(x, ((append_seq [@tailcall]) tl b))\n",
    ";;\n",
    "\n",
    "append_seq sample (Next(4, Next(5, Next(6, End))))\n",
    "\n",
    "(* We can make a recursive append *)\n",
    "let append_seq' a b =\n",
    "  let rec append' acc = function\n",
    "    | End -> b\n",
    "    | Next (x, t) -> append' (Next(x, acc)) t\n",
    "  in\n",
    "  append' End (rev_seq a)\n",
    ";;\n",
    "\n",
    "append_seq sample (Next(4, Next(5, Next(6, End)))) ;;\n",
    "\n",
    "let (+:) a b = cons_seq a b ;;\n",
    "0 +: sample"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we can start playing with functions and lists. What about `init`, `map` and, more importantly, `fold_right` and `fold_left`?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val init_seq : int -> (int -> 'a) -> 'a seq = <fun>\n"
      ]
     },
     "execution_count": 62,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "- : int seq = Next (1, Next (2, Next (3, End)))\n"
      ]
     },
     "execution_count": 62,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val map_seq : ('a -> 'b) -> 'a seq -> 'b seq = <fun>\n"
      ]
     },
     "execution_count": 62,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "File \"[62]\", line 13, characters 32-59:\n",
      "Warning 51: expected tailcall\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "- : int seq = Next (2, Next (4, Next (6, End)))\n"
      ]
     },
     "execution_count": 62,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val map_seq : f:('a -> 'b) -> 'a seq -> 'b seq = <fun>\n"
      ]
     },
     "execution_count": 62,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "- : int seq = Next (2, Next (4, Next (6, End)))\n"
      ]
     },
     "execution_count": 62,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(* init operator *)\n",
    "let init_seq n f =\n",
    "  let rec init' n' acc =\n",
    "    if n' = 0 then acc else init' (n' - 1) (cons_seq (f n') acc)\n",
    "  in\n",
    "  init' n End\n",
    ";;\n",
    "\n",
    "init_seq 3 (fun x -> x) ;;\n",
    "\n",
    "(* map operator, not tail recursive *)\n",
    "let rec map_seq f = function\n",
    "  | Next (x, t) -> Next ((f x), ((map_seq [@tailcall]) f t))\n",
    "  | _ -> End\n",
    ";;\n",
    "\n",
    "map_seq (fun x -> x * 2) sample ;;\n",
    "\n",
    "(* map operator, now tail recursive *)\n",
    "let map_seq ~f l =\n",
    "  let rec map_seq' acc = function\n",
    "    | End -> acc\n",
    "    | Next (x, t) -> map_seq' (Next((f x), acc)) t\n",
    "  in\n",
    "  rev_seq (map_seq' End l)\n",
    ";;\n",
    "\n",
    "map_seq ~f:(fun x -> x * 2) sample"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now it is time for the `fold` functions. The fold functions is just a nicer way to say \"aggregate\" functions."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 105,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val fold_left_seq : f:('a -> 'b -> 'a) -> init:'a -> 'b seq -> 'a = <fun>\n"
      ]
     },
     "execution_count": 105,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "- : int = 6\n"
      ]
     },
     "execution_count": 105,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let rec fold_left_seq ~f ~init = function\n",
    "  | End -> init\n",
    "  | Next (x, tl) -> (fold_left_seq [@tailcall]) ~f ~init:(f init x) tl\n",
    ";;\n",
    "\n",
    "fold_left_seq ~f:(fun a b -> a + b) ~init:0 sample"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "the contrapart of `fold_left_seq` is `fold_right_seq`, we can implement it in two ways, a non-tail recursive and a tail recursive version, let's see both:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 143,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "File \"[143]\", line 5, characters 24-66:\n",
      "Warning 51: expected tailcall\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "val fold_right_seq : f:('a -> 'b -> 'b) -> 'a seq -> init:'b -> 'b = <fun>\n"
      ]
     },
     "execution_count": 143,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val fold_right_seq : f:('a -> 'b -> 'b) -> 'a seq -> init:'b -> 'b = <fun>\n"
      ]
     },
     "execution_count": 143,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(* Non tail recursive fold_right *)\n",
    "let rec fold_right_seq ~f l ~init =\n",
    "  match l with\n",
    "  | End -> init\n",
    "  | Next (x, tl) -> f x ((fold_right_seq [@tailcall]) ~f tl ~init)\n",
    ";;\n",
    "\n",
    "(* tail recursive fold_right *)\n",
    "(* Notice we have to _reverse_ the list and change the signature of ~f *)\n",
    "let rec fold_right_seq ~f l ~init = \n",
    "  fold_left_seq ~f:(fun a b -> f b a) (rev_seq l) ~init ;;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "When to use which? well, it depends, in _theory_ the non-tail recursive is more efficient but of course it cannot work in long sequences, being $O(n)$ while the tail recursive is $O(n^2)$. **Remember**, `cons_seq` is $O(1)$, while `rev_seq` is $O(n)$ (the same as `fold_left_seq`) and when using _reverse inner accumulator loop_ we get $O(2n)$ which is basically $O(n)$\n",
    "\n",
    "The difference between both is about memory and performance. For _large sequences_ our tail recursive version is the only option while for short sequences is prefered to use the non tail recursive.\n",
    "\n",
    "We can implement other basic sequence functions based in `fold_left`, for example, the always important function `rev`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 125,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val rev_seq' : '_weak8 seq -> '_weak8 seq = <fun>\n"
      ]
     },
     "execution_count": 125,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "- : int seq = Next (3, Next (2, Next (1, End)))\n"
      ]
     },
     "execution_count": 125,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let rev_seq' = \n",
    "  fold_left_seq ~f:(fun l' x -> cons_seq x l') ~init:End \n",
    ";;\n",
    "\n",
    "rev_seq' sample"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Notice how we are _currying_ the function definition, because _why not?_.\n",
    "\n",
    "More complex functions can be represented with fold as well, for example, `map`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 144,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val map_seq' : f:('a -> 'b) -> 'a seq -> 'b seq = <fun>\n"
      ]
     },
     "execution_count": 144,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "- : int seq = Next (1, Next (2, Next (3, End)))\n"
      ]
     },
     "execution_count": 144,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "- : int seq = Next (2, Next (4, Next (6, End)))\n"
      ]
     },
     "execution_count": 144,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let map_seq' ~f =\n",
    "  fold_right_seq ~f:(fun elem l -> cons_seq (f elem) l) ~init:End\n",
    ";;\n",
    "sample ;;\n",
    "map_seq' ~f:(fun x -> x * 2) sample"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "OCaml 4.06.0",
   "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.06.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}