loopless_tutorial.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Look ma' - no loops!\n",
    "\n",
    "This is a small tutorial containing Python recipes for loopless programming.\n",
    "\n",
    "## What is loopless programming?\n",
    "\n",
    "As the name suggests, loopless is about avoiding `for`- and `while` loops.\n",
    "Less loops in your code, often simplifies the code and lets us focus on *what* we are trying to achieve, rather than *how*.\n",
    "\n",
    "Note that throughout this tutorial we will use the term `sequence` interchangably with `iterable`, even though technically a [Sequence](https://docs.python.org/3/glossary.html#term-sequence) in Python is different from an [Iterable](https://docs.python.org/3/glossary.html#term-iterable).\n",
    "\n",
    "This little tutorial will provide tiny recipes sorted by topic.\n",
    "But first, let's define a little function for providing more interesting output."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from IPython.display import display, Markdown\n",
    "\n",
    "\n",
    "# this little function prints markdown instead of raw text\n",
    "def print_markdown(markdown: str) -> None:\n",
    "    display(Markdown(markdown))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Combining sequences\n",
    "\n",
    "One common task in programming is combining sequences of data. This use case has two varieties that we are going to take a look at next."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Simple pairing\n",
    "\n",
    "For pairing two sequences of equal length, we can use the built-in [`zip()`](https://docs.python.org/3/library/functions.html#zip)\n",
    "function.\n",
    "\n",
    "**Recipe 1**:\n",
    "\n",
    "> `combined = zip(seq1, seq2, ...)`\n",
    "\n",
    "**Example**:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "a = [1, 2, 3, 4]\n",
    "b = ['solo', 'duet', 'trio', 'quartette']\n",
    "\n",
    "c = zip(a, b)\n",
    "print(list(c))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Merging sequences of unequal lengths\n",
    "\n",
    "What if we have two sequences of different lengths? In this case we have a few ways of generating a combined result."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Option 1: Combine using the shortest sequence\n",
    "\n",
    "This is what the `zip()` function des by default.\n",
    "\n",
    "**Recipe 2.1**:\n",
    "\n",
    "> `shortest_combination = zip(seq1, seq2, ...)`\n",
    "\n",
    "**Example:**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "a = [1, 2, 3, 4, 5]\n",
    "b = ['solo', 'duet', 'trio', 'quartette']\n",
    "\n",
    "c = zip(a, b)\n",
    "print(list(c))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Option 2: Padding\n",
    "\n",
    "A second way of combining sequences of different lengths is to pair the extra elements in the longest  sequences with some fixed value. This is often referred to as *padding* and can be achieved using [`itertools.zip_longest`](https://docs.python.org/3/library/itertools.html#itertools.zip_longest).\n",
    "\n",
    "**Recipe 2.2**:\n",
    "\n",
    "> `padded_combined_seq = zip_longest(seq1, seq2, ..., fillvalue=padding_value)`\n",
    "\n",
    "**Example**:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from itertools import zip_longest\n",
    "\n",
    "a = [1, 2, 3, 4, 5, 23]\n",
    "b = ['solo', 'duet', 'trio', 'quartette']\n",
    "\n",
    "c = zip_longest(a, b, fillvalue='many')\n",
    "print(list(c))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Option 3: Repeat the shorter sequence\n",
    "\n",
    "The function [`itertools.cycle`](https://docs.python.org/3/library/itertools.html#itertools.cycle) allows us to\n",
    "restart an iterator after it returned its last element.\n",
    "\n",
    "**Recipe 2.3**:\n",
    "\n",
    "> `combined = zip(longer_seq, cycle(shorter_seq), ...)`\n",
    "\n",
    "**or**\n",
    "\n",
    "> `combined = zip(cycle(shorter_seq), longer_seq, ...)`\n",
    "\n",
    "**Example**:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from itertools import cycle\n",
    "\n",
    "a = ['red', 'green', 'blue', 'yellow']\n",
    "b = ['TRIANGLE', 'CIRCLE']\n",
    "\n",
    "c = zip(a, cycle(b))\n",
    "print_markdown('➡'.join(f'<span style=\"color:{col}\">{txt}</span>' for col, txt in c))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Option 4: Repeat a single value\n",
    "\n",
    "We can also pair input sequences with a single value using [`itertools.repeat`](https://docs.python.org/3/library/itertools.html#itertools.repeat).\n",
    "\n",
    "**Recipe 2.4**:\n",
    "\n",
    "> `combined = zip(seq1, ..., repeat(some_value))`\n",
    "\n",
    "**Example**:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from itertools import repeat\n",
    "\n",
    "a = [10, 12, 15, 18]\n",
    "\n",
    "c = zip(a, repeat('SAMPLE TEXT'))\n",
    "print_markdown('•'.join(f'<span style=\"font-size:{sz}pt\">{txt}</span>' for sz, txt in c))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### All combinations of multiple sequences\n",
    "\n",
    "Oftentimes we want to generate all combinations of multiple sequences.\n",
    "Take a card game, for example. We have suits and card values and want to generate a list of all available cards in the game. Such combination is called a [*Cartesian product*](https://en.wikipedia.org/wiki/Cartesian_product) and can be generated using [`itertools.product`](https://docs.python.org/3/library/itertools.html#itertools.product).\n",
    "\n",
    "**Recipe 3**:\n",
    "\n",
    "> `all_combinations = product(seq1, seq2, ...)`\n",
    "\n",
    "**Example**:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from itertools import product\n",
    "\n",
    "suites = ['♠', '♣', '♥', '♦']\n",
    "values = ['ace', 'king', 'queen', 'jack', '10', '9', '8', '7']\n",
    "\n",
    "deck = product(suites, values)\n",
    "print(list(deck))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Flatten nested sequences\n",
    "\n",
    "A [common question](https://stackoverflow.com/questions/25674169/how-does-the-list-comprehension-to-flatten-a-python-list-work) is how to turn a nested sequence into a flat sequence.\n",
    "\n",
    "Since we're in the *loopless* camp, we don't want no list comprehensions😉. Instead, we can use [`itertools.chain`](https://docs.python.org/3/library/itertools.html#itertools.chain) and a [`starred expression`](https://docs.python.org/3/reference/expressions.html#grammar-token-python-grammar-starred_item).\n",
    "\n",
    "**Recipe 4**:\n",
    "\n",
    "> `flattened = chain(*nested)`\n",
    "\n",
    "**Example**:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from itertools import chain\n",
    "\n",
    "def f(x):\n",
    "    return x + 10\n",
    "\n",
    "def g(x):\n",
    "    return x * 10\n",
    "\n",
    "# some operation that returns tuples of (f(x), g(x))\n",
    "data = [1, 23, 4, 17, 9, 2, 49]\n",
    "result = chain(*((f(x), g(x)) for x in data))\n",
    "print(list(result))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Multiple nesting levels\n",
    "\n",
    "The `chain`-method can in principle be applied to more deeply nested sequences:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "lines = [((1, 2, 3), (4, 5, 6)), ((7, 8, 9), (10, 11, 12))]\n",
    "\n",
    "coords = chain(*chain(*lines))\n",
    "\n",
    "print(list(coords))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It might, however, be more readable and cleaner to do the flattening explicitly instead:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "lines = [((1, 2, 3), (4, 5, 6)), ((7, 8, 9), (10, 11, 12))]\n",
    "\n",
    "points = chain(*lines)      # list of pairs of vecs -> sequence of vecs\n",
    "coords = chain(*points)     # sequence of vecs -> sequence of individual coords\n",
    "\n",
    "print(list(coords))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Splitting nested sequences\n",
    "\n",
    "Sometimes it's useful to split a nested sequence into multiple sequences, each containing elements of the input sequence.\n",
    "\n",
    "We can use a combination of `zip()` and a *starred expresision* to do this looplessly:\n",
    "\n",
    "**Recipe 5a**:\n",
    "\n",
    "> `*zip(*nested)`\n",
    "\n",
    "In contexts where a *starred expression* cannot be used, we can replace it with `map()` to generate a tuple of outputs instead:\n",
    "\n",
    "**Recipe 5b**:\n",
    "\n",
    "> `seq1, seq2, ... = map(iter|list, zip(*nested))`\n",
    "\n",
    "**Example**:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "parameters_by_name = {\n",
    "    'x': 1.0,\n",
    "    'y': -7.2,\n",
    "    'z': 0.0\n",
    "}\n",
    "\n",
    "names, values = map(iter, zip(*parameters_by_name.items()))\n",
    "print(list(names))\n",
    "print(list(values))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Transforming data\n",
    "\n",
    "Data sequences can be transformed by extracting the transformation step into a function and using `map()` to apply the function to each element:\n",
    "\n",
    "**Recipe 6**:\n",
    "\n",
    "> results = map(transformation_fn, seq_of_args, ...)\n",
    "\n",
    "**Example 1 - Single input**:\n",
    "\n",
    "Let's transform a sequence of integers by applying $ f: x \\to x^2 $"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def f(x):\n",
    "    return x ** 2\n",
    "\n",
    "squares = map(f, range(1, 21))\n",
    "print(list(squares))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Example 2 - Multiple inputs**:\n",
    "\n",
    "Functions with multiple inputs work by passing multiple arguments to `map()`.\n",
    "Say we have $f: \\Bbb{N}^2 \\to \\Bbb{R}, (x, y) \\to \\frac{x^2}{y}$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def f(x, y):\n",
    "    return x ** 2 / y\n",
    "\n",
    "results = map(f, range(10), range(1, 11))\n",
    "print(list(results))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Example 3 - Tuple input:**\n",
    "\n",
    "Since the use-case of the previous example is so common and data may already be tuples,\n",
    "`itertools.starmap()` unpacks tuples for us if the input is just a single iterable."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from itertools import starmap\n",
    "\n",
    "\n",
    "styles = {\n",
    "    'font-size': '18pt',\n",
    "    'color': 'steelblue',\n",
    "    'font-weight': 'bold',\n",
    "    'text-decoration': 'underline'\n",
    "}\n",
    "\n",
    "def css_prop(property, value):\n",
    "    return f'{property}:{value}'\n",
    "\n",
    "props = starmap(css_prop, styles.items())\n",
    "span = f'<span style=\"{\";\".join(props)}\">Hello, world!</span>'\n",
    "print_markdown(span)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Filtering data\n",
    "\n",
    "Selecting elements from a sequence based on some boolean function (\"criterion\" or \"predicate\") can be done using `filter()` function. `itertools.filterfalse()` adds\n",
    "the ability to filter for the case when the predicate function returns false.\n",
    "\n",
    "**Recipe 7:**\n",
    "\n",
    "> matching_elements = filter(predicate, sequence)\n",
    "\n",
    "**-or-**\n",
    "\n",
    "> nonmatching_elements = filterfalse(predicate, sequence)\n",
    "\n",
    "**Example**:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def is_multiple_of_4(x):\n",
    "    return not x % 4\n",
    "\n",
    "numbers = range(1, 21)\n",
    "multiples_of_4 = filter(is_multiple_of_4, numbers)\n",
    "print(list(multiples_of_4))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Replacing nested loops\n",
    "\n",
    "Using the tools we've looked at so far, we can now procede to replace nested `for`-loops with loopless versions.\n",
    "\n",
    "For a motivating example, let's consider a use case where we want to schedule the play-offs between two divisions of an e-sports league.\n",
    "\n",
    "We might start with a looped implementation similar to this:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "division_a = ['The Squirrels', 'Hometown Girls', 'Geeks United']\n",
    "division_b = ['Scooter Gang', 'Slow Pokes']\n",
    "game_modes = ['Best-of-Three', 'Lucky-Shot']\n",
    "\n",
    "\n",
    "def schedule_game(team_a, team_b, game_mode):\n",
    "    return f'scheduling {game_mode} match between {team_a} and {team_b}'\n",
    "\n",
    "schedule = []\n",
    "for team_a in division_a:\n",
    "    for team_b in division_b:\n",
    "        for mode in game_modes:\n",
    "            match = schedule_game(team_a, team_b, mode)\n",
    "            schedule.append(match)\n",
    "\n",
    "print('\\n'.join(schedule))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Looking at the loops, we can see that we have a case of *Cartesian product*, which we already know how to handle:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from itertools import product\n",
    "\n",
    "all_combinations = list(product(division_a, division_b, game_modes))\n",
    "print(all_combinations)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Finally, we can *transform* these lists to our final result by using `starmap()` and `schedule_game()`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from itertools import starmap\n",
    "\n",
    "schedule = starmap(schedule_game, all_combinations)\n",
    "print('\\n'.join(schedule))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Putting it all together, we can replace the nested `for`-loop version with this loopless one-liner:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from itertools import product, starmap\n",
    "\n",
    "schedule = starmap(schedule_game, product(division_a, division_b, game_modes))\n",
    "print('\\n'.join(schedule))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### General recipe for replacing nested loops\n",
    "\n",
    "To summarise how to replace nested `for`-loops that iterate over multiple inputs:\n",
    "\n",
    "**Recipe 8:**\n",
    "\n",
    "> `result = starmap(loop_body_fn, product(outermost_inputs, middle_inputs, ...))`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Refactoring the loop body\n",
    "\n",
    "The first step to convert existing nested `for`-loops is to move the loop-body into a separate function. Pass all variables used in the loop into that function starting with non-loop variables.\n",
    "\n",
    "Anything the loop body calculates and stores somewhere should be part of the return value instead, e.g."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "\n",
    "colours = ['green', 'lime', 'yellow', 'orange']\n",
    "font_sizes = [10, 14]\n",
    "sample_texts = ['Foo', 'Bar']\n",
    "\n",
    "# non-loop variable\n",
    "delim = random.choice('!?;:')\n",
    "\n",
    "markdown_text = []\n",
    "for colour in colours:\n",
    "    for font_size in font_sizes:\n",
    "        for text in sample_texts:\n",
    "            # -- loop body --\n",
    "            style = f'font-size:{font_size}pt; color:{colour}'\n",
    "            sample = f'<span style=\"{style}\">{text}{delim}</span>'\n",
    "            markdown_text.append(sample)  # calculated output\n",
    "            # ---------------"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# step 1: move loop body into a separate function:\n",
    "\n",
    "def loop_body_fn(delim, colour, font_size, text):\n",
    "    style = f'font-size:{font_size}pt; color:{colour}'\n",
    "    sample = f'<span style=\"{style}\">{text}{delim}</span>'\n",
    "    return sample"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Next we can apply the recipe. We can use `list()` to trigger the evaluation:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from itertools import product, starmap\n",
    "\n",
    "_ = list(starmap(loop_body_fn, product(colours, font_sizes, sample_texts)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Unfortunately, this doesn't work. We somehow need to pass our non-loop variable `delim` to `loop_body_fn()` somehow. We could use the `repeat()` recipe to pass a sequence that always returns the value of `delim` as the first parameter:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# don't uncomment the lines below and run this 😉\n",
    "# _ = list(starmap(loop_body_fn, product(repeat(delim), colours, font_sizes, sample_texts)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Hm. We'd rather not run this, because since `repeat()` will never stop returning elements, this will cause problems. Of course we could switch the order of the parameters or pass the number of times to `repeat()`, but that's not a good general solution.\n",
    "\n",
    "Instead, we can use `functools.partial()` to get a function that will have the first (or any, really) argument fixed to whatever we want:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from itertools import product, starmap\n",
    "from functools import partial\n",
    "\n",
    "fixed_loop_body = partial(loop_body_fn, delim)\n",
    "markdown = starmap(fixed_loop_body, product(colours, font_sizes, sample_texts))\n",
    "print_markdown(''.join(markdown))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Advanced: Splitting sequences based on a predicate\n",
    "\n",
    "So far, we've dealt with separating sequences into sequences of the same length.\n",
    "What if we wanted to split an input sequence based on an arbitrary predicate?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from itertools import filterfalse\n",
    "\n",
    "candidates = iter(range(1, 13))\n",
    "\n",
    "\n",
    "def is_multiple_of_4(x):\n",
    "    return not x % 4\n",
    "\n",
    "\n",
    "multiples_of_4 = filter(is_multiple_of_4, candidates)\n",
    "other_values = filterfalse(is_multiple_of_4, candidates)\n",
    "print(list(multiples_of_4))\n",
    "print(list(other_values))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "What happened here, why is our second sequence empty? Note how `candidates` uses `iter()` to turn the range into an iteration. Since we exhaust the iterator with the first call to `filter()` already, the subsequent call to `filterfalse()` will get an empty sequence.\n",
    "\n",
    "Luckily, there's the `itertools.tee()` function, which can return multiple independent iterators from the given one:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from itertools import filterfalse, tee\n",
    "\n",
    "candidates = iter(range(1, 13))\n",
    "\n",
    "\n",
    "def is_multiple_of_4(x):\n",
    "    print(f'🔎{x}')\n",
    "    return not x % 4\n",
    "\n",
    "# get an independent iterator for both filter passes\n",
    "it1, it2 = tee(candidates)\n",
    "\n",
    "multiples_of_4 = filter(is_multiple_of_4, it1)\n",
    "other_values = filterfalse(is_multiple_of_4, it2)\n",
    "print(list(multiples_of_4))\n",
    "print(list(other_values))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "That worked! Great, but we also noticed that it still looks at the input twice.\n",
    "This might be very costly if the predicate is a complex function, or worse straight up impossible if our input iterator cannot be restarted (e.g. when we are processing a non-seekable stream of data).\n",
    "\n",
    "We can evaluate both, the input and the predicate in one go and return the value along with its evaluated predicate:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "candidates = iter(range(1, 18))\n",
    "\n",
    "def pred(x):\n",
    "    return not x % 4\n",
    "\n",
    "evaluated = map(lambda x: (x, pred(x)), candidates)\n",
    "print(list(evaluated))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we can filter the evaluated results. This still means iterating twice, but only over an already evaluated set of data."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from itertools import filterfalse, tee\n",
    "\n",
    "candidates = iter(range(1, 13))\n",
    "\n",
    "def pred(x):\n",
    "    return not x % 4\n",
    "\n",
    "evaluated = map(lambda x: (x, pred(x)), candidates)\n",
    "# remember that we need two independent iterators\n",
    "iter_matches, iter_others = tee(evaluated)\n",
    "matches = filter(lambda x: x[1], iter_matches)\n",
    "others = filterfalse(lambda x: x[1], iter_others)\n",
    "print(list(matches))\n",
    "print(list(others))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Finally we need to transform the filtered results by discarding the second tuple member.\n",
    "\n",
    "We can put this into a `partition()` function that can be reused whenever the functionality is needed:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "from functools import partial\n",
    "from itertools import filterfalse, tee\n",
    "from typing import Callable, Iterable, TypeVar, Union\n",
    "\n",
    "\n",
    "_T = TypeVar('_T')\n",
    "\n",
    "\n",
    "def partition(\n",
    "    predicate: Callable[[_T], bool], iterable: Iterable[_T]\n",
    ") -> tuple[Iterable[_T], Iterable[_T]]:\n",
    "    \"\"\"Return a 2-tuple of iterables from an input iterable based on a\n",
    "    predicate.\n",
    "\n",
    "    Args:\n",
    "        predicate (Callable): Predicate that takes an element of the iterable\n",
    "            and returns whether element matches some criterion\n",
    "\n",
    "        iterable (iter): Iterable to be partitioned in matching and non-matching\n",
    "            elements\n",
    "\n",
    "    Returns:\n",
    "        (tuple[iter, iter]) The first iterable yields all matching elements in the\n",
    "            input. The second iterable yields all non-matching elements of the\n",
    "            input.\n",
    "    \"\"\"\n",
    "    def _get(n: int, tuple_: tuple[_T, bool]) -> Union[_T, bool]:\n",
    "        return tuple_[n]\n",
    "\n",
    "    first, second = partial(_get, 0), partial(_get, 1)\n",
    "    evaluations = map(lambda x: (x, predicate(x)), iterable)\n",
    "    iter_matches, iter_others = tee(evaluations)\n",
    "    return (\n",
    "        map(first, filter(second, iter_matches)),\n",
    "        map(first, filterfalse(second, iter_others))\n",
    "    )"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's try our previous example using the `partition()` function: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "candidates = iter(range(1, 14))\n",
    "\n",
    "\n",
    "def is_multiple_of_4(x):\n",
    "    print(f'🔎{x}')\n",
    "    return not x % 4\n",
    "\n",
    "\n",
    "multiples_of_4, other_values = partition(is_multiple_of_4, candidates)\n",
    "\n",
    "print(list(multiples_of_4))\n",
    "print(list(other_values))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As we can see, every value in the input is only looked at once.\n",
    "If you're interested in more tools like `partition()`, there's\n",
    "the [**more-itertools**](https://github.com/more-itertools/more-itertools) libary,\n",
    "which also contains a `partition()` function (though it disagrees on the order of\n",
    "the returned iterators) among many other useful tools for loopless programming.\n",
    "\n",
    "This is also the point where our little journey ends."
   ]
  }
 ],
 "metadata": {
  "interpreter": {
   "hash": "3e329b1da267758074ae479256bab7eb65d1196bcfdf9708a39f16c0f5257827"
  },
  "kernelspec": {
   "display_name": "Python 3.9.10 ('base')",
   "language": "python",
   "name": "python3"
  },
  "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.10.4"
  },
  "orig_nbformat": 4
 },
 "nbformat": 4,
 "nbformat_minor": 2
}