Adverbs.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "ab2f3cc0",
   "metadata": {},
   "source": [
    "# Adverbs\n",
    "\n",
    "K's adverbs, like their namesakes in linguistics, determine _how_ a verb is applied to its arguments. We can think of them as advanced functional looping constructs. If you're familiar with _filter_, _map_ or _reduce_ from other languages, these would be examples of adverbs in k. The adverbs in k tend to be overloaded on argument types, meaning that some care is required when deciphering code. \n",
    "\n",
    "In `ngn/k`, there is a ref-card for adverbs available as `\\'`. The basic adverbs in most ks are _each_ `'`, _reduce_ `/`, _scan_ `\\`, _each-prior_ `/:`, _each-right_ `/:` and _each-left_ `\\:`, but many more are overloaded on the basic set depending on argument types and valence.\n",
    "\n",
    "As types matter so much for this, we'll adopt the following notation, variations of which most ks use in their ref-cards:\n",
    "\n",
    "* <b>[c]</b>har\n",
    "* <b>[i]</b>nt\n",
    "* <b>[n]</b>umber(int|float)\n",
    "* <b>[s]</b>ymbol\n",
    "* <b>[a]</b>tom\n",
    "* <b>[d]</b>ict\n",
    "* <b>[f]</b>unc(monad)\n",
    "* <b>[F]</b>unc(dyad)\n",
    "* <b>[xyz]</b>any\n",
    "\n",
    "In other words, where we write `f'` we mean `'` applying a monad.\n",
    "\n",
    "```{note}\n",
    "As a stylistic choice, we covered some items that are technically adverbs in the verbs chapter:\n",
    "\n",
    "* encode, decode\n",
    "* split, join\n",
    "\n",
    "Whilst they're overloaded on adverb characters, they don't quite fit the linguistic definition of an adverb - something that affects how a verb is applied. Arguably, _window_ and _bin search_ belong in this group, too.\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "73d9eb24",
   "metadata": {},
   "source": [
    "## Each `f'`\n",
    "\n",
    "Arguably the most fundamental of the adverbs is _each_, `f'`. This would be called _map_ in other languages. It returns a vector of the results of applying `f` to every element in the right argument in turn. It follows that `f'x` will have the same length as `x`. For example, let's count the length of each element in a nested list:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "c9f69fe0",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5 2 3 1\n"
     ]
    }
   ],
   "source": [
    "#'(1 2 3 4 5;1 2;7 6 5;,6)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ad21d3e6",
   "metadata": {},
   "source": [
    "## Reduce `F/`, `xF/`"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6df5b5d8",
   "metadata": {},
   "source": [
    "You're most likely familiar with _reduce_, too. In k, it's sometimes also called _over_, or _fold_. Reduce is also available in APL on the same symbol, but a huge advantage for k's version is that it operates left to right, unlike APL's version which operates right to left: k's reduce is a so-called _foldl_. The left to right application of foldl is, for most people, the intuitive behaviour. _Reduce_ is called \"reduce\" because it reduces the rank of the argument by 1. A list is reduced to a scalar. A matrix is reduced to a vector. A cuboid is reduced to a matrix, etc.\n",
    "\n",
    "One way to think of _reduce_ is that it interjects its dyadic verb into the gaps between elements in a list. For example, the sum-reduction"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "3e1dda61",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "36\n"
     ]
    }
   ],
   "source": [
    "+/1 2 3 4 5 6 7 8"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5bcd069e",
   "metadata": {},
   "source": [
    "is equivalent to "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "99e230af",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "36\n"
     ]
    }
   ],
   "source": [
    "1+2+3+4+5+6+7+8"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d77d474c",
   "metadata": {},
   "source": [
    "or -- to be precise -- although there is no difference in this case:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "f039e16c",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "36\n"
     ]
    }
   ],
   "source": [
    "(((((((1+2)+3)+4)+5)+6)+7)+8)    / foldL"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "37cba36e",
   "metadata": {},
   "source": [
    "K's _reduce_ also allows you to seed the accumulator, that is, to start from a different value than the first element:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "ddc7e8ec",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "45\n",
      "144\n"
     ]
    }
   ],
   "source": [
    "+/!10     / unseeded reduce, accumulator starts set to the first value\n",
    "99+/!10   / seeded reduce"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ce79cf72",
   "metadata": {},
   "source": [
    "Another way to think of the seeding is that its prepending the seed to the list before applying the unseeded version:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "772512ba",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "144\n"
     ]
    }
   ],
   "source": [
    "+/99,!10"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "75295698",
   "metadata": {},
   "source": [
    "## Scan `F\\`, `xF\\`"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9bb11b8c",
   "metadata": {},
   "source": [
    "_Scan_ is _reduce_'s brattier little sister. If we think back to reduce we just discussed, _scan_ does the same thing, but instead of returning the final value, it returns the sequence of every intermediate application of `F`. In other words, the last value returned by _scan_ would be the value returned by _reduce_ if applied to the same data. If you're familiar with Python's NumPy, it has a sum-scan primitive built in, called `numpy.cumsum`. In k, we'd say"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "af5bb811",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "55\n",
      "1 3 6 10 15 21 28 36 45 55\n"
     ]
    }
   ],
   "source": [
    "+/1+!10   / sum-reduce\n",
    "+\\1+!10   / sum-scan: note that the last element is the sum-reduction"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e54e11e4",
   "metadata": {},
   "source": [
    "The elements in the sum-scan `+\\x` is simply `x[0]`, `x[0]+x[1]`, `x[0]+x[1]+x[2]`,...etc. The good news is that in k, a scan is as efficient as a reduce, which isn't the case in APL.\n",
    "\n",
    "As with reductions, we can also seed scans in the same way by providing the initial value:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "93c1cac6",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "99 100 102 105 109 114 120 127 135 144\n"
     ]
    }
   ],
   "source": [
    "99+\\!10   / seeded scan"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7be7476b",
   "metadata": {},
   "source": [
    "## Each-prior `F':`, `xF':`"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "140e3ca6",
   "metadata": {},
   "source": [
    "If you think back to _each_ above, it applies a monad to every element in turn. _Each-prior_ applies a dyad to every neighbour pairing."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "id": "18c33ac1",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 3 5 7 9 11 13 15 17\n"
     ]
    }
   ],
   "source": [
    "+':1 2 3 4 5 6 7 8 9     / pair-wise sums"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f20e1d13",
   "metadata": {},
   "source": [
    "The eagle-eyed reader may have spotted that the first element is 1, and that the number of elements in the result is the same as the original argument. Perhaps you would have guessed that it should have started with 3 and have one fewer elements, like the number of panels required for _n_ fence-posts? You're not alone.\n",
    "\n",
    "The first element is assumed to be the dyad applied to the prototypal element and the first element; a sort of initial \"overhang\". In other words, in the example above, the sequence is"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "id": "2868d858",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 3 5 7 9 11 13 15 17\n"
     ]
    }
   ],
   "source": [
    "(0+1;1+2;2+3;3+4;4+5;5+6;6+7;7+8;8+9)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "577ae5ea",
   "metadata": {},
   "source": [
    "Each-prior is an example of a _windowed reduction_. In other words, in this case, we reduce each pairing to an atom.\n",
    "\n",
    "As with _reduce_ and _scan_, _each-prior_ can also be given a seed value, which would be taken as the left argument of the first application (in place of the prototypal element):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "id": "54a835f3",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "10 3 5 7 9 11 13 15 17\n"
     ]
    }
   ],
   "source": [
    "9+':1 2 3 4 5 6 7 8 9"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1e4970a3",
   "metadata": {},
   "source": [
    "## Each-left, each-right `F\\:`, `F/:` "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "87393ca6",
   "metadata": {},
   "source": [
    "K lacks APL's elegant _rank_ operator, `⍤`, but between them, _each-left_ and _each_right_ can do many of the same things. If we have a vector to the left and a vector to the right, _each-left_ allows us to call a dyad with each of the elements to the left, with the whole of the right vector,"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "id": "b2fc3e61",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(10 10\n",
      " 11 11\n",
      " 12 12\n",
      " 13 13)\n"
     ]
    }
   ],
   "source": [
    "1 2 3 4+\\:9 9"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bec13336",
   "metadata": {},
   "source": [
    "In other words, _each_ of the elements to the left, plus the _whole_ of the right, like"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "id": "a3357afb",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(10 10\n",
      " 11 11\n",
      " 12 12\n",
      " 13 13)\n"
     ]
    }
   ],
   "source": [
    "(1+9 9;2+9 9;3+9 9;4+9 9)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a7e4ecb5",
   "metadata": {},
   "source": [
    "_Each-right_ does the same thing, but in the opposite direction. With _each-left_ and _each-right_ you can approximate APL's outer product operator, for example, building a \"times table\" to teach multiplication:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "id": "f1a2c950",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(0 0 0 0 0 0 0 0 0 0 0\n",
      " 0 1 2 3 4 5 6 7 8 9 10\n",
      " 0 2 4 6 8 10 12 14 16 18 20\n",
      " 0 3 6 9 12 15 18 21 24 27 30\n",
      " 0 4 8 12 16 20 24 28 32 36 40\n",
      " 0 5 10 15 20 25 30 35 40 45 50\n",
      " 0 6 12 18 24 30 36 42 48 54 60\n",
      " 0 7 14 21 28 35 42 49 56 63 70\n",
      " 0 8 16 24 32 40 48 56 64 72 80\n",
      " 0 9 18 27 36 45 54 63 72 81 90\n",
      " 0 10 20 30 40 50 60 70 80 90 100)\n"
     ]
    }
   ],
   "source": [
    "(!11)*\\:!11"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "db7802a3",
   "metadata": {},
   "source": [
    "Sometimes you even see _each-left-each-right_ `/:\\:`. Here's a partial example from [Advent of Code, 2021, day 2](https://adventofcode.com/2021/day/2). Let's say we have a vector that lists a sequence of pairs representing direction and magnitude: [[try it]((https://ngn.bitbucket.io/k#eJxLsdLQUErLLypPLEpRsjbVtNZQSskvz4My4RIWIF5pgZK1MUKFBYoKI01NrlwUw6DKQNo06/StYqxSoq0NYjW1wAzDWK5iK2199Vyu4miDWK3iaMNY3eJoo1gAm+ko9w==))]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "id": "b2c3c126",
   "metadata": {
    "tags": [
     "no-link"
    ]
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "((\"forward\";5)\n",
      " (\"down\";5)\n",
      " (\"forward\";8)\n",
      " (\"up\";3)\n",
      " (\"down\";8)\n",
      " (\"forward\";2))\n"
     ]
    }
   ],
   "source": [
    ":d:((\"forward\";5);(\"down\";5);(\"forward\";8);(\"up\";3);(\"down\";8);(\"forward\";2))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d50c082c",
   "metadata": {},
   "source": [
    "We want to convert this to a matrix of magnitudes for each step, with separate rows for the three directions. One way we could do this is:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "id": "f319ad40",
   "metadata": {
    "tags": [
     "no-link"
    ]
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(5 0 8 0 0 2\n",
      " 0 5 0 0 8 0\n",
      " 0 0 0 3 0 0)\n"
     ]
    }
   ],
   "source": [
    ":m:((\"forward\";\"down\";\"up\")~/:\\:d[;0])*\\:d[;1]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a31c339b",
   "metadata": {},
   "source": [
    "The match-each-right-each-left `~/:\\:` matches each element to the left with each element to the right, as if we'd done the following:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "id": "31ac4802",
   "metadata": {
    "tags": [
     "no-link"
    ]
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 0 1 0 0 1\n",
      "0 1 0 0 1 0\n",
      "0 0 0 1 0 0\n"
     ]
    }
   ],
   "source": [
    "\"forward\"~/:d[;0]\n",
    "\"down\"~/:d[;0]\n",
    "\"up\"~/:d[;0]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4e1ab4db",
   "metadata": {},
   "source": [
    "In the matrix `m` above, each column represents a move with a magnitude, where the rows are `forward`, `down` and `up` respectively. The problem now asks us to answer the following:\n",
    "\n",
    "> Calculate the horizontal position and depth you would have after following the planned course. What do you get if you multiply your final horizontal position by your final depth?\n",
    "\n",
    "We can translate that readily to k:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "id": "2aa4b385",
   "metadata": {
    "tags": [
     "no-link"
    ]
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "150\n"
     ]
    }
   ],
   "source": [
    "s:+/'m          / sum each row\n",
    "s[0]*s[1]-s[2]  / forward sum * (down sum - up sum)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c3b4a531",
   "metadata": {},
   "source": [
    "## For `i f/`, `i f\\`"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "14c1f162",
   "metadata": {},
   "source": [
    "K has a rich set of functional looping constructs. Perhaps the simplest one is the `for` loop (APL's _power_ `⍣i`), which calls a monad repeatedly on its own result a set number of times. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "d3a13fd4",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "32\n"
     ]
    }
   ],
   "source": [
    "5 {x*2}/1   / starting with 1, multiply by 2, 5 times: 2*2*2*2*2*1"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d8d7bd17",
   "metadata": {},
   "source": [
    "In naive Python, perhaps you'd written that as\n",
    "\n",
    "```python\n",
    "def power(f, v, count):\n",
    "    for i in range(count):\n",
    "        v = f(v)\n",
    "    return v\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "510c5463",
   "metadata": {},
   "source": [
    "Flip the slash to a backslash, and (as you may have suspected already) you'll get the full sequence of intermediate results:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 72,
   "id": "be09d2f9",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 2 4 8 16 32\n"
     ]
    }
   ],
   "source": [
    "5 {x*2}\\1"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "40c6146d",
   "metadata": {},
   "source": [
    "## While `f f/`, `f f\\`"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9f5854b6",
   "metadata": {},
   "source": [
    "Pass a predicate verb to the left of `f/` and we instead have a _while_ loop. It will repeatedly call the monad on its own result as long as the left argument verb, called on the result, returns non-zero. \n",
    "\n",
    "In Python:\n",
    "\n",
    "```python\n",
    "def whileg(f, v, g):\n",
    "    while g(v):\n",
    "        v = f(v)\n",
    "    return v\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 77,
   "id": "a6c362e4",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "16\n"
     ]
    }
   ],
   "source": [
    "{x<10}{x*2}/1  / starting with 1, multiply by 2 while the value < 10"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bac60991",
   "metadata": {},
   "source": [
    "As with _for_ above, we can get the intermediate values by flipping the slash:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 80,
   "id": "7f36533b",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 2 4 8 16\n"
     ]
    }
   ],
   "source": [
    "{x<10}{x*2}\\1 "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e98ceeeb",
   "metadata": {},
   "source": [
    "## Converge `f/`, `f\\`"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f67e3e3e",
   "metadata": {},
   "source": [
    "If we supply no left argument to `f/` we end up with _converge_. This repeatedly applies the monad f to its result until the result is either the starting value, or the previous value. Note that it's not a good idea to call _converge_ with a function that does not converge."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 84,
   "id": "e57e001a",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1.618033988749895\n"
     ]
    }
   ],
   "source": [
    "{1+1.0%x}/1       / the golden mean"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "154b2a9b",
   "metadata": {},
   "source": [
    "_Converge_, with a backslash, returns the intermediates, too:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 88,
   "id": "d5d7edc9",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(1\n",
      " 2.0\n",
      " 1.5\n",
      " 1.6666666666666665\n",
      " 1.6\n",
      " 1.625\n",
      " 1.6153846153846154\n",
      " 1.619047619047619\n",
      " 1.6176470588235294\n",
      " 1.6181818181818182)\n"
     ]
    }
   ],
   "source": [
    "10#{1+1.0%x}\\1    / first 10 values only              "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0f351801",
   "metadata": {},
   "source": [
    "## Window `i':x`"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9f09f93e",
   "metadata": {},
   "source": [
    "_Window_ produces a sliding window of the specified size, returning a vector of shape `(1-i-#x;i)`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 143,
   "id": "e334ee38",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(0 1 2\n",
      " 1 2 3\n",
      " 2 3 4\n",
      " 3 4 5\n",
      " 4 5 6\n",
      " 5 6 7\n",
      " 6 7 8\n",
      " 7 8 9)\n"
     ]
    }
   ],
   "source": [
    "3':!10"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7bcc1113",
   "metadata": {},
   "source": [
    "This can be handy for doing windowed reductions. The sliding sum length 3 from 0-19:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 144,
   "id": "1485b421",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3 6 9 12 15 18 21 24\n"
     ]
    }
   ],
   "source": [
    "+/'3':!10"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0058a39a",
   "metadata": {},
   "source": [
    "What happens if you use a length 0 window? Well, the result still follows the rule that the shape is `(1-i-#X;i)`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 104,
   "id": "e13c9019",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(!0\n",
      " !0\n",
      " !0\n",
      " !0\n",
      " !0)\n",
      "(\"\"\n",
      " \"\"\n",
      " \"\"\n",
      " \"\"\n",
      " \"\"\n",
      " \"\")\n",
      "(()\n",
      " ()\n",
      " ()\n",
      " ())\n",
      "(()\n",
      " ()\n",
      " ())\n"
     ]
    }
   ],
   "source": [
    "0':1 2 3 4\n",
    "0':\"hello\"\n",
    "0':(1 2 3;4 5 6;7 8 9)\n",
    "0':2 3 5#5"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "333dff8c",
   "metadata": {},
   "source": [
    "## Stencil `i f':`"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "59a7af8f",
   "metadata": {},
   "source": [
    "_Stencil_ is similar to _window_, but it applies the monad to the window. We did a sliding windowed sum above as "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 145,
   "id": "ce0bff10",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3 6 9 12 15 18 21 24\n"
     ]
    }
   ],
   "source": [
    "+/'3':!10   / window, then sum"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9c100195",
   "metadata": {},
   "source": [
    "This can be more efficiently expressed as a _stenciled sum_:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 146,
   "id": "8fee3c00",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3 6 9 12 15 18 21 24\n"
     ]
    }
   ],
   "source": [
    "3+/':!10    / stencil sum"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b8ceb97e",
   "metadata": {},
   "source": [
    "The _stencil_ version avoids having to first generate the windows, and then applying the monad to each of them."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8a7f8b12",
   "metadata": {},
   "source": [
    "## Bin search `X'`"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d0212ca1",
   "metadata": {},
   "source": [
    "_Bin search_ is a binning algorithm -- given a set of ranged bins, it picks the bin corresponding to the arguments. This is what an APLer or NumPyer would call _interval index_. Here's how it works:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 116,
   "id": "274e9189",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3 4 -1\n"
     ]
    }
   ],
   "source": [
    "1 3 5 7 9'8 9 0  / bin 8, 9 and 0 over the intervals 1 3 5 7 9"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9266459e",
   "metadata": {},
   "source": [
    "Consider the gaps between the elements to the left. The first interval is then [1, 3), the second is [3, 5), the third is [5, 7) etc. An element belongs to the bin where it is greater than or equal to the lower end, and less than the upper end. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 117,
   "id": "8deb94a6",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2\n"
     ]
    }
   ],
   "source": [
    "1 3 5 7 9'5      / elements on on boundary goes in the higher bin"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "07318710",
   "metadata": {},
   "source": [
    "Elements smaller than the first bin goes in the -1 bin, which is assumed to cover every number lower than the first bin. Similarly, elements greater than the last bin will end up with a bin number equal to the number of elements (note: not the number of _bins_) to the left:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 118,
   "id": "85760d64",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "-1 3\n"
     ]
    }
   ],
   "source": [
    "3 5 7 9'0 100"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "95830daa",
   "metadata": {},
   "source": [
    "It works for other types, too:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 119,
   "id": "b8fd5bab",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 1 2 2 3 -1 4 3 3 2 0\n"
     ]
    }
   ],
   "source": [
    "\"AEIOU\"'\"HELLO WORLD\""
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7d60f63d",
   "metadata": {},
   "source": [
    "In other words, \"H\" comes on or after \"E\" but not after \"I\", \"E\" is on or after \"E\" etc.\n",
    "\n",
    "Typical use cases for _bin search_ involves various kinds of classification. For example, in the UK, alcoholic beverages are [taxed](https://www.gov.uk/government/publications/uk-trade-tariff-excise-duties-reliefs-drawbacks-and-allowances/uk-trade-tariff-excise-duties-reliefs-drawbacks-and-allowances) based on their _alcohol by volume_ (abv) percentage. Let's consider cider and perry:\n",
    "\n",
    "| Class or description                     | Tax type code | Rate of excise duty/hl |\n",
    "| :---                                     |          ---: |                   ---: |\n",
    "| abv does not exceed 1.2%                 |           431 |                     £0 |\n",
    "| abv exceeding 1.2% but less than 6.9%    |           481 |                 £40.38 |\n",
    "| abv at least 6.9% but not exceeding 7.5% |           487 |                 £50.71 |\n",
    "| abv at least 7.5% but not exceeding 8.5% |           483 |                 £61.04 |"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a6a3d849",
   "metadata": {},
   "source": [
    "Given the following ciders with the associated abv, what are their respective tax code and tax rate per hecto-litre? [[try it](https://ngn.bitbucket.io/k#eJwlT81qwzAYu/spRA5rS8HYy++cW3vbGIXtCZzkI/2omwTb7fPPXg8CIQkJjTyRDwb74mvdNusH8jN+E7k5Xmb8rIGKvjg93D3FcPE882Jdks6ew8YL4pXwaccbxSRe3ITv9RFxvpL3TAFvOL1YcRB2eBq0UqGSNTpZQkklxnUiU5UaVZfRJjTC20gm5ZQsO9RKthqNlqoSju8cg9HyHY38SGW5qBYDL0YfX+YuzYjjfvw/1ucmJLvPO5kcxB/6fkgU)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 137,
   "id": "27894f60",
   "metadata": {
    "tags": [
     "no-link"
    ]
   },
   "outputs": [],
   "source": [
    "ciders: (\"Kopparberg Sparkling Rose\";\"Bulmers Original\";\"Crispin the Jacket\";\"Old Mout Cherries & Berries\")\n",
    "abv: 7.0 4.5 8.3 0.0"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "eb1bea8d",
   "metadata": {},
   "source": [
    "Let's encode the table above into a set of vectors first:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 138,
   "id": "cd2f580b",
   "metadata": {
    "tags": [
     "no-link"
    ]
   },
   "outputs": [],
   "source": [
    "code:431 481 487 486\n",
    "rate:0 40.38 50.71 61.04\n",
    "limits:1.2 6.9 7.5 8.5"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3a0e6d79",
   "metadata": {},
   "source": [
    "Let's find the bins from the limits, and add one to capture the -1 bin appropriately:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 141,
   "id": "7df6987f",
   "metadata": {
    "tags": [
     "no-link"
    ]
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2 1 3 0\n"
     ]
    }
   ],
   "source": [
    ":bin:1+limits'abv"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8632b23a",
   "metadata": {},
   "source": [
    "Now we can lay out a nice table:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 142,
   "id": "4c33fcfb",
   "metadata": {
    "tags": [
     "no-link"
    ]
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "((\"Kopparberg Sparkling Rose\";50.71;487)\n",
      " (\"Bulmers Original\";40.38;481)\n",
      " (\"Crispin the Jacket\";61.04;486)\n",
      " (\"Old Mout Cherries & Berries\";0.0;431))\n"
     ]
    }
   ],
   "source": [
    "+(ciders;rate bin;code bin)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 147,
   "id": "cf760577",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      ": SET      RETURN    '  each|slide|bin\n",
      "+ add      flip      /  fold|join |dec\n",
      "- subtract negate    \\  scan|split|enc\n",
      "* multiply first     ': eachprior\n",
      "% divide   sqrt      /: eachright\n",
      "! mod|dict enum|key  \\: eachleft\n",
      "& min|and  where\n",
      "| max|or   reverse\n",
      "< less     ascend    0: lines i/o\n",
      "> more     descend   1: bytes i/o\n",
      "= equal    group\n",
      "~ match    not\n",
      ", concat   enlist\n",
      "^ without  null\n",
      "# reshape  length\n",
      "_ drop|cut floor\n",
      "$ cast     string    $[c;t;f] COND\n",
      "? find|rnd uniq\n",
      "@ apply(1) type      @[x;i;[f;]y] amend\n",
      ". apply(n) eval      .[x;i;[f;]y] drill\n",
      "grammar:  E:E;e|e e:nve|te| t:n|v v:tA|V n:t[E]|(E)|{E}|N\n"
     ]
    }
   ],
   "source": [
    "\\h"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 148,
   "id": "e4ca9d8c",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\\   help               \\\\         exit\n",
      "\\a  license(AGPLv3)    \\l file.k  load\n",
      "\\0  types              \\t:n expr  time(elapsed milliseconds after n runs)\n",
      "\\+  verbs              \\v         variables\n",
      "\\:  I/O verbs          \\f         functions\n",
      "\\'  adverbs            \\cd path   change directory\n",
      "\\`  symbols            \\other     command(through /bin/sh)\n",
      "\\h  summary\n"
     ]
    }
   ],
   "source": [
    "\\"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 149,
   "id": "144f7710",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "I/O verbs\n",
      "  0:x read  lines\n",
      "x 0:y write lines\n",
      "  1:x read  bytes\n",
      "x 1:y write bytes\n",
      "   <s open          fd:<`\"file.txt\"\n",
      "   >i close         >fd\n",
      "\n",
      "x can be a file descriptor (int) or symbol or string such as\n",
      " \"file.txt\"\n",
      " \"/path/to/file\"\n",
      " \"host:port\"\n",
      " \":port\"         /host defaults to 127.0.0.1\n"
     ]
    }
   ],
   "source": [
    "\\:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 150,
   "id": "f1bb7064",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Special symbols:\n",
      "    `@x serialize    ` 7 8 9 -> 0x020300000000000000070809\n",
      "    `?C deserialize  `?0x020300000000000000070809 -> 7 8 9\n",
      "   `j?C parse json   `j?\"{\\\"a\\\":1,\\\"b\\\":[true,\\\"c\\\"]}\" -> `a`b!(1.0;(1;,\"c\"))\n",
      "   `k@x pretty-print `k(\"ab\";2 3) -> \"(\\\"ab\\\";2 3)\"\n",
      "   `p@C parse k\n",
      " `hex@C hexadecimal  `hex\"ab\" -> \"6162\"\n",
      "   `x@x fork-exec    `x((\"/bin/wc\";\"-l\");\"a\\nbc\\nd\\n\") -> \"3\\n\"\n",
      "   `t[] current time (microseconds)\n",
      "`argv[] list of cmd line args\n",
      " `env[] dict of env variables\n",
      "`prng[] `prng@I get/set pseudo-random number generator internal state\n",
      "                     s:`prng[];r:9?0;`prng s;r~9?0 -> 1\n",
      "        `prng@0 use current time to set state\n",
      " `err@C throw error\n",
      "Special symbols available only in an interpreter built with \"make k-libc\":\n",
      " `sin@N trigonometry `sin 12.34 -> -0.22444212919135995\n",
      " `exp@N exponential  `exp 1 -> 2.7182818284590455\n",
      "  `ln@N logarithm    `ln 2 -> 0.6931471805599453\n"
     ]
    }
   ],
   "source": [
    "\\`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 151,
   "id": "07589f81",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Adverbs:   ' / \\ ': /: \\:\n",
      "   f' each1     #'(\"abc\";3 4 5 6) -> 3 4\n",
      " x F' each2     2 3#'\"ab\" -> (\"aa\";\"bbb\")\n",
      "   X' binsearch 1 3 5 7 9'8 9 0 -> 3 4 -1\n",
      "   F/ fold      +/1 2 3 -> 6\n",
      "   F\\ scan      +\\1 2 3 -> 1 3 6\n",
      " x F/ seeded /  10+/1 2 3 -> 16\n",
      " x F\\ seeded \\  10+\\1 2 3 -> 11 13 16\n",
      " i f/ n-do      5(2*)/1 -> 32\n",
      " i f\\ n-dos     5(2*)\\1 -> 1 2 4 8 16 32\n",
      " f f/ while     (1<){$[2!x;1+3*x;-2!x]}/3 -> 1\n",
      " f f\\ whiles    (1<){$[2!x;1+3*x;-2!x]}\\3 -> 3 10 5 16 8 4 2 1\n",
      "   f/ converge  {1+1.0%x}/1 -> 1.618033988749895\n",
      "   f\\ converges (-2!)\\100 -> 100 50 25 12 6 3 1 0\n",
      "   C/ join      \"ra\"/(\"ab\";\"cadab\";\"\") -> \"abracadabra\"\n",
      "   C\\ split     \"ra\"\\\"abracadabra\" -> (\"ab\";\"cadab\";\"\")\n",
      "   I/ decode    24 60 60/1 2 3 -> 3723   2/1 1 0 1 -> 13\n",
      "   I\\ encode    24 60 60\\3723 -> 1 2 3   2\\13 -> 1 1 0 1\n",
      "  i': window    3'\"abcdef\" -> (\"abc\";\"bcd\";\"cde\";\"def\")\n",
      "i f': stencil   3{x,\".\"}':\"abcde\" -> (\"abc.\";\"bcd.\";\"cde.\")\n",
      "  F': eachprior -':12 13 11 17 14 -> 12 1 -2 6 -3\n",
      "x F': seeded ': 10-':12 13 11 17 14 -> 2 1 -2 6 -3\n",
      "x F/: eachright 1 2*/:3 4 -> (3 6;4 8)\n",
      "x F\\: eachleft  1 2*\\:3 4 -> (3 4;6 8)\n"
     ]
    }
   ],
   "source": [
    "\\'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 152,
   "id": "54ba378e",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Verbs:    : + - * % ! & | < > = ~ , ^ # _ $ ? @ . 0: 1:\n",
      "notation: [c]har [i]nt [n]umber(int|float) [s]ymbol [a]tom [d]ict\n",
      "          [f]unc(monad) [F]unc(dyad) [xyz]any\n",
      "special:  var:y     set    a:1;a -> 1\n",
      "          (v;..):y  unpack (b;(c;d)):(2 3;4 5);c -> 4\n",
      "          :x        return {:x+1;2}[3] -> 4\n",
      "          $[x;y;..] cond   $[0;`a;\"\\0\";`b;`;`c;();`d;`e] -> `e\n",
      "          o[..]     recur  {$[x<2;x;+/o'x-1 2]}9 -> 34\n",
      "          [..]      progn  [0;1;2;3] -> 3\n",
      "\n",
      "::  self      ::12 -> 12\n",
      " :  right     1 :2 -> 2   \"abc\":'\"d\" -> \"ddd\"\n",
      " +x flip      +(\"ab\";\"cd\") -> (\"ac\";\"bd\")\n",
      "N+N add       1 2+3 -> 4 5\n",
      " -N negate    - 1 2 -> -1 -2\n",
      "N-N subtract  1-2 3 -> -1 -2\n",
      " *x first     *`a`b -> `a   *(0 1;\"cd\") -> 0 1\n",
      "N*N multiply  1 2*3 4 -> 3 8\n",
      " %N sqrt      %25 -> 5.0   %-1 -> 0n\n",
      "N%N divide    4 3%2 -> 2 1   4 3%2.0 -> 2.0 1.5\n",
      " !i enum      !3 -> 0 1 2   !-3 -> -3 -2 -1\n",
      " !I odometer  !2 3 -> (0 0 0 1 1 1;0 1 2 0 1 2)\n",
      " !d keys      !`a`b!0 1 -> `a`b\n",
      " !S ns keys   a.b.c:1;a.b.d:2;!`a`b -> ``c`d\n",
      "x!y dict      `a`b!1 2 -> `a`b!1 2\n",
      "i!I div       -10!1234 567 -> 123 56\n",
      "i!I mod       10!1234 567 -> 4 7\n",
      " &I where     &3 -> 0 0 0   &1 0 1 4 2 -> 0 2 3 3 3 3 4 4\n",
      " &x deepwhere &(0 1 0;1 0 0;1 1 1) -> (0 1 2 2 2;1 0 0 1 2)\n",
      "N&N min/and   2&-1 3 -> -1 2   0 0 1 1&0 1 0 1 -> 0 0 0 1\n",
      " |x reverse   |\"abc\" -> \"cba\"   |12 -> 12\n",
      "N|N max/or    2|-1 3 -> 2 3   0 0 1 1|0 1 0 1 -> 0 1 1 1\n",
      " <X ascend    <\"abacus\" -> 0 2 1 3 5 4\n",
      " >X descend   >\"abacus\" -> 4 5 3 1 0 2\n",
      " <s open      fd:<`\"/path/to/file.txt\"\n",
      " >i close     >fd\n",
      "N<N less      0 2<1 -> 1 0\n",
      "N>N more      0 1>0 2 -> 0 0\n",
      " =X group     =\"abracadabra\" -> \"abrcd\"!(0 3 5 7 10;1 8;2 9;,4;,6)\n",
      " =i unitmat   =3 -> (1 0 0;0 1 0;0 0 1)\n",
      "N=N equal     0 1 2=0 1 3 -> 1 1 0\n",
      " ~x not       ~(0 2;``a;\"a \\0\";::;{}) -> (1 0;1 0;0 0 1;1;0)\n",
      "x~y match     2 3~2 3 -> 1   \"4\"~4 -> 0   0~0.0 -> 0\n",
      " ,x enlist    ,0 -> ,0   ,0 1 -> ,0 1   ,`a!1 -> +(,`a)!,,1\n",
      "x,y concat    0,1 2 -> 0 1 2  \"a\",1 -> (\"a\";1)\n",
      " ^x null      ^(\" a\";0 1 0N;``a;0.0 0n) -> (1 0;0 0 1;1 0;0 1)\n",
      "a^y fill      1^0 0N 2 3 0N -> 0 1 2 3 1   \"b\"^\" \" -> \"b\"\n",
      "X^y without   \"abracadabra\"^\"bc\" -> \"araadara\"\n",
      " #x length    #\"abc\" -> 3   #4 -> 1   #`a`b`c!0 1 0 -> 3\n",
      "i#y reshape   3#2 -> 2 2 2\n",
      "I#y reshape   2 3#` -> (```;```)\n",
      "f#y replicate (3>#:')#(0;2 1 3;5 4) -> (0;5 4)   {2}#\"ab\" -> \"aabb\"\n",
      "x#d take      `c`d`f#`a`b`c`d!1 2 3 4 -> `c`d`f!3 4 0N\n",
      " _n floor     _12.34 -12.34 -> 12 -13\n",
      " _c lowercase _\"Ab\" -> \"ab\"\n",
      "i_Y drop      2_\"abcde\" -> \"cde\"   `b_`a`b`c!0 1 2 -> `a`c!0 2\n",
      "I_Y cut       2 4 4_\"abcde\" -> (\"cd\";\"\";,\"e\")\n",
      "f_Y weed out  (3>#:')_(0;2 1 3;5 4) -> ,2 1 3\n",
      "X_i delete    \"abcde\"_2 -> \"abde\"\n",
      " $x string    $(12;\"ab\";`cd;+) -> (\"12\";(,\"a\";,\"b\");\"cd\";,\"+\")\n",
      "i$C pad       5$\"abc\" -> \"abc  \"   -3$\"a\" -> \"  a\"\n",
      "s$y cast      `c$97 -> \"a\"   `i$-1.2 -> -1   `$\"a\" -> `a\n",
      "s$y int       `I$\"-12\" -> -12\n",
      " ?x uniq      ?\"abacus\" -> \"abcus\"\n",
      "X?y find      \"abcde\"?\"bfe\" -> 1 0N 4\n",
      "i?x roll      3?1000 -> 11 398 293   1?0 -> ,-8164324247243690787\n",
      "i?x deal      -3?1000 -> 11 398 293 /guaranteed distinct\n",
      " @x type      @1 -> `b   @\"ab\" -> `C   @() -> `A   @(@) -> `v\n",
      "x@y apply(1)  {x+1}@2 -> 3   \"abc\"@1 -> \"b\"   (`a`b!0 1)@`b -> 1\n",
      " .S get       a:1;.`a -> 1   b.c:2;.`b`c -> 2\n",
      " .C eval      .\"1+2\" -> 3\n",
      " .d values    .`a`b!0 1 -> 0 1\n",
      "x.y apply(n)  {x*y+1}. 2 3 -> 8   (`a`b`c;`d`e`f). 1 0 -> `d\n",
      "\n",
      "@[x;y;f]   amend  @[\"ABC\";1;_:] -> \"AbC\"   @[2 3;1;{-x}] -> 2 -3\n",
      "@[x;y;F;z] amend  @[\"abc\";1;:;\"x\"] -> \"axc\"   @[2 3;0;+;4] -> 6 3\n",
      ".[x;y;f]   drill  .[(\"AB\";\"CD\");1 0;_:] -> (\"AB\";\"cD\")\n",
      ".[x;y;F;z] drill  .[(\"ab\";\"cd\");1 0;:;\"x\"] -> (\"ab\";\"xd\")\n",
      ".[f;y;f]   try    .[+;1 2;\"E:\",] -> 3   .[+;1,`2;\"E:\",] -> \"E:typ\"\n",
      "?[x;y;z]   splice ?[\"abcd\";1 3;\"xyz\"] -> \"axyzd\"\n"
     ]
    }
   ],
   "source": [
    "\\+"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d67b99c4",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "ngn/k",
   "language": "ngnk",
   "name": "ngnk"
  },
  "language_info": {
   "file_extension": ".k",
   "mimetype": "text/ngnk",
   "name": "ngnk"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}