Dicts.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "d76bcec6",
   "metadata": {},
   "source": [
    "# Dicts\n",
    "\n",
    "Other resources: [kx docs](https://code.kx.com/q/basics/dictsandtables/), [oK docs](https://github.com/JohnEarnest/ok/blob/gh-pages/docs/Manual.md), [nsl: Lists are Maps](http://nsl.com/papers/m.txt)\n",
    "\n",
    "k has a beautiful dict implementation, which should be the envy of any APLer. A k dict is a key-value lookup table that can map anything to anything. To construct a dict in k, we have several options, the easiest is to join a vector of keys to a vector of values with dyadic `!`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "823b85e6",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "`bob`adam`sue`rita!23 54 12 82\n"
     ]
    }
   ],
   "source": [
    "keys:`bob`adam`sue`rita\n",
    "vals:23 54 12 82\n",
    "keys!vals                         / construct a dict"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d96bdfa6",
   "metadata": {},
   "source": [
    "We can list the keys using `!` and the values with `.`: [[try it](https://ngn.bitbucket.io/k#eJzLTq0stkpIyk9KSExJzE0oLk1NKMosSeQqS8wptjIyVjA1UTA0UrAw4kqxygYqVQSJcymmKBAA+grpqSUKIB1cekQqBppcmloMANwdIj8=)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "59863b6f",
   "metadata": {
    "tags": [
     "no-link"
    ]
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "`bob`adam`sue`rita\n",
      "23 54 12 82\n"
     ]
    }
   ],
   "source": [
    "d:keys!vals\n",
    "!d                                / get keys\n",
    ".d                                / get values"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e31c78f3",
   "metadata": {},
   "source": [
    "and indexing a dict follows the normal k conventions: [[try it](https://ngn.bitbucket.io/k#eJzLTq0stkpIyk9KSExJzE0oLk1NKMosSeQqS8wptjIyVjA1UTA0UrAw4kqxygYqVQSJc6VEgxTGcqU4QBSngCmQGABAuxsm)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "c69ccdbf",
   "metadata": {
    "tags": [
     "no-link"
    ]
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "12\n",
      "82\n",
      "82 12\n"
     ]
    }
   ],
   "source": [
    "d[`sue]\n",
    "d@`rita\n",
    "d`rita`sue"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a555326f",
   "metadata": {},
   "source": [
    "Updating a dict, unlike updating a vector, has upsert semantics: [[try it](https://ngn.bitbucket.io/k#eJwdjFEKwjAQBf9ziucJpGkFyVVE2K27hRCbym4ientrf4eZKfr1RPM2Ewuv5F3JcuPw5qenOOIyYYi4xiCp7Orpz4PcDvEo1PKDFuNa7mlAxIgJwBlr/rRuim1Bfwk3dXAV5OpqbV/8AMbWKLo=)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "28eac4f1",
   "metadata": {
    "tags": [
     "no-link"
    ]
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "`bob`adam`sue`rita`eric`frank!23 2 1 82 3 4\n"
     ]
    }
   ],
   "source": [
    "d[`sue`adam`eric`frank]:1 2 3 4   / mixture of updates and inserts\n",
    "d"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2d606ced",
   "metadata": {},
   "source": [
    "Concatenating dicts also has upsert semantics:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "b4d4bf00",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "`bob`adam`sue`rita`eric`frank!44 99 12 82 66 77\n"
     ]
    }
   ],
   "source": [
    "d1:`bob`adam`sue`rita!23 54 12 82\n",
    "d2:`adam`eric`bob`frank!99 66 44 77\n",
    "d1,d2"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8f09bf9c",
   "metadata": {},
   "source": [
    "Unlike dicts found in many other languages, a dict in k is guaranteed to retain its insertion order. \n",
    "This is a consequence of its implementation: adding an element to a dict appends the key to the key vector,\n",
    "and the value to the value vector."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5e6f968b",
   "metadata": {},
   "source": [
    "This means that we can take and drop items from the beginning and end, for example, taking the last two k-v pairs:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "e456ff65",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "`eric`frank!3 4\n"
     ]
    }
   ],
   "source": [
    "-2#`bob`adam`sue`rita`eric`frank!23 2 1 82 3 4  / take from the end"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "806936ef",
   "metadata": {},
   "source": [
    "As we stated above, both keys and values can be any valid k-type. For example, we frequently need values to be vectors:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "6e23e133",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "`Mon`Tue`Wed`Thu`Fri!(1 4 8 9 4 5;3 6;7 0 0 9;2 8 0 9 9 7 6 7;0 6 2)\n"
     ]
    }
   ],
   "source": [
    "sales:`Mon`Tue`Wed`Thu`Fri!(1 4 8 9 4 5;3 6;7 0 0 9;2 8 0 9 9 7 6 7;0 6 2)\n",
    "sales"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c1206f09",
   "metadata": {},
   "source": [
    "In k, a dictionary is treated like any other vector when it comes to function application. Eaching a monad over a dict applies to the values, but leaves the keys, just like eaching a monad over a vector applies to a vector's _elements_, but leaves its indexes. This can be extraordinarily useful. If we say that the above `sales` dict holds product ids sold each day, how many sales did we make per day? [[try it](https://ngn.bitbucket.io/k/#eJwrTsxJLbZK8M3PSwgpTU0IT01JCMkoTXArylTUMFQwUbBQsASSptbGCmbW5goGQGhpbQQUBdJAaK5gpmBubQAkjTS5lNWLQYYpAADixRTn)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "64065d1d",
   "metadata": {
    "tags": [
     "no-link"
    ]
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "`Mon`Tue`Wed`Thu`Fri!6 2 4 8 3\n"
     ]
    }
   ],
   "source": [
    "#'sales                            / apply monadic # to each value, retaining keys"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3bb86bc5",
   "metadata": {},
   "source": [
    "If we internalise the concept that a dict is just like a vector, but with a different domain, a lot of clever things follow. For example, we know that in k we can find the indexes of 1s in a boolean vector with `&`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "f1b355e2",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 3 4 7\n"
     ]
    }
   ],
   "source": [
    "&1 0 0 1 1 0 0 1 0"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6ff5e777",
   "metadata": {},
   "source": [
    "So what will happen if we apply `&` to a dict with a boolean range?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "e9918fbd",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "`sue`frank\n"
     ]
    }
   ],
   "source": [
    "&`rita`bob`sue`adam`frank!0 0 1 0 1         / get all keys which have a value of 1"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c509fb78",
   "metadata": {},
   "source": [
    "Similarly, we can use `?` -- which for vectors finds the index of the first occurrence of its right argument in its left -- to do a reverse lookup: find the key for a given value:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "4897f991",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "`sue\n"
     ]
    }
   ],
   "source": [
    "(`bob`adam`sue`rita!23 54 12 82)?12         / lookup key by value                                        "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "36958774",
   "metadata": {},
   "source": [
    "If there were several keys holding the same value, we'd only get the _first_ such key. This follows from the behaviour of `?` for vectors, and the fact that dicts retain the insertion ordering. If we wanted ALL matching keys, we could do"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "1d723d66",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "`bob`sue\n"
     ]
    }
   ],
   "source": [
    "&5=`bob`adam`sue`rita!5 1 5 3               / All keys having value 5"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e66fd9de",
   "metadata": {},
   "source": [
    "What happens if we reduce a dict? Again, thinking of a dict as a vector with a range and domain, let's find the max of a dict:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "f6368f05",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "87\n"
     ]
    }
   ],
   "source": [
    "|/`rita`bob`sue`adam`frank!12 7 87 32 11    / find the max value in a dict"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e8a70a17",
   "metadata": {},
   "source": [
    "In other words, reductions (and scans) apply to the _values_ of a dict."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "aea272ea",
   "metadata": {},
   "source": [
    "It should come as no surprise that any function application that makes sense on a vector can also be applied to a dict. Keys odd values? Sure (and thus demonstrating three different meanings of `!`):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "9327828a",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "`b`d`f`h\n"
     ]
    }
   ],
   "source": [
    "&2!`a`b`c`d`e`f`g`h!!8                      / keys of odd values"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "76abfa73",
   "metadata": {},
   "source": [
    "We could apply `filter` directly to the dict, too, which operates on the values:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "db84ef4b",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "`b`d`f`h!1 3 5 7\n"
     ]
    }
   ],
   "source": [
    "(2!)#`a`b`c`d`e`f`g`h!!8                    / filter values"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6f154dfe",
   "metadata": {},
   "source": [
    "The `#` is [special-cased](https://code.kx.com/q/ref/take/#dictionary) for dicts if the left argument is a vector of symbols (or a string in oK and ngn/k), where it becomes `take`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "c792d5c0",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "`b`c!1 2\n"
     ]
    }
   ],
   "source": [
    "`b`c#`a`b`c`d`e`f`g`h!!8                    / take the `b and `c pairs"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b1cda8fe",
   "metadata": {},
   "source": [
    "If you `take` keys that don't exist in the dict, you get a null place-holder, as dictated by the prototype element:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "5acf9f13",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "`b`Q`c!1 0N 2\n"
     ]
    }
   ],
   "source": [
    "`b`Q`c#`a`b`c`d`e`f`g`h!!8                  / take non-existent key `Q gives a 0N as values are ints"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "593382f7",
   "metadata": {},
   "source": [
    "and, as a final spin on `#`, we can `replicate` (ngn/k-specific):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "f2b939c8",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "`b`c`g`h!1 2 6 7\n"
     ]
    }
   ],
   "source": [
    "{0 1 1 0 0 0 1 1}#`a`b`c`d`e`f`g`h!!8       / pick pairs by bool map"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7e8164b4",
   "metadata": {},
   "source": [
    "Perhaps we can now guess how the grades (monadic `<` and `>`) apply to dicts. Grading a vector results in the order by which we'd need to select from the vector in order to sort it. This holds true for dicts, too:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "0e662c9c",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "`c`d`f`e`a`b\n",
      "1 2 4 5 8 9\n"
     ]
    }
   ],
   "source": [
    "dict:`a`b`c`d`e`f!8 9 1 2 5 4\n",
    "<dict                            / grade down\n",
    "dict[<dict]                      / sort by selecting on the grade"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f82620cf",
   "metadata": {},
   "source": [
    "Monadic `=` becomes `group`. If you know APL, this is similar to [key](https://xpqz.github.io/learnapl/key.html) (`⌸`). It takes a vector and creates a mapping from each unique element in order of occurrence to a vector of its indexes of occurrence:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "id": "fe56fec6",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\"a ctsonm\"!(0 3 7 13 16;1 5 9 12 14;,2;4 8 17;,6;,10;,11;,15)\n"
     ]
    }
   ],
   "source": [
    "=\"a cat sat on a mat\""
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6198de8c",
   "metadata": {},
   "source": [
    "`Group` can be applied to any vector, for example"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "id": "f4de7bb4",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 2 3 8 9!(0 2 3 9 10;,1;,4;5 11;6 7 8)\n"
     ]
    }
   ],
   "source": [
    "=1 2 1 1 3 8 9 9 9 1 1 8"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9a907b11",
   "metadata": {},
   "source": [
    "If we instead wanted frequency counts, we can use the `each-length` approach we used before,"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "id": "600ab199",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 2 3 8 9!5 1 1 2 3\n"
     ]
    }
   ],
   "source": [
    "#'=1 2 1 1 3 8 9 9 9 1 1 8             / lengths of groups"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3a2b1d40",
   "metadata": {},
   "source": [
    "When using `group` like this, occasionally there is the need to ensure that all keys from some set are present, defaulting to some value should they not be present in the data. For example, if we're calculating letter frequencies in a paragraph of text, we might want to make sure that any letters that aren't present in the text are still entered into the table, but with a value of 0. Here's one way we can achieve that using the `take` form of `#` and a \"null-fill\" with `^`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "id": "a27565b1",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\"abcdefghijklmnopqrstuvwxyz\"!4 0 0 0 3 1 1 2 1 0 0 0 0 0 1 2 0 3 2 2 0 0 0 1 0 0\n"
     ]
    }
   ],
   "source": [
    "abc:`c$\"a\"+!26                         / generate lower-case alphabet\n",
    "0^abc##'=\"hereisaparagraphoftexts\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "2d785ee0",
   "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
}