scan_left.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Python `scan` function\n",
    "- [Introduction](#introduction)\n",
    "- [Install](#install)\n",
    "  - [via `ur`](#ur)\n",
    "  - [as a `git` `submodule`](#submodule)\n",
    "- [Implementation](#implementation)\n",
    "- [Examples](#examples)\n",
    "\n",
    "## Introduction <a id=\"introduction\"></a>\n",
    "\"Scans\" (technically \"scan left\" and \"scan right\") are a common functional-ish list operation conspicuously absent from Python's stdlib (and even `functools`!).\n",
    "\n",
    "A \"scan\" is like a \"reduce\" (or \"fold\"), but *every intermediate value is returned*, in a list (instead of just the final \"total\"):\n",
    "\n",
    "```python\n",
    "from functools import reduce\n",
    "from operator import add\n",
    "\n",
    "reduce(add, range(10))\n",
    "# 45\n",
    "\n",
    "scan(add, range(10))\n",
    "# [0, 1, 3, 6, 10, 15, 21, 28, 36, 45]                 \n",
    "```\n",
    "\n",
    "See below for an implementation and [some examples](#Examples):"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Install <a id=\"install\"></a>\n",
    "Use this module by as a source dependency (using [`ur`](https://pypi.org/project/ur/)) or by [adding it as a `git submodule`](#submodule):\n",
    "\n",
    "### via [`ur`](https://pypi.org/project/ur/) <a id=\"ur\"></a>\n",
    "[`ur`](https://pypi.org/project/ur/) is a module that supports `import`ing code directly from remote Gists.\n",
    "\n",
    "Install it:\n",
    "```python\n",
    "from sys import executable as python\n",
    "!{python} -m pip install -q ur==0.1.3\n",
    "```\n",
    "\n",
    "Then you can import directly from this Gist!\n",
    "```python\n",
    "from gists.b2b0ef9365e050da361e37b6150dbc4a.scan_left import scan\n",
    "```\n",
    "\n",
    "Use away!\n",
    "\n",
    "```python\n",
    "from operator import add\n",
    "scan(add, range(10))\n",
    "# [0, 1, 3, 6, 10, 15, 21, 28, 36, 45]\n",
    "```\n",
    "\n",
    "See [a live example](./ur-import-scan-example.ipynb).\n",
    "\n",
    "### As a `git submodule` <a id=\"submodule\"></a>\n",
    "An easy (and more production-appropriate) way to quickly make `scan` available in your project is to add this gist as a `git submodule`.\n",
    "\n",
    "From the root of your project, run:\n",
    "```bash\n",
    "git submodule add git@gist.github.com:b2b0ef9365e050da361e37b6150dbc4a.git scans\n",
    "```\n",
    "\n",
    "Then `import` from your Python sources:\n",
    "```python\n",
    "from scans.scan_left import scan\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Implementation <a id=\"implementation\"></a>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from functools import reduce\n",
    "\n",
    "def scan(fn, elems, *args, **kwargs):\n",
    "    '''Like functools.reduce, but return an array of all partially-reduced values\n",
    "\n",
    "    If a third (\"init\") value is passed, the returned array will include it as its first element, and be longer than the\n",
    "    input array by 1.\n",
    "\n",
    "    Otherwise, the output array will share the same first element as the input, and have the same length.'''\n",
    "\n",
    "    # Determine whether a final, optional \"init\" argument was passed (distinguishing between no argument being passed at\n",
    "    # all, and e.g. None being passed)\n",
    "    init = None\n",
    "    found_init = False\n",
    "    if args:\n",
    "        if len(args) > 1:\n",
    "            raise ValueError('At most one positional argument (\"init\") allowed: %s' % args)\n",
    "        (init,) = args\n",
    "        found_init = True\n",
    "\n",
    "    if kwargs:\n",
    "        keys = list(kwargs.keys())\n",
    "        if keys != ['init']:\n",
    "            raise ValueError('Unepxected kwargs (only \"init\" allowed): %s' % kwargs)\n",
    "\n",
    "        if found_init:\n",
    "            raise ValueError('Provide \"init\" either as positional xor keyword arg: %s, %s' % (args, kwargs))\n",
    "\n",
    "        init = kwargs['init']\n",
    "        found_init = True\n",
    "\n",
    "    def _fn(results, elem):\n",
    "        return results + [fn(results[-1], elem)]\n",
    "\n",
    "    if not found_init:\n",
    "        if not len(elems):\n",
    "            raise ValueError(\"Can't scan empty list without init value\")\n",
    "        init = elems[0]\n",
    "        elems = elems[1:]\n",
    "\n",
    "    return reduce(_fn, elems, [init])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Examples <a id=\"examples\"></a>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "from operator import add"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "When a 3rd (\"init\") argument is passed, it becomes the base case, and is the first element in the output:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 1, 3, 6, 10, 15, 21, 28, 36, 45]"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "scan(add, range(1,10), 0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "When `init` is absent, the first element of the input is taken as the base:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "45"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from functools import reduce\n",
    "reduce(add, range(10))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 1, 3, 6, 10, 15, 21, 28, 36, 45]"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "scan(add, range(10))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If no explicit `init` is provided, empty input `raise`s:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "ValueError: Can't scan empty list without init value\n"
     ]
    }
   ],
   "source": [
    "try: \n",
    "    scan(add, [])\n",
    "except Exception as e:\n",
    "    print(f'{type(e).__name__}: {e}')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Presence of explicit `init` makes empty input OK:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[123]"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "scan(add, [], 123)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "3.8.1",
   "language": "python",
   "name": "3.8.1"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}

ur-import-scan-example.ipynb