hashtables.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "2388b295",
   "metadata": {},
   "source": [
    "# Hash tables in Dyalog APL\n",
    "\n",
    "If you're coming to Dyalog APL from a different programming language, before long you'll probably wonder \"where's the hash table/dict/associative array?\". If you ask around, some seasoned APLer will chirp up with \"you don't need one, we have _arrays_\". \n",
    "\n",
    "<div class=\"alert alert-block alert-info\">\n",
    "As all Real Programmers know, the only useful data structure is the array. Strings, lists, structures, sets -- these are all special cases of arrays and and can be treated that way just as easily without messing up your programing language with all sorts of complications.<p><p>From <a href=\"https://www.ecb.torontomu.ca/~elf/hack/realmen.html\">Real programmers don't use Pascal</a></div>\n",
    "\n",
    "Ultimately, this _is_ true -- with a little bit of legwork, we _can_ achieve much of the same things that Python (say) does with its built-in `dict` using APL arrays.\n",
    "\n",
    "For example:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "id": "c05137bf",
   "metadata": {},
   "outputs": [],
   "source": [
    "keys ← 'bob' 'eric' 'frankie' 'alison' 'jo'\n",
    "vals ←   5      9       6         4      9\n",
    "find ← {vals[keys⍳⍵]}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "id": "4331aade",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<pre class=\"language-APL\">6\n",
       "</pre>"
      ]
     },
     "execution_count": 53,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/html": [
       "<pre class=\"language-APL\">6 9 5\n",
       "</pre>"
      ]
     },
     "execution_count": 53,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "find ⊂'frankie'\n",
    "find 'frankie' 'jo' 'bob'"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "19f5e596",
   "metadata": {},
   "source": [
    "Fair -- but whilst this is an [associative array](https://en.wikipedia.org/wiki/Associative_array), it's not much of a _hash_ table -- there is no actual _hashing_ going on, just a linear search. We _can_ make it a bit hashier by employing a [cute little trick](https://help.dyalog.com/latest/index.htm#Language/Defined%20Functions%20and%20Operators/Search%20Functions%20and%20Hash.htm):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "id": "24fc4fb1",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<pre class=\"language-APL\">6 9 5\n",
       "</pre>"
      ]
     },
     "execution_count": 54,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "keyfind ← keys∘⍳          ⍝ Binding array to ⍳ (or ∊) makes secret hash\n",
    "find ← {vals[keyfind ⍵]}\n",
    "find 'frankie' 'jo' 'bob'"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3ab4d94f",
   "metadata": {},
   "source": [
    "By binding the `keys` array to dyadic iota, we let the interpreter know that we will perform multiple lookups, and the interpreter then creates a hashed lookup table 'behind the scenes'. This means that our hash table is read-only, but sometimes this is what you want.\n",
    "\n",
    "We can be a little bit more flexible by marking arrays for hashing, with [1500⌶](https://help.dyalog.com/latest/index.htm#Language/I%20Beam%20Functions/Hash%20Array.htm):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "id": "86ce70cd",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<pre class=\"language-APL\">6 9 5\n",
       "</pre>"
      ]
     },
     "execution_count": 55,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "keys ← 1500⌶'bob' 'eric' 'frankie' 'alison' 'jo'\n",
    "vals ←        5      9       6         4      9\n",
    "find ← {vals[keys⍳⍵]}\n",
    "find 'frankie' 'jo' 'bob'"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "78bedacd",
   "metadata": {},
   "source": [
    "This tells the interpreter to maintain a hashed index for the `keys` array, meaning that certain operations will be able to do lookups faster (like `⍳` and `∊`). However, it comes with a couple of caveats. If we add elements to the end of the array with `,←`, the hash will be maintained. If we pass the hashed array as an argument to a function, the hash will be maintained. The bad news is that if we do anything else, the hash vanishes. However, that still gives us a pretty decent use case coverage -- we can do lookups and we can add new items to the hash. We can't delete items from, or change items in the key array (perhaps no big surprise there). The `vals` array needn't be hashed, so in our simple hash table we can still do what we want to the values:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "id": "1200585e",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<pre class=\"language-APL\">6\n",
       "</pre>"
      ]
     },
     "execution_count": 56,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/html": [
       "<pre class=\"language-APL\">10\n",
       "</pre>"
      ]
     },
     "execution_count": 56,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "find ⊂'frankie'\n",
    "vals[keys⍳⊂'frankie']←10\n",
    "find ⊂'frankie'"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f9a3e1e4",
   "metadata": {},
   "source": [
    "We can use the `1500⌶` to check the state of the hash table:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "id": "912537dc",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<pre class=\"language-APL\">2\n",
       "</pre>"
      ]
     },
     "execution_count": 57,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "1 (1500⌶) keys"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "97f76615",
   "metadata": {},
   "source": [
    "As per the documentation, a `2` means that the array has a hash table.\n",
    "\n",
    "To add a new item, we need to add the new key to the `keys` array, and the corresponding value to the `vals` array:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "id": "453ae083",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<pre class=\"language-APL\">32\n",
       "</pre>"
      ]
     },
     "execution_count": 58,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/html": [
       "<pre class=\"language-APL\">2\n",
       "</pre>"
      ]
     },
     "execution_count": 58,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "keys ,← ⊂'zach'\n",
    "vals ,← 32\n",
    "find ⊂'zach'\n",
    "1 (1500⌶) keys ⍝ Verify that we still have a hash table: 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "id": "54f433a9",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<pre class=\"language-APL\">┌───┬────┬───────┬──────┬──┬────┐\n",
       "│bob│eric│frankie│alison│jo│zach│\n",
       "└───┴────┴───────┴──────┴──┴────┘\n",
       "</pre>"
      ]
     },
     "execution_count": 59,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/html": [
       "<pre class=\"language-APL\">5 9 10 4 9 32\n",
       "</pre>"
      ]
     },
     "execution_count": 59,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "keys\n",
    "vals"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e3e028e8",
   "metadata": {},
   "source": [
    "This kind of hash table is _insertion order preserving_. As you're only ever adding new items to the end of the `keys` and `vals`, the order of the keys never changes.\n",
    "\n",
    "Hashing with the `1500⌶` certainly makes a bit of difference in terms of performance, but perhaps not as much as one might think. \n",
    "\n",
    "Here's an example. Let's read in the system dictionary (around 235k English words) and use those as our keys, and then look up every single key with `⍳` and measure the difference comparing hashed and unhashed arrays:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "id": "bd5f50ac",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<pre class=\"language-APL\">  _←vals[words1⍳keys] → 1.9E¯2 |   0% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕                \n",
       "  _←vals[words2⍳keys] → 3.1E¯2 | +64% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕\n",
       "</pre>"
      ]
     },
     "execution_count": 60,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "'cmpx'⎕cy'dfns'\n",
    "words1 ← 1500⌶ ⊃⎕NGET'/usr/share/dict/words'1 ⍝ Hashed\n",
    "words2 ← ⊃⎕NGET'/usr/share/dict/words'1       ⍝ Not hashed\n",
    "vals ← ⍳≢words1\n",
    "keys ← ⊖words2 ⍝ Our lookup test. Reverse order \n",
    "cmpx '_←vals[words1⍳keys]' '_←vals[words2⍳keys]'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "id": "f3268de4",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<pre class=\"language-APL\">235976\n",
       "</pre>"
      ]
     },
     "execution_count": 61,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "≢keys"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "52ae8934",
   "metadata": {},
   "source": [
    "A saving of around 10ms. Hashing is worthwhile perhaps on larger arrays, but Dyalog's pretty speedy without, too.\n",
    "\n",
    "In terms of developer ergonomics, we lack a way to \"upsert\" values in this approach. A nice thing with Python-style dicts is that if you assign to a non-present key, it will be added to the dict, and if the key is present, the value will be updated:\n",
    "\n",
    "```python\n",
    "Python 3.11.2 (main, May  2 2023, 15:12:41) [Clang 14.0.3 (clang-1403.0.22.14.1)] on darwin\n",
    "Type \"help\", \"copyright\", \"credits\" or \"license\" for more information.\n",
    ">>> d = {}\n",
    ">>> d[\"bob\"] = 1\n",
    ">>> d[\"eric\"] = 2\n",
    ">>> d[\"bob\"] = 3\n",
    ">>> d\n",
    "{'bob': 3, 'eric': 2}\n",
    "```\n",
    "We can \"upsert\" by first checking if a key is present, and if so, just update the corresponding item in the values array."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 108,
   "id": "eb34682a",
   "metadata": {},
   "outputs": [],
   "source": [
    "]dinput\n",
    "upsert ← {\n",
    "    ⍝ 'upsert' -- for keys already present, update values.\n",
    "    ⍝             for keys not present, append to key and val array\n",
    "    ⍝\n",
    "    ⍝ ⍺ keys \n",
    "    ⍝ ⍵ values\n",
    "    ⍝ \n",
    "    ⍝ Restriction: the keys in ⍺ must be unique\n",
    "    \n",
    "    idx ← keys⍳⊆⍺\n",
    "    k ← idx≠⎕IO+≢keys\n",
    "    \n",
    "    values[k/idx] ← k/⍵ ⍝ Update\n",
    "    \n",
    "    ⍝ Any new kv-pairs: add at the end\n",
    "    keys,←(~k)/⊆⍺\n",
    "    values,←(~k)/⍵\n",
    "    ⍬\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5c40927d",
   "metadata": {},
   "source": [
    "## Namespaces as hash tables\n",
    "\n",
    "What else can we do? Well, the intrepid Dyaloger will have noted the conceptual similarity between namespaces and lookup tables. Can we use namespaces as hash tables? Sort of. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 79,
   "id": "9d2f9ac7",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<pre class=\"language-APL\">6\n",
       "</pre>"
      ]
     },
     "execution_count": 79,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a←⎕NS⍬\n",
    "a.(bob eric frankie alison jo) ← 5 9 6 4 9\n",
    "a.frankie"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4bed4853",
   "metadata": {},
   "source": [
    "Now that _is_ pretty nice! We can add a couple of helper functions to give the illusion that namespaces are hash-like:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 80,
   "id": "bdac0d0a",
   "metadata": {},
   "outputs": [],
   "source": [
    "Keys←{⍵.⎕NL ¯2}\n",
    "Vals←{⍵.(⍎¨⎕NL ¯2)}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 81,
   "id": "3a390e6a",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<pre class=\"language-APL\">┌──────┬───┬────┬───────┬──┐\n",
       "│alison│bob│eric│frankie│jo│\n",
       "└──────┴───┴────┴───────┴──┘\n",
       "</pre>"
      ]
     },
     "execution_count": 81,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/html": [
       "<pre class=\"language-APL\">4 5 9 6 9\n",
       "</pre>"
      ]
     },
     "execution_count": 81,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Keys a\n",
    "Vals a"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "dc0630d3",
   "metadata": {},
   "source": [
    "Unfortunately, there is no particularly nice way yet to set variables in a namespace from character vectors. Here's one way we can try:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 106,
   "id": "9f6396d7",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<pre class=\"language-APL\">¯1\n",
       "</pre>"
      ]
     },
     "execution_count": 106,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "'alison' 'eric' 'bob' a.{⍎(∊⍺,¨' '),'←⍵'} ¯1 ¯2 ¯3\n",
    "a.alison"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0491fcfc",
   "metadata": {},
   "source": [
    "but evaluating strings comes with its own set of complications. For example,"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 76,
   "id": "95046122",
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "⍎VALUE ERROR: Undefined name: Jean\n",
      "      Jean-Pierre←⍵\n",
      "      ∧\n"
     ]
    }
   ],
   "source": [
    "'Jean-Pierre' 'Jean-Christophe' 'D''Artagnan' (a.{⍎⍺,'←⍵'})¨ 9 8 10 ⍝ VALUE ERROR"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7617988c",
   "metadata": {},
   "source": [
    "In order to be safe, we'd need to encode strings in some way to ensure that they're valid APL names before putting them into a namespace. Fortunately, there is a handy I-beam function we can use for that, [7162⌶](https://help.dyalog.com/latest/index.htm#Language/I%20Beam%20Functions/JSON%20Translate%20Name.htm) -- it's used by `⎕JSON` which faces the same issue when converting JSON-data to Dyalog namespaces. \n",
    "\n",
    "Let's put that into action with a getter-setter pair of helper routines:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 94,
   "id": "3084cde2",
   "metadata": {},
   "outputs": [],
   "source": [
    "_Set ← {⍺⍺⍎'←⍵',⍨∊' ',¨⍨0(7162⌶)¨⊆⍺} \n",
    "Get ← {⍺⍎¨0(7162⌶)¨⍵}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bf547a39",
   "metadata": {},
   "source": [
    "Here's how they work:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 95,
   "id": "ff8cdad0",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<pre class=\"language-APL\">1 4 6\n",
       "</pre>"
      ]
     },
     "execution_count": 95,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a←⎕NS⍬\n",
    "'aaa' 'bbb' 'ccc' 'jean-pierre' 'b+c' 'a/d' (a _Set) 1 2 3 4 5 6\n",
    "a Get 'aaa' 'jean-pierre' 'a/d'"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2c5b7e95",
   "metadata": {},
   "source": [
    "Unfortunately, we still have a problem. If we try to set a large number of keys, we run into limitations of `⍎`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 93,
   "id": "1cc1877c",
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "LIMIT ERROR\n",
      "_Set[0] _Set←{⍺⍺⍎'←⍵',⍨∊' ',¨⍨0(7162⌶)¨⍺}\n",
      "                ∧\n"
     ]
    }
   ],
   "source": [
    "a←⎕NS⍬\n",
    "words2 (a _Set) vals ⍝ LIMIT ERROR"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "20e2c57e",
   "metadata": {},
   "source": [
    "This is an internal limitation that a Dyalog function can comprise of no more than 4095 \"tokens\". Our tokens, in this case, are our keys to the left, and then two more, for the `←⍵` bit of the evaluation. We need to 'chunk' our data into sizes less than 4093. Let's use 4000, a nice, round number:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 96,
   "id": "75390e88",
   "metadata": {},
   "outputs": [],
   "source": [
    "]dinput\n",
    "_Set ← {⎕IO←0\n",
    "    ch ← 0=4000|⍳≢⊆⍺                       \n",
    "    _sset ← {⍺⍺⍎'←⍵',⍨∊' ',¨⍨0(7162⌶)¨⊆⍺}  \n",
    "    (⍺⍺ _sset)⌿¨↓⍉↑(ch⊂⍺)(ch⊂⍵)            \n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "56c9a576",
   "metadata": {},
   "source": [
    "Now we should be able to avoid the limit error, but with our ~235k token data set, it's a bit slow."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 99,
   "id": "3bd81f6c",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<pre class=\"language-APL\">\n",
       "* Benchmarking \"words2 (a _Set) vals\"\n",
       "┌──────────┬─────┐\n",
       "│          │(ms) │\n",
       "├──────────┼─────┤\n",
       "│CPU (avg):│14617│\n",
       "├──────────┼─────┤\n",
       "│Elapsed:  │14617│\n",
       "└──────────┴─────┘\n",
       "</pre>"
      ]
     },
     "execution_count": 99,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a←⎕NS⍬\n",
    "]runtime \"words2 (a _Set) vals\""
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2f37f4f8",
   "metadata": {},
   "source": [
    "## .NET Collections\n",
    "\n",
    "What about pulling in a hash table from .NET? .NET has a superb set of collections. Let's try the aptly named `Hashtable`. It's nicely ergonomic, and can be indexed directly with strings, even in APL:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 100,
   "id": "1791661c",
   "metadata": {},
   "outputs": [],
   "source": [
    "⎕USING ← 'System.Collections'\n",
    "ht ← ⎕NEW Hashtable\n",
    "{ht.Add ⍵}¨↓⍉↑words2 vals ⍝ Quick"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6015e28a",
   "metadata": {},
   "source": [
    "## Keyed properties\n",
    "\n",
    "Most things C# can do, we can also do in Dyalog. We can actually write a dictionary-like class that is indexable directly using strings, just like the .NET example above, using what's known as a \"keyed property\":"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 133,
   "id": "f5bb7285",
   "metadata": {},
   "outputs": [],
   "source": [
    "]dinput\n",
    ":Class Dict\n",
    "    ⍝ )ed ○ Dict\n",
    "    :Field Public _keys←(1500⌶)⍬\n",
    "    :Field Public _values←⍬\n",
    "\n",
    "    :Property Keyed Default Item\n",
    "        :Access Public Instance\n",
    "\n",
    "        ∇ r←get arg\n",
    "            r←_values[_keys⍳⊃arg.Indexers]\n",
    "        ∇\n",
    "\n",
    "        ∇ set arg;unique;kk;vv;seen\n",
    "            unique ← ≠⊃arg.Indexers\n",
    "            kk ← unique/⊃arg.Indexers\n",
    "            vv ← unique/arg.NewValue\n",
    "            seen ← kk∊_keys\n",
    "            (seen/_values)←seen/vv\n",
    "            _keys,←(~seen)/kk\n",
    "            _values,←(~seen)/vv\n",
    "        ∇\n",
    "\n",
    "    :EndProperty\n",
    "\n",
    "    ∇ Make(keys values)\n",
    "        :Access Public\n",
    "        :Implements Constructor\n",
    "\n",
    "        (_keys _values)←keys values\n",
    "    ∇\n",
    ":EndClass"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 132,
   "id": "0fbf97ec",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<pre class=\"language-APL\">┌───┬──┬──┐\n",
       "│Bob│42│42│\n",
       "└───┴──┴──┘\n",
       "</pre>"
      ]
     },
     "execution_count": 132,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "z←⎕NEW Dict (('APL' 'Rocks!')(42 'Bob'))\n",
    "z['Rocks!' 'APL' 'APL'] "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e1b71efc",
   "metadata": {},
   "source": [
    "Let's load up that big word list and compare what we have tried so far:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 134,
   "id": "1914c0fc",
   "metadata": {},
   "outputs": [],
   "source": [
    "z←⎕NEW Dict (words2 vals)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 135,
   "id": "46155643",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<pre class=\"language-APL\">  ≢ht[keys]          → 5.9E¯1 |   0% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕\n",
       "  ≢a Get keys        → 2.6E¯1 | -57% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕                       \n",
       "  ≢vals[words1⍳keys] → 1.9E¯2 | -97% ⎕                                       \n",
       "  ≢z[keys]           → 3.4E¯2 | -95% ⎕⎕                                      \n",
       "</pre>"
      ]
     },
     "execution_count": 135,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "cmpx '≢ht[keys]' '≢a Get keys' '≢vals[words1⍳keys]' '≢z[keys]'"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1b917e6e",
   "metadata": {},
   "source": [
    "So our orignal attempt using arrays is still the fastest, and -- perhaps surprisingly -- the .NET approach the slowest. The guts of our keyed property class is the same as our original 'hashed array', so it should come as no surprise that they are pretty much identical in terms of performance.\n",
    "\n",
    "## dfns alist\n",
    "\n",
    "There is a set of [association list functions](https://dfns.dyalog.com/n_alists.htm) in the dfns workspace. They're simple, but nicely put together. An assoication list is a 2-element vector, where the first element is a vector of keys, and the second element is a vector of the corresponding keys:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 109,
   "id": "1e9d32cd",
   "metadata": {},
   "outputs": [],
   "source": [
    "'alpush' 'alpop' 'alset' 'alget'⎕cy'dfns'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 110,
   "id": "ee6089f4",
   "metadata": {},
   "outputs": [],
   "source": [
    "alist ← ('bob' 'eric' 'frankie' 'alison' 'jo')(5 9 6 4 9)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e0ccb60e",
   "metadata": {},
   "source": [
    "To retrieve the value corresponding to a particular key, we use `alget`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 113,
   "id": "c08b60f3",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<pre class=\"language-APL\">6\n",
       "</pre>"
      ]
     },
     "execution_count": 113,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "alist alget 'frankie'"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "56da42b5",
   "metadata": {},
   "source": [
    "Note that `alget` only operates on single keys -- we can't retrieve multiple values by feeding it a vector of keys:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 115,
   "id": "bf103585",
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "INDEX ERROR\n",
      "alget[2] (keys⍳⊂⍵)⊃vals      ⍝ :: val ← list ∇ key\n",
      "                  ∧\n"
     ]
    }
   ],
   "source": [
    "alist alget 'frankie' 'jo' ⍝ INDEX ERROR"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3e03ae40",
   "metadata": {},
   "source": [
    "To put another key-value pair onto our association list, we use `alpush`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 116,
   "id": "b2cee73a",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<pre class=\"language-APL\">┌─────────────────────────────────┬────────────┐\n",
       "│┌────┬───┬────┬───────┬──────┬──┐│32 5 9 6 4 9│\n",
       "││zach│bob│eric│frankie│alison│jo││            │\n",
       "│└────┴───┴────┴───────┴──────┴──┘│            │\n",
       "└─────────────────────────────────┴────────────┘\n",
       "</pre>"
      ]
     },
     "execution_count": 116,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "⊢alist ← alist alpush 'zach' 32"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "103fe0e2",
   "metadata": {},
   "source": [
    "Note that `alpush` adds new items to the beginning of the vectors holding keys and values. `alset` modifies the value of an existing key:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 119,
   "id": "31097705",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<pre class=\"language-APL\">┌─────────────────────────────────┬────────────┐\n",
       "│┌────┬───┬────┬───────┬──────┬──┐│32 5 9 2 4 9│\n",
       "││zach│bob│eric│frankie│alison│jo││            │\n",
       "│└────┴───┴────┴───────┴──────┴──┘│            │\n",
       "└─────────────────────────────────┴────────────┘\n",
       "</pre>"
      ]
     },
     "execution_count": 119,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "⊢alist ← alist alset 'frankie' 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 118,
   "id": "27ce226b",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<pre class=\"language-APL\">┌─────────────────────────────────┬────────────┐\n",
       "│┌────┬───┬────┬───────┬──────┬──┐│32 5 9 2 4 9│\n",
       "││zach│bob│eric│frankie│alison│jo││            │\n",
       "│└────┴───┴────┴───────┴──────┴──┘│            │\n",
       "└─────────────────────────────────┴────────────┘\n",
       "</pre>"
      ]
     },
     "execution_count": 118,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "alist"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a3182448",
   "metadata": {},
   "source": [
    "The final function is `alpop` -- it _removes_ the specified key-value pair, returning the value and the resulting list:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 120,
   "id": "2817ea7b",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<pre class=\"language-APL\">┌─┬─────────────────────────────────────────┐\n",
       "│9│┌────────────────────────────┬──────────┐│\n",
       "│ ││┌────┬───┬───────┬──────┬──┐│32 5 2 4 9││\n",
       "│ │││zach│bob│frankie│alison│jo││          ││\n",
       "│ ││└────┴───┴───────┴──────┴──┘│          ││\n",
       "│ │└────────────────────────────┴──────────┘│\n",
       "└─┴─────────────────────────────────────────┘\n",
       "</pre>"
      ]
     },
     "execution_count": 120,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "⊢(eric_val alist) ← alist alpop 'eric'"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7fbb3419",
   "metadata": {},
   "source": [
    "Sadly, there is no `alupsert` function that would modify an existing value if a key is present, and otherwise add a new key-value pair. We can, of course, write one ourselves:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 121,
   "id": "1ef7ce30",
   "metadata": {},
   "outputs": [],
   "source": [
    "alupsert←{(k v)←⍵⋄3::⍺ alpush k v⋄⍺ alset k v} ⍝ Modify if present"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 122,
   "id": "bd63fc8f",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<pre class=\"language-APL\">┌──────────────────────────────────────┬────────────┐\n",
       "│┌─────────┬────┬───┬───────┬──────┬──┐│8 32 5 2 4 9│\n",
       "││æthelflæd│zach│bob│frankie│alison│jo││            │\n",
       "│└─────────┴────┴───┴───────┴──────┴──┘│            │\n",
       "└──────────────────────────────────────┴────────────┘\n",
       "</pre>"
      ]
     },
     "execution_count": 122,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/html": [
       "<pre class=\"language-APL\">┌──────────────────────────────────────┬─────────────┐\n",
       "│┌─────────┬────┬───┬───────┬──────┬──┐│8 32 5 ¯1 4 9│\n",
       "││æthelflæd│zach│bob│frankie│alison│jo││             │\n",
       "│└─────────┴────┴───┴───────┴──────┴──┘│             │\n",
       "└──────────────────────────────────────┴─────────────┘\n",
       "</pre>"
      ]
     },
     "execution_count": 122,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "⊢alist ← alist alupsert 'æthelflæd' 8\n",
    "⊢alist ← alist alupsert 'frankie' ¯1"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d7ed7d3e",
   "metadata": {},
   "source": [
    "The way this structure is defined is very neat -- completely immutable, much closer in spirit to an Erlang [dict](https://www.erlang.org/doc/man/dict.html) than the Python equivalent. Any modifying operation returns a copy of the original with the change applied. In comparison, all the other things we've done are mutable -- we change things in place. Of course, always returning a copy has a cost associated with it. In functional languages like Erlang where immutability is the norm, returning copies of things doesn't actually copy much data. In Dyalog we have to pay the price if we want to do frequent modifications of a large association list. Also, as we can only pick a single item at a time, our \"big data\" retrieval test is somewhat disappointing:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 124,
   "id": "8908b71e",
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "INTERRUPT"
     ]
    }
   ],
   "source": [
    "alist ← words2 vals\n",
    "]runtime \"alist∘alget¨keys\" ⍝ Manually interrupted after several minutes out of boredom"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ec37af8e",
   "metadata": {},
   "source": [
    "As they stand, the `al*` routines in the dfns ws are nicely ergonomic for small data sets, perhaps as a way to store the contents of some kind of structured configuration file, but they're probably not the best choice for large data sets and frequent access or modification."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3f1c9594",
   "metadata": {},
   "source": [
    "\n",
    "## Wrapping up\n",
    "\n",
    "We all occasionally need to map keys to values, and whilst Dyalog does not come with a native dictionary type, we've explored several ways by which we can achieve the same thing."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "879bf376",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Dyalog APL",
   "language": "apl",
   "name": "dyalog-kernel"
  },
  "language_info": {
   "file_extension": ".apl",
   "mimetype": "text/apl",
   "name": "APL"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}