docs/pattern_matching_nesting_reduction.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Pattern matching nesting reduction"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We have to implement the function `classify` with the following signature"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "dotnet_interactive": {
     "language": "fsharp"
    },
    "polyglot_notebook": {
     "kernelName": "fsharp"
    },
    "vscode": {
     "languageId": "polyglot-notebook"
    }
   },
   "outputs": [],
   "source": [
    "type Status = Started | NotStarted | Completed\n",
    "let classify (first: 'a option) (last: 'b option): Status = raise <| NotImplementedException()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A common implementation would be the following:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "dotnet_interactive": {
     "language": "fsharp"
    },
    "polyglot_notebook": {
     "kernelName": "fsharp"
    },
    "vscode": {
     "languageId": "polyglot-notebook"
    }
   },
   "outputs": [],
   "source": [
    "let classify (first: 't option) (last: 'u option) =\n",
    "  match first with\n",
    "  | Some _ ->\n",
    "    match last with\n",
    "    | Some _ -> Completed\n",
    "    | _ -> Started\n",
    "  | _ -> NotStarted"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "dotnet_interactive": {
     "language": "fsharp"
    },
    "polyglot_notebook": {
     "kernelName": "fsharp"
    },
    "vscode": {
     "languageId": "polyglot-notebook"
    }
   },
   "outputs": [],
   "source": [
    "[classify (Some 0) None; classify None (Some \"x\"); classify (Some 0) (Some \"y\")]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "However, we can make a trade of nested pattern matching by a more complex data structure and a simpler pattern match:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "dotnet_interactive": {
     "language": "fsharp"
    },
    "polyglot_notebook": {
     "kernelName": "fsharp"
    },
    "vscode": {
     "languageId": "polyglot-notebook"
    }
   },
   "outputs": [],
   "source": [
    "let classify (first: 't option) (last: 'u option) =\n",
    "  match first, last with\n",
    "  | Some _, Some _ -> Completed\n",
    "  | Some _, _ -> Started \n",
    "  | _ -> NotStarted"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "dotnet_interactive": {
     "language": "fsharp"
    },
    "polyglot_notebook": {
     "kernelName": "fsharp"
    },
    "vscode": {
     "languageId": "polyglot-notebook"
    }
   },
   "outputs": [],
   "source": [
    "[classify (Some 0) None; classify None (Some \"x\"); classify (Some 0) (Some \"y\")]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The trick can be generalized if the following conditions are true\n",
    "- you have a nested pattern matching\n",
    "- the decision to take one branch or another depends only on pure values (no implicit state can change the decision)\n",
    "\n",
    "Then what we do is encoding in each branch the precondition necessary to produce each value in the original code. Let's anotate the previous example with such preconditions:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "dotnet_interactive": {
     "language": "fsharp"
    },
    "polyglot_notebook": {
     "kernelName": "fsharp"
    },
    "vscode": {
     "languageId": "polyglot-notebook"
    }
   },
   "outputs": [],
   "source": [
    "let classify (first: 't option) (last: 'u option) =\n",
    "  match first with\n",
    "  | Some _ ->\n",
    "    match last with\n",
    "    | Some _ ->\n",
    "        // precondition: first.IsSome && last.IsSome \n",
    "        Completed\n",
    "    | _ ->\n",
    "        // precondition: first.IsSome && last.IsNone\n",
    "        Started\n",
    "  | _ -> \n",
    "    // precondition: first.IsNone\n",
    "    NotStarted"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now you can see we only use the arrow `->` when we match the exact condition that produces a value, and by following that principle we continue by creating a more complex structure to match, but we reduce the nested matches. The inspiration for this trick comes from [Dijkstra's Guarded Command Language](https://www.cs.utexas.edu/users/EWD/transcriptions/EWD04xx/EWD472.html) and [Programming: The Derivation of Algorithms](https://books.google.de/books/about/Programming.html?id=4nJqQgAACAAJ&redir_esc=y)."
   ]
  }
 ],
 "metadata": {
  "language_info": {
   "name": "python"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}