Skip to content

Instantly share code, notes, and snippets.

@ryan-williams

ryan-williams/dask-monad.ipynb

Last active April 1, 2020 05:54
Show Gist options
  • Save ryan-williams/5304c3c400a1eeb5995bf2d85188d1d9 to your computer and use it in GitHub Desktop.
Save ryan-williams/5304c3c400a1eeb5995bf2d85188d1d9 to your computer and use it in GitHub Desktop.
Download ZIP
Display the source blob
Display the rendered blob
Raw
dask-monad.ipynb
{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Is [Dask `Delayed`](https://docs.dask.org/en/latest/delayed.html) a Monad?\n",
"[Dask](https://dask.org/) is a very cool Python library, and one of its core abstractions is the \"[Delayed](https://docs.dask.org/en/latest/delayed.html)\" container.\n",
"\n",
"`delayed`:\n",
"- wraps values\n",
"- records subsequent operations on these wrapped values (without performing the operations)\n",
"- lets you think you are working with raw values\n",
"\n",
"Meanwhile, it builds a graph of your program, providing opportunities to [visualize](https://docs.dask.org/en/latest/graphviz.html), [optimize](https://docs.dask.org/en/latest/optimize.html), and [parallelize](https://distributed.dask.org/en/latest/) your computations.\n",
"\n",
"## Contexualizing Dask Delayed\n",
"Delayed clearly looks like abstractions found in other contexts; it provides \"laziness\" and \"provenance\", and I've guessed that it's a [Monad](https://en.wikipedia.org/wiki/Monad_(functional_programming) (though the API doesn't make that obvious).\n",
"\n",
"I recently needed to do [some relatively intricate Dask-graph manipulations](https://nbviewer.jupyter.org/gist/ryan-williams/0aeb2111cb8b7fd588784e2a7c35433e/chain-example.ipynb), and had trouble ekeing simple monadic transformations out of Dask's APIs, so here I'll compare [`Delayed`](https://docs.dask.org/en/latest/delayed.html) to a few relevant to [category-theoretic](https://en.wikipedia.org/wiki/Category_theory) concepts (as implemented in [Scala's \"Cats\" library](https://typelevel.org/cats)):\n",
"- [**`Delayed` is an Applicative**](#applicative)\n",
" - [`pure`](#pure)\n",
" - [`map`](#map)\n",
" - [`ap`](#ap)\n",
"- [**`Delayed is a Monad**](#monad)\n",
" - [`flatten`](#flatten)\n",
" - [`flatMap`](#flatMap)\n",
"- [**Discussion**](#discussion)\n",
" - [Sequencing computations](#sequencing)\n",
" - [Example: task-chaining](#chaining)\n",
" - [Dynamic task graphs](#dynamic-graphs)"
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {},
"outputs": [],
"source": [
"from dask import delayed"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"--------\n",
"## Delayed is an [Applicative](https://typelevel.org/cats/typeclasses/applicative.html#applicative) <a id=\"applicative\"></a>\n",
"[Applicatives](https://typelevel.org/cats/typeclasses/applicative.html#applicative) support 3 operations:\n",
"\n",
"| Name | Type | Notes |\n",
"| ---- | ---- | ----- |\n",
"| `pure` | `A ⇒ F[A]` | Lift any value into the `Delayed` container |\n",
"| `ap` | `(F[A], F[A ⇒ B]) ⇒ F[B]` | Apply a `Delayed` function to a `Delayed` value and obtain a `Delayed` result |\n",
"| `map` | `(F[A], A ⇒ B) ⇒ F[B]` | Apply a function to a `Delayed` value and obtain a `Delayed` result |\n",
"\n",
"See examples below:\n",
"### `pure` <a id=\"pure\"></a>\n",
"`A ⇒ F[A]`; lift any value into the `Delayed` container:"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"Delayed('int-fdb51b88-bca5-44de-b591-6d98f19b6497')"
]
},
"execution_count": 2,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"a = 4\n",
"fa = delayed(a); fa"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\"Unboxing\", just to check:"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"4"
]
},
"execution_count": 3,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"fa.compute()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"A \"generic\" implementation is trivial:"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {},
"outputs": [],
"source": [
"def pure(a): return delayed(a)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"As we see, `delayed` itself is the simplest generic implementation of the `pure` capability:"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {},
"outputs": [],
"source": [
"pure = delayed"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### `ap` <a id=\"ap\"></a>\n",
"`(F[A], F[A ⇒ B]) ⇒ F[B]`; apply a `Delayed` function to a `Delayed` value and obtain a `Delayed` result"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"Delayed('hex-38be2eca-d878-44fd-bc9e-7749e355a8a5')"
]
},
"execution_count": 6,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"_hex = delayed(hex) # F[int ⇒ str]: a delayed function from an int to a str\n",
"fb = _hex(fa); fb"
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"'0x4'"
]
},
"execution_count": 7,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"fb.compute()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We passed a `Delayed` value to a `Delayed` function and the two levels of \"delay\" were \"flattened\" into the usual/desired one level, so that a single `.compute()` returns the value.\n",
"\n",
"🆒😎\n",
"\n",
"The generic implementation is again trivial:"
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {},
"outputs": [],
"source": [
"ap = lambda fa, f_a_b: f_a_b(fa)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### `map`\n",
"`(F[A], A ⇒ B) ⇒ F[B]`; apply a function to a `Delayed` value and obtain a `Delayed` result\n",
"\n",
"This is the defining capability of a [Functor](https://typelevel.org/cats/typeclasses/functor.html), which [Applicatives](https://typelevel.org/cats/typeclasses/applicative.html#applicative) implement, and is conceptually simpler than [`ap`](#ap).\n",
"\n",
"However, it's not obvious how to do in Dask, at least directly. Dask really wants to work with `Delayed` functions, not feed `Delayed` values directly to eager functions.\n",
"\n",
"Luckily, [`pure`](#pure) and [`ap`](#ap) are sufficient to implement `map` (which also explains why [`Applicative`s](https://typelevel.org/cats/typeclasses/applicative.html#applicative) are [`Functor`s](https://typelevel.org/cats/typeclasses/functor.html)):"
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {},
"outputs": [],
"source": [
"map = lambda fa, a_b: delayed(a_b)(fa)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Example:"
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"Delayed('hex-3d16e63e-8790-4680-9c71-be3bf71ac3dc')"
]
},
"execution_count": 10,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"fb = map(fa, hex); fb"
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"'0x4'"
]
},
"execution_count": 11,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"fb.compute()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Here we turned an `F[int]` and an `int ⇒ str` into an `F[str]` 👍"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"-------\n",
"## Is `Delayed` a [Monad](https://typelevel.org/cats/typeclasses/monad.html)? <a id=\"monad\"></a>\n",
"Great, `Delayed` is an [Applicative](https://typelevel.org/cats/typeclasses/applicative.html#applicative) (and a [Functor](https://typelevel.org/cats/typeclasses/functor.html)); but is it a [Monad](https://typelevel.org/cats/typeclasses/monad.html)?\n",
"\n",
"According to [Cats' Monad docs](https://typelevel.org/cats/typeclasses/monad.html#monad):\n",
"> `Monad` extends the `Applicative` type class with a new function `flatten`. Flatten takes a value in a nested context (eg. `F[F[A]]` where F is the context) and “joins” the contexts together so that we have a single context (ie. `F[A]`).\n",
"\n",
"So all we need to prove `Delayed`'s monadicity is `flatten`!\n",
"\n",
"### `flatten` <a id=\"flatten\"></a>\n",
"`F[F[A]] ⇒ F[A]`: \"join\" two levels of `Delayed` into one\n",
"\n",
"(Note: this operation is commonly called \"join\" as well)\n",
"\n",
"Naively, we can always remove a layer of `F[_]` wrapping by calling `.compute()` (which has type `F[A] ⇒ [A]`):"
]
},
{
"cell_type": "code",
"execution_count": 12,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"4"
]
},
"execution_count": 12,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"fa.compute() # F[int] ⇒ int"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"In principle flattening is as simple as:"
]
},
{
"cell_type": "code",
"execution_count": 13,
"metadata": {},
"outputs": [],
"source": [
"def flatten(fa): return fa.compute() # F[A] ⇒ A"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We know this works for `F[A] ⇒ A`, but what about `F[F[A]] ⇒ F[A]`?\n",
"\n",
"Substituting \"`F[A]`\" for \"`A`\" in the type `F[A] ⇒ A` yields `F[F[A]] ⇒ F[A]`, indicating that it *should* work, but let's try to construct an `F[F[A]]` to test it:"
]
},
{
"cell_type": "code",
"execution_count": 14,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"Delayed('int-fdb51b88-bca5-44de-b591-6d98f19b6497')"
]
},
"execution_count": 14,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"ffa = delayed(fa); ffa"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"It turns out that `delayed` is clever, and has short-circuited the double-wrap here. A single `.compute()` gives us our value back:"
]
},
{
"cell_type": "code",
"execution_count": 15,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"4"
]
},
"execution_count": 15,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"ffa.compute()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"However, we can still pull one over on `delayed`:"
]
},
{
"cell_type": "code",
"execution_count": 16,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"Delayed('lambda-3e297b56-1348-49ca-b3a2-7ad5a0b9a7d5')"
]
},
"execution_count": 16,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"ffa = delayed(lambda a: delayed(a))(a); ffa"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"`ffa` is truly of type `F[F[A]]`; calling `.compute()` gives us an `F[A]` (still Delayed!):"
]
},
{
"cell_type": "code",
"execution_count": 17,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"Delayed('int-174298a5-f846-4c8d-8b51-166eff6c0dd4')"
]
},
"execution_count": 17,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"ffa.compute()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Calling `.compute()` twice yields our original value again:"
]
},
{
"cell_type": "code",
"execution_count": 18,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"4"
]
},
"execution_count": 18,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"ffa.compute().compute()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Clearly, `flatten` (a.k.a. `compute`) is possible for Delayed objects! So…\n",
"\n",
"#### 🎉🎉 `Delayed` is a monad! 🎉🎉"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### `flatMap` <a id=\"flatMap\"></a>\n",
"`(F[A], A ⇒ F[B]) ⇒ F[B]`\n",
"\n",
"For completeness, let's discuss `flatMap`.\n",
"\n",
"#### intro\n",
"`flatMap` is typically the core behavior of a Monad:\n",
"- a `Delayed` value (`F[A]`) is fed to a function\n",
"- that function, roughly:\n",
" - enters the `F` \"box\" where the actual `A` value is\n",
" - transforms the `A` to a `B` *while introducing a second level of delay/wrapping* (`A ⇒ F[B]`)\n",
" - leaves the box (meaning now we expect to be doubly-nested in two layers of `F[_]`, with an `F[F[B]]`)!.\n",
"\n",
"#### magic\n",
"Yet, somehow, the magic of `flatMap` yields a transformed – but only singly-wrapped – value (`F[B]`).\n",
"\n",
"This \"magic\" – the specifics of *how* a monad takes something doubly-wrapped, and unwraps a layer (or, more commonly, fakes it and lets you carry on as if it has) – is what defines the big, famous, common monads:\n",
"\n",
"- Maybe (a.k.a. Option)\n",
"- Future (a.k.a. Promise; see also async/await)\n",
"- List, Set\n",
"- Try (like Option, but stores+propagates an error)\n",
"- IO, Lazy (basically what Dask Delayed does)\n",
"\n",
"#### deriving from `map`, `flatten`\n",
"With all that said, `flatMap` is trivially implementable in terms of `map` and `flatten`:"
]
},
{
"cell_type": "code",
"execution_count": 19,
"metadata": {},
"outputs": [],
"source": [
"flatMap = lambda fa, a_fb: flatten(map(fa, a_fb))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Testing:"
]
},
{
"cell_type": "code",
"execution_count": 20,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"'0x4'"
]
},
"execution_count": 20,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"int_to_delayed_str = lambda a: delayed(hex(a))\n",
"\n",
"flatMap(fa, int_to_delayed_str).compute()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Hooray!"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Discussion <a id=\"discussion\"></a>\n",
"\n",
"### Sequencing computations <a id=\"sequencing\"></a>\n",
"A defining characteristic of Monads is that they support *sequencing* computations (i.e. running things in serial, one after another).\n",
"\n",
"That's ironic given Dask's focus on parallel computation, but nevertheless frequently useful.\n",
"\n",
"The intuition for why that is can be found in the signature of [`flatMap`](#flatMap):\n",
"```\n",
"(F[A], A ⇒ F[B]) ⇒ F[B]\n",
"```\n",
"You start with one computation (`F[A]`), and you end with another (`F[B]`); could they both be running concurrently at some point?\n",
"\n",
"The answer is no: the second computation, `F[B]`, is never created (or introduced into the task graph) until the function `A ⇒ F[B]` has completed, and the `A` from the original `F[A]` must be available, and unboxed, before `A ⇒ F[B]` can happen!\n",
"\n",
"#### Case study: \"chaining\" tasks <a id=\"chaining\"></a>\n",
"Let's leverage this \"sequencing\" property to construct a function that, given two tasks `F[A]` and `F[B]`, will run `F[A]` to completion, then `F[B]`, and return both values (`(F[A], F[B]) ⇒ (A, B)`):"
]
},
{
"cell_type": "code",
"execution_count": 21,
"metadata": {},
"outputs": [],
"source": [
"from time import sleep\n",
"def id(x):\n",
" '''Simple function that returns the value it's passed\n",
" \n",
" It also prints its progress, and sleeps on a certain value\n",
" (which we'll pass first, to verify tasks aren't running\n",
" concurrently)'''\n",
"\n",
" print(f'computing: {x}')\n",
" if x == 'A':\n",
" print(f'Sleeping…')\n",
" sleep(1)\n",
" print(f'computed: {x}')\n",
" return x\n",
"\n",
"id = delayed(id)\n",
"\n",
"# Sample \"delayed\" values\n",
"fa = id('A', dask_key_name='idA')\n",
"fb = id('B', dask_key_name='idB')"
]
},
{
"cell_type": "code",
"execution_count": 22,
"metadata": {},
"outputs": [],
"source": [
"def sequence(fa, fb):\n",
" # Helper which receives a computed `a`, and in turn computes `b`\n",
" _sequence = lambda a: (a, fb.compute())\n",
"\n",
" name = f\"combine_{fb._key}\"\n",
" return delayed(_sequence)(fa, dask_key_name=name)"
]
},
{
"cell_type": "code",
"execution_count": 23,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"Delayed('combine_idB')"
]
},
"execution_count": 23,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"res = sequence(fa, fb); res"
]
},
{
"cell_type": "code",
"execution_count": 24,
"metadata": {
"scrolled": true
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"computing: A\n",
"Sleeping…\n",
"computed: A\n",
"computing: B\n",
"computed: B\n"
]
},
{
"data": {
"text/plain": [
"('A', 'B')"
]
},
"execution_count": 24,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"res.compute()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We can see the task graph shows `A` being computed, and then combined with `B`:"
]
},
{
"cell_type": "code",
"execution_count": 25,
"metadata": {},
"outputs": [
{
"data": {
"image/png": "iVBORw0KGgoAAAANSUhEUgAAAHwAAAFeCAYAAABHDXs3AAAAAXNSR0IArs4c6QAAAERlWElmTU0AKgAAAAgAAYdpAAQAAAABAAAAGgAAAAAAA6ABAAMAAAABAAEAAKACAAQAAAABAAAAfKADAAQAAAABAAABXgAAAAD+N3sgAAAivUlEQVR4Ae1dCdRd0/XfaWNMiFQQJGYRQ1tDsYgIoaE0GtSsUkJRLF0rEUq06guWBEXVFIlMhqJpGvMUU4ihhqiZEGIoouZZe/77t/W+//veu/e9O5z7zjnvnL3W97337r1n2r97zz3D3r/dRbFQEF80MPY7vrQ0tPNbDQTAPbsTutrS3ilTptD48eOpZ8+etlRJWz1mzZplTbusAXzixInU0dFBvXr10qZoGzIaNWoUPf744zR48GAbqkPWAN61a1fq0aMHDRw40ArF6KpEt27ddGWlJZ/wDteiRncyCYC7g5WWmgbAtajRnUwC4O5gpaWmAXAtanQnkwC4O1hpqWkAXIsa3ckkAO4OVlpqGgDXokZ3MgmAu4OVlpoGwLWo0Z1MAuDuYKWlpgFwLWp0J5MAuDtYaalpAFyLGt3JJADuDlZaahoA16JGdzIJgLuDlZaaBsC1qNGdTALg7mClpaYBcC1qdCeTALg7WGmpaQBcixrdySQA7g5WWmoaANeiRncyCYC7g5WWmgbAtajRnUwC4O5gpaWmAXAtanQnkwC4O1hpqWkAXIsa3ckkAO4OVlpqGgDXokZ3MuliC23Xj3/8Y1q0aBF1797dHe2lqOmcOXOE8mPjjTdOcXXpl4y1BvCPPvqI5s2bV3qLQUs3aNAgGj58OI0YMaL08pZbbjn6/ve/X3o5KQuwB/CUFS582ezZs2nXXXeltddem5566qnC+TmWgX/EfGCL+vLLL2n+/Pm0YMECx/AqXl2vBm1fffUV/e1vfyN06/ibPn16cQ06loNXgN98880EejAInvLLLrvMMbiKV9crwCdMmEAff/xxRWvvvvuud+9xbwD/9NNP6fbbb6+AjS9ff/01gfLTJ/EG8JkzZ9Liiy/eCVsAPnny5E7H2v2HN4BffPHF9Mknn9Th+cUXX9DcuXPrjrfrAS8Af++99wgrXnHy2Wef0RlnnBF3qi2PWUOuW6Z2l1xySfrNb35D//rXv6SYp59+mvr06SNkvpietWLFrcz2ZcnbmqXVLJUuei2orMeMGWMNpXXR9mRI799KWwbltOWlXrzD2xK5nI0KgOdUnKvJAuCuIpez3l4C3qVLF/rOd7xsOnnZakzF/vvf/+Z8RtxO5iXgbkNWrPYB8GL6cy51ANw5yIpVOABeTH/OpfYScIzQMVL3UbwEHCN0jNR9FC8B9xHoqM0B8EgTnnwGwD0BOmpmADzShCefAXBPgI6a6SXgYVoWwe/JZ5iWeQJ0aCb5uT3qM/BevsMD4D5rwLO2t60jAtyK4PAP5wNwx8D7BA6F8BGHT9m1115LDz30EC2xxBIEWo5evXrR8ssvT3379hUnhXY1gXLeEeGbb76hJ554QsB78sknxf33+eefJ7gQgdZjpZVWEjBXXHFFggcKHAqXWmopAR0+4kiPmwE3xfvvv0+vvPIKvfPOO7T66qvThhtuSD/4wQ8IhDwDBgyQvBzvENzjeMEuFwCGc/8dd9xBDz/8MK211loCyEYbbSQArbfeegSA8wp6gVdffVVIhnAT4e/ee++lnj170nbbbUc77bQTDRkyRHqGvGUYSucO4Pfffz9dc8010hUvs8wy9JOf/ET+ttpqK1p22WVL1x9utOeee47uueceuuGGG8Q5cdNNN6V99tmH9thjD1phhRVKr4OGAsZiX9haeeONN9TYsWMVP8GKn1516qmnqpdeesmK+vLrQDFfjNp3330VjwHUsGHD1I033qj+85//WFG/hEp0WAn4P/7xD1Hk9773PXX44YerRx99NKH+dhzm8YJiOhG1xRZbqDXWWEOde+65igeNdlSucy3sApy7bbXDDjsoHimrs88+W/GounN1Hfj1yCOPqL322kvxiF/94Q9/UEw4aFOt7QCcB0WKB0KKR8aKKTgUT5tsUlKuuvBoXx100EGKp3tq3LhxCq8AC8Qs4DwVUkcccYTiAY9iSg7Fo2MLdKK3CjzQUzyoU2uuuaa88/Xmnjk3c4BPnTpV8dRJHXvssYrnv5lr7loCnkIqnteroUOHqtdff91U9VsP+JtvvqmYOVn98Ic/VDyfNtVwI+XyIo+819HNY5BnQFoL+F//+lfpvk8//XSFxvsq6OZxw+++++4Kr7UWSmsAxyCMSXXUOuusox588MEWts/eojCIGzlypFpttdUURvYtkvIB580Lte2226pddtlFMe1li9rlTjG8aidTuEsvvbQVlS4X8GeeeUYWIrBCxmZFrWiQk2W88MILav3111fHHXdc2XoqD3Bec1a9e/dW06ZNcxKEVlf6ww8/VAMHDlSnnHJKmXP2cgC/6667ZMHh7rvvbrXenC4P73XejFE777yz+vzzz8toS4d2Eyde96btt9+eLrroIoktomGHx5sssFd/1VVXye7flltuWY7Do87biOmp5cnmvWOd2XqXF8Y7fJcr3nNXTP6rs/36nvAHHniADjjgAOItQuJ3kTdPZRkNhe86bOd5t5BGjx5NvOWqrxgdtw/2qNmUSN1yyy06sgt5/E8DWL/A7uExxxyjSyfFB21sD6bWXXddxfFDdFUq5FOlAaxdcNwz2WOvOpz3azHAYd2BESVWjIKUp4HXXntNNpo0zHqKvcN5zkg8faAzzzxT3zsm5FSnAZhOY/QO+zk2+6o7n+lA3vsSd9uqq66qODJQ3ixCuowa4MgNiqe8RVbj8j3hH3zwAf3iF7+QuF8w4A/SGg1gxA47+vHjx+cuMJcjApvuiFku253lLjgkzKeBt956Sxwj7rzzToIdfkbJbqZ82223yZaeiwaGGXtQay+/5JJLFK/E5TGJztalI+QTmw3TpEmTaOmll854c4XLdWngV7/6legfy9dZJVOXftppp0nw8+uuuy5rOeF6zRpAZCa4PfHWqrhApcw+vasR26JJ4HNsjrCxfcr8w2VlauCoo46i7373u3T++eenLSY94EceeaTcSWyPljbzcF3JGoC3a79+/YhNpNI+hOkAhyflJptsQrxmLgv6JbcjZJ9BA7///e9p4cKFMq5KkSwd4Icddpg4ySPzIHZpAMQHcJdm41D5bFK75oDDOR7dxvz584UhoUmG4bQBDZx44okSF/1Pf/pTs9KbA/673/2OEFg9zxSgWenhvB4NgNakf//+wl4B0oIG0jgUJZbx2EOCRo0a1SCPcMq0BthYlNipgS6//PKmVWlo0/b3v/+dQJ8BrpQgdmvgkEMOkb2NZrVsCPjEiROJvTub5RHOW6ABmJXBNGru3LkNa5MIOJiNwKuy2267NcwgnLRHA/vvvz9deeWVDSuUCPiMGTOIrVnCmnlD9dl1EgYS4J+DAWSSJAKO9fL99tsvKV04bqEG2FlT1kvQMydJLOAwW0IitphMSheOW6oBcMix9XBi7WIBZ1ch+tGPfkTgQwvilgbAXwfSwiSJBXz27Nny/k5KFI7bq4Gtt95aVkVhhhYnsYCjOwfDYRD3NABS4M0335zgCRQndYCzByP985//JDizBXFTA0zAkB5wgI3RHpiHg7ipAXDAMptlbOXrnnAAzq4tsReHg25oAJTfYICOk1jAwQ8exF0NMFEQweD03//+d10j6gCHVUvYLKnTk3MHYBQBLGulDnCEjQhGirVqcu83U33K/nhtzWMBx6DNJYE3BrvVxlYZljpJc9LYBBkPNsufmawy5qjncvTSsEWslU6AY0qGv+7du9deZ+VvMCPA7YmdGunZZ5+NrSM2gMaMGRN7TsfBpPyZT5V23HHHijvQeeedJ/XEPBmLIxgnbbbZZsSEhaXckAjYA0ulOqn2pwHp6yqrrFJ9yPrvL7/8svChcISi2LpyTJRSyWwb5X/11Verrl27VuoFImEGQHGPJMfANcsePBIMoHKRpi9sy6AOPvjg2tw6OoWxwqiuzNgd2LbTHR5qscUW63QTcwvFECA6iFUnHKuW6Bod9YnLH2XBPAx1q24vOFsg0THmWxXzb4TT0i3AsekoHUP5WgXqqAg8HbFUi2Aw2IGDewwEuzqDBw8mpuUkDh9B7HMux2FahV0fjiggn+ie8B2bAlgBRGOuuOIKuTb6x8S9sn6AGGQRQQE2gTg6AcHMGvLnP/9ZFAwiA9QHm0PVlp7Tp0+X/DHgYfbIhvvKyK82fxy79dZbpY141Zx88smdbj6crxZ0udAFunbdAgow7HrWSfUzP2fOHMXvl+pDhb+/+OKLwiUaEQewjZw6+uij1VNPPSXdGQ96pAwwEPLqnsJv9puSc7xjpxBZ4Le//a10hUgH+guwELOSJB0b4cu5XXfdVaF7RRQCNvVRCJCDP151UgceeKBci7z56RLuV7wKRowYIVQaOMlrz2rQoEESsgJkt6woxTeqpEv6V5s/z3CkDagTBPFaOBBeJTlCYiBfBMZBG8AXDy9QUIrrFr4ZpT01+Xb2HkW8Lt1LqhdccAFts802EiwOd9tNN91EJ510EjGZrNi7Y74IwROBHmbKlCm0wQYbSNwxGGBgijh8+HC55tBDD5XIgbDQrB2BogdA98oBZuRahJri8YgYBMgB/oeyEKSOFU54itGzwO4e3S/MsGHWBZcq5AFLUOadi5LGftbmf+GFFxITHFXKRO8FO7NagZ0grFPQ+zz++ON0zjnn1F5S+DciLiICY610eoejG4DSdQpGz4gOGEkEMOb71QIAEFyu9jiu6dGjR/WlEj4Ss4lq4cGR/IRdNqaVCGbXTKLXFz8FskgBnrkTTjihWbLE85iCYcYQCeoUBzgT6QpLJUDHOAKA//rXv5abMEpb9BP6idpXnVenaRkAx1OuUwAA3tXVdlZ4V0MxWLdHPNBIoKA+ffpEPyufcUqrnIz5gjCUeNKyCNafMdaoFo5LVv2z6Xf0RhiA4QZKKwh5Cd0gCJ5OAeB4ymulE+DozuO6gdpEWX7DAgODE9zBcDWGJwt8m9FdYx7NjBKSHeat8KDAXQ/BjRcxEDLTsByLBiGoY/UNFF2PT5QBfytw0EBwQ+EGgCANuu8o3+g4jvEYQEJbokvn8YUM5hDDtJlU57/nnntK/NJoQIkbGoqPmJeiUXOkYywIwegQ6x7gp9Up0B9eX3VS/VIvYx7OSlasRMV+zDJgwkCGFSzF/vGPfxQmqI6ODsXvbQUqCwiPpmVwg0HbY489ptj8Vn5jYMaACs00N0QiFSJIHGKoIHIhBmcIJMMGHJIPe2IoDlMpYTdmzpwp4aSQDgMlBMMDXTV+82haKKsxkMJvfoXIwJLBknyS/tXmj3Zh0IiBISIdIHAd91iKF34Ud9tCJ478UVf2xpVzvDhTqW9SOXmOJ83DOzFA4G5EHE986hY8CXjCau3k8JTxSLwyoMpbLuqMJxtTuCKC3qhbt25ins2KJizbJsnKK68c+47m4HQSxRjp0a1G8+6kfMo4DqYnDEhrGJ/Gdhq0oXL4g+J0L69CiXECrhiEbS4qUd2L5lO98IT1eQzkkmTWrFl1NzCubUXw26Q6Rccx46huS3S8E+A4iIEHttXCnvi3wGFxxUUBhnvvvXdd1TsN2nAWgC+omTLVpQoHrNcAMASWtVIHOLbVsOUXxG0N4AmP2+auAxzz0TSLFm6ro71rz8vPMuiMNmuqWxsLeJIBXHXC8N1eDQA/PLhxUgc4+DvRpeteYo0rPBwrRwO8diGuYnG51wGO6Q3MlMvYo42rQDimXwMcZEisauJyrgMcF2F3K8lVJS6TcMweDWBxC04IMKOKk1jAsa6Ljfwg7mkADyp2JGEIEieJgOMuSbIEjcsoHLNDA7AKwoZVksQCjl0WdOsc1T4pXThuqQbQM8OSNkliAcfF2Opjq8ukdOG4hRrAYgu2mQcMGJBYu0TAYXAIw4Vozzgxh3DCGg385S9/EbOpRrtziYBjmxF3CixIg7ihAVB2gbqrkSQCjkQwGrz44osbpQ/nLNHAfffdJ6ZVzZg7GgIOUj7YTbOpsSXNCtVI0gCHAiXEQmkmnSxe4i4ObMpxWrHrWBY25aaAB750u8CNq41WvnQUECIixKnZjmPaIyKgWfDyAFEM3udFjQTtUFP71AKvXJhBg/k6hTSPiBBlAnttrM9ywNPoUPg0rAFENYLDBZbB48yZYqqXHnCY68K6FHutKTOPKS8c0qmBUuOWoaIhMqFOuIrllTcyISbrqYVdfRQ/3U3daFNnGC7MrQEOQ6nYMzdr+s7uws3uOfiewc0X8TWqnQCbpQvn9WqAXbLEBA3jqqzSdB4elyEc9eDVUIZfc1x54dj/awAxYOEkAsbrlsQPRx/Co0PVt29fxZvtWbuUcH0BDbDXqzhAMqVJ3lyydenRfYbpGfhQmDKDFi1aFB0OnyVrYNy4cQQf+uOOOy5/SXlvFaTjSb/wiLC/c5FsQtoUGmDrI3E3hkt3Acn3hEe31ymnnCJO58cff3x0KHyWoAF4ksCLFRZI1ZQiuYoqcLdIUmY1ULzao3h7rmhWIX2MBtiQVLEXiWKioZizmQ91JubLc8eAwwWWkrCOAT8L+NWC6NEAqEiGDRsmBEDM4qgl04YGEGlLgMcpCHBAvRXs2dNqrfF1/OwKTw1ivzI1SuOLM5zNNQ9Pyh9mzcy3QmBpYpK7pMvC8SYaANjgogOJEVgm4P6lSRqHk85aCNiDwVwERqRG0fGy5uvT9QAbVqd4PV5//fU6wf5WjZlf+ykScLcuzEn8pKe4OlwSaQCsUTzzUUOGDKkwXUXnNH0Wm5YlPXlcYULsUnCuYYEmSHMNgPkJxMPw7caTzTRnzRPluULTnRObDdNuKmYaFD418LUFidcAEwCq/v37q9GjR6uS9dSRaXs0vrqNj7799tvCXsxEtsJU3Phq/87y06x69eqlJkyY0IrGlw84WoGlVw71oHj6pjiCfSsaZn0ZeF+PHDlSGBtB190iaQ3gUWN4ri4c4Ww5IzdBdNy3T7zqsHoGqk/efGpl81sLOFoGMnhejVMc/kExV3grG2u8LHCxYhSOLtzQUnTrAY+0Pm3aNMU86gqBX7C/3u7CZPtC/MvuW6VEQEipP3OAo4Lozjg6gNzx7LSomPI5Zb3duYx50BW7Xium4VB4pRkWs4BHjefVOenmQTk9efLktni/I1YLm4LJzcyGC0LPHbXX4KcdgEcKQKAZXnwQHvGzzjpLsaFkdMqZTwTa+fnPfy4rjRwZybapqF2AR6iCBJ8jJiimjlTsAiuk+NE5Gz9B0s/WvIqD7CiO3aI4CqFiny8bq2on4JGmMKLHFA7vP0Q6QBgo5jGJThv9xDx6xowZipePFdv4yRSLIzYpGBpaLB1at0fzLO2mTQP+sWuuuUb+QN4PaiqEoQLjQSsI6RlECUSDrV+EyMJuIALMYb8AfDg81UrbFJPXpfctM1nL2rLB9gwrG+y/gyIURHRgHoTvG8I7wmigOnRWbfpmvxFOA3zj2MiI/kCpAese9vgQWizs+yeR3zXL3+B5NwGvVhjMgHAD8PKkgIP9eEQjgt80LHEQcA4uznCcAP8cQnUh7AZAReQfRBhCtCGEjMAnRyyU73CYRMA8sBLD8B83VJGbqLrOBr+7D3iS8uAKhacUXq8RmLgJADIiD2ILFyTCcJ9CILzopmAHC4lo2Ij6KqlMB463L+BJyo8iKA0dOlTMh5Kua9Pjek2cXFDS1KlTpVtHgDwfSQe1WK26AHRUR9BboVvHu5yD10WHvfn0CvB58+ZVgqiDKRquz76JV4AjVDWe7kjYGKNyA0TH2v3TG8CxcALAMY2LBOGWYWzpk3gDOFbqqp9ugIypm29cst4APmnSpNhROYK8R+GefXjSvQAc3TiopREAplawwOKT7XxdsNlahbTD74ULFwoJDtgTIHifQ7p06SL+W1iO9UW8eMJ5j1pAxro5/rbddlvCwgu+A3yfnnAvAPfl6U3TzgB4Gi210TUB8DYCM01TAuBptNRG1wTA2wjMNE3xEnDMvTEl81G8BBwLMNFc3DfQvQTcN5Cr2+sl4OjO29RmrRrb2O9eAo7uPG5dPVZDbXbQS8DbDMNMzQmAZ1KX+xd7CXh4h7t/42ZqQXiHZ1JXuNhlDXjZpYeVNpdv2Rx1DyttOZQWkripgdClu4lb7lp7CXjo0nPfLyGhaxrw8gkPo3TXbtOC9fW5S7fGEeHDDz8UrpaCWKZKztyuBNfh0qIOVNUCxD8gGrJFrKHtAisSsxgKgU7ZyoEDAsBuxZ74vffeS8wa3ZJ2pdDbWGuecCa0k9hngwcPTlFvdy5Be8AOZYt4OWizRfkm6hEAN6F1g2UGwA0q30TRAXATWjdYZgDcoPJNFB0AN6F1g2UGwA0q30TRAXATWjdYZgDcoPJNFB0AN6F1g2UGwA0q30TRAXATWjdYZgDcoPJNFB0AN6F1g2UGwA0q30TRAXATWjdYZgDcoPJNFB0AN6F1g2UGwA0q30TRAXATWjdYZgDcoPJNFB0AN6F1g2UGwA0q30TRAXATWjdYZgDcoPJNFB0AN6F1g2UGwA0q30TRAXATWjdYZgDcoPJNFB0AN6F1g2UGwA0q30TRAXATWjdYZgDcoPJNFG0NAwQ4Xj744AO65557TOihtDI/+eST0vLOk7E1gB977LF09tlnUxQBOE9j0qYB70q/fv2od+/eaZPkvm6ppZaiTTfdNHd63QmtIfXR3bCk/BA6euONN5YIw3fddVfSZe16fKx37/DJkycLg9P9998vr5B2RTapXd4BPmXKFIkbvvjii9O1116bpJe2Pe4V4A888AB9+eWXAuann35Kl1xySdsCm9QwrwC//PLL6bPPPqvoAu/zt956q/Lbhy/eAA7iv6uvvrpTgDqwMV555ZU+4FxpozeA33HHHXURhT///HO69NJLK8rw4Ys3gF922WUUtwjy2muv0UsvveQD1tJGLwD/4osv6LrrrosNIQ0qbZ8Gb9astJX5iC1atIhWXnnlSpeOEfoSSywhq3p4t7eCRrvM9mXJ27uVNigHDMdjxoyRzyzKaoNr/VtpawPQCjXBi3d4IQ21WeIAeJsB2qw5AfBmGmqz814CHuKHt9ld3Kw5IX54Mw2F822jAS+79LZBL0dDAuA5lOZykgC4y+jlqHsAPIfSXE7iJeBhWubyLZuj7mFalkNpIYmbGvCyS3cTKj21DoDr0aMzuQTAnYFKT0W9BByB4jFS91G8BByGixip+yheAu4j0FGbvQQ8dOkR/J58hi7dE6BDM4m86tLxZH/00UfiMgxOmch12KcboW0dEQAmWB5mz55Njz32GD333HO0cOFCAudKjx49CI6EH3/8sXigrLfeetS/f38aNGgQbb/99rT22mu36z0wtu0AnzNnDoHWY8aMGQIivEy23nprWnfddWmdddapm38D9Keffpqef/55uv322+nuu++mlVZaiQ488EA6+OCDabnllmsn8MdiPtoWcsstt6htttlG8ZOqxo8fr95+++3c7WLXYvXLX/5S9ezZUx1//PHqvffey52XZQk7nAd8wYIFavfdd1frr7++Yud+xe9pbTp+9dVX1dFHH61WWGEFxX7kWvPWVslsGbkNOLsACxinnnqq+vrrr7M1PcPVTzzxhNpqq63ULrvsopgiJENK6y51F/CRI0eqNddcUzFPS8u0Onr0aNWnTx/15JNPtqxMzQW5Bzi6bLxXl1lmGcVTK836aJ7drFmzpFfhgV7zi+27osOpeTjrj4YPH04333wzvfPOO7Tsssu2fAQ9dOhQAn3IhhtuKFO9llegYIFOAX7CCScQOFkefPBBWnLJJQs2PX/y3XbbjS644AIhFJg/f37+jAykdIby44YbbqCrrrqK5s2bJ4snBnTVqcijjjpKGB33228/WeBZbLHFOp239YcTCy9vvvmmMBLfdNNNVjETA9S9996bVl99deK5v60YV9fLjZU2vLex+jVu3LjqylvxHWOJDTbYgO677z7itQAr6tSgEvavtDE/qlpttdUUU2/ZN+b9X42wKMNLuNbWr6pi9o/SzzjjDOJpmGxyNLhzjZ7CmvsLL7xAjzzyiNF6pCnc6nc4NjWGDBlCvMTZkkgJaRSWdM2ECRNkuohNG4vFbtqu6dOny65VK8JiFAVp3333JfC5vv/++0WzKjW9tfNwfu/QFVdcQYccckipCtCVOa/80c9+9jNhbNaVZxn5WAs4DBZAiQnjhCyChRBER0qSZ555JvYUDCLwV0R23nlnecqL5FF2WmsBhyHCjjvumLn9UDpoNWvl9ddfl/w22mij2lPy+5xzziH8FRHUF/W2WqqG7FZ9PfTQQ9VFF12UuU4PP/ywYnBj0zFBvuLxQN05JthVa6yxhurbt6/65ptv6s5nObDqqqsq7NFbKvZOy2BylLU7x5O1+eab0yqrrFL3kDGQhOVP2KTXyq233iqmTLB5u/7662tPZ/qNOqPutkp96y2pKaZisEHLIohDttdee9Fhhx1WSQYwd9hhBzrooIPo5JNPrrNpw4WIioBQGLzAQxdeeGElbZ4vsJ3jJzxP0paksRZwGBd269YtkxLwdL388ssV82PcNMOGDSOErgKgAwcOrMsP6/QY5GFZdMSIETLoevHFF+uuS3tg6aWXjo28kDZ92ddZDXhWi1F05WyRUtEZnlY8cdExWLDWeo1OnDiR2GBR0mAKiPM8dqjkkfUL6oyb1VaxFnDYj8fFKMmiSEzBeBBVSYIFnGrA4ZiAJx9722yzJq8DtlQlhLvKO0UD2HjKbRVrAcdCRtEnhUfe9NBDDyW6Bt94440SgxRr4HPnzpU/gI8uHjdCHkGdUXdbxVrA8WS+8cYbmfWGeCZRMLo999xTljqxYgdBYDp4pET5nnfeeYQl0Wphk2cxnTr33HM7xTirvqbRdwS+Q3wVa8XS+aLaf//9FQ+2MlWPu2LFdm5iZDhz5kyZU/PoXPFUTLZYt9hiC7E65YUZsTdnUBR7mKivvvqqUg57raju3buDLUCcESonUn7hMYPiV0nKq1t+WYe1u2WnnXaaOP6deeaZhR8WOBAiuCyrV7ZZ4+bihQvhDPDe79Wrl7wSLDV5sne3DCPq2267TQcO0kXD6BEDwbLARkWxDrDlllvKAo+WipeQibXv8M0220wWMNivq4Rml5MlPFVxo9os1gKOLhiLJlOnTrVZf5W6Yel22rRpBCtWm8VawKG0Aw44QJRoswKjuuH1w65P1vuWWw04thvx5MA82XZhh0YaNWqU7dUkqwGH9k488UQ6/fTTrVYkBmtYrMEc3naxHvB99tlHnvJJkyZZqUuew9MRRxxBZ511lhNBa60HHGvfWO486aSTCFGCbRN4nPTr149++tOf2la1+Pq0fK0nZ4EdHR2KSXcKW6TkLD42GU/DFC+jukQSYK/FS+3tCc9R7HYdeeSRtaeM/H7llVfEhBqvmt69exupQ65CY29dSw+CAIBXzNThhx9utIYMtmJfN8V76UbrkaNw9xggsNHB70wFyg8TwubTsrHC26cmii9apjtdetR9YVMChADYv4arbrQVGp0v85OpwWi77bYj3lGzfkUtSQ/Wj9LjKg6rlDvvvJOYTos22WQTAhlfmYKbCusBbDot3jBwX3ZWivYRptODugu24LBjZzoQrdUBgRA7B4q9Oq8HKJ4Was3fQGbuvcPjlMS2b8LsBOZEXgRRjz76aNxlqY+xmZIYX4DVke3cFXuTpE5r+YX2GkDk6TLhuXn++eeLWTLsyrAYArLcAQMGNOSFYZCEeDfiWmVqLnlXH3PMMbncnfLUvUVp3KD8yKMMZo4Qf22sc4NNefnllxdPFti6w5QY1ikwOHz33Xfp2WeflWMYkOFvjz32kOvzlGt5mvYFvFbx8AaBkwJAxh/229ELrLjiirI0arOlaW1bCvz2B/ACSmqnpPbatLWTlm1qi5PzcJsU6Fpd/g+44RAMWFJbNwAAAABJRU5ErkJggg==\n",
"text/plain": [
"<IPython.core.display.Image object>"
]
},
"execution_count": 25,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"res.visualize()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"(the original `B` node does not appear on its own in Dask's view of this computation; it is \"side-loaded\" by the `combine_idB` node, but that is OK!)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Dynamic Task Graphs <a id=\"dynamic-graphs\"></a>\n",
"Another defining characteristic of \"task Monads\" is that they allow for \"dynamic dependency graphs\", where the information about dependencies between nodes (and even what nodes exist!) is only available \"at run-time\" (as other nodes are executed.\n",
"\n",
"Note that this doesn't mean all nodes' in a given task graph leverage this dynamicism, simply that it is possible.\n",
"\n",
"For example, imagine a workflow that involves performing some computation that outputs a number, and performing some other step that number of times (or using that many partitions); the latter task nodes are only created when execution of their ancestors has completed!\n",
"\n",
"The implications of such dynamicism is examined in the delightful [\"Build Systems a la Carte\" (Mokhov 2019)](https://www.microsoft.com/en-us/research/uploads/prod/2018/03/build-systems-final.pdf), which is well worth a read.\n",
"\n",
"This means that Dask task graphs can be entirely dynamic; does this occur in the wild? It seems doubtful, but certainly something that may be worth making more explicit + streamlined.\n",
"\n",
"Thanks for reading!"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "dask-3.8.1",
"language": "python",
"name": "dask-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": 2
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment