docs/Remove-Function.ipynb

   1 {
   2  "cells": [
   3   {
   4    "cell_type": "markdown",
   5    "id": "0edff064",
   6    "metadata": {},
   7    "source": [
   8     "# `remove`\n",
   9     "\n",
  10     "       [1 2 3 4] 5 remove\n",
  11     "    ------------------------\n",
  12     "          [1 2 3 4]\n",
  13     "\n",
  14     "       [1 2 3 4] 2 remove\n",
  15     "    ------------------------\n",
  16     "          [1 3 4]\n",
  17     "\n",
  18     "       [] a remove\n",
  19     "    ------------------------\n",
  20     "          []\n",
  21     "\n",
  22     "## First attempt\n",
  23     "\n",
  24     "First let's handle the case of an empty list:\n",
  25     "\n",
  26     "    remove == [pop not] [pop] [remove'] ifte\n",
  27     "\n",
  28     "For non-empty lists, the predicate and base case are easy:\n",
  29     "\n",
  30     "    remove' == [swap first =] [pop rest] [R0] [R1] genrec\n",
  31     "\n",
  32     "The recursive branch:\n",
  33     "\n",
  34     "    [1 2 3 4] 3 R0 [remove'] R1\n",
  35     "\n",
  36     "For `R0` use `[uncons] dip`:\n",
  37     "\n",
  38     "    [1 2 3 4] 3 [uncons] dip [remove'] R1\n",
  39     "    [1 2 3 4] uncons 3 [remove'] R1\n",
  40     "    1 [2 3 4] 3 [remove'] R1\n",
  41     "\n",
  42     "For `R1` let's try `i cons`:\n",
  43     "\n",
  44     "    1 [2 3 4] 3 [remove'] i cons\n",
  45     "    1 [2 3 4] 3 remove' cons\n",
  46     "    ...\n",
  47     "    1 2 [3 4] 3 remove' cons cons\n",
  48     "    ...\n",
  49     "    1 2 [4] cons cons\n",
  50     "    ...\n",
  51     "    [1 2 4]\n",
  52     "\n",
  53     "Ergo:\n",
  54     "\n",
  55     "    remove' == [swap first =] [pop rest] [[uncons] dip] [i cons] genrec\n",
  56     "    remove  == [pop not] [pop] [remove'] ifte\n"
  57    ]
  58   },
  59   {
  60    "cell_type": "code",
  61    "execution_count": 1,
  62    "id": "80f0926d",
  63    "metadata": {},
  64    "outputs": [
  65     {
  66      "name": "stdout",
  67      "output_type": "stream",
  68      "text": []
  69     }
  70    ],
  71    "source": [
  72     "[remove' [swap first =] [pop rest] [[uncons] dip] [i cons] genrec] inscribe\n",
  73     "[remo [pop not] [pop] [remove'] ifte] inscribe"
  74    ]
  75   },
  76   {
  77    "cell_type": "code",
  78    "execution_count": 2,
  79    "id": "6ef0d06a",
  80    "metadata": {},
  81    "outputs": [
  82     {
  83      "name": "stdout",
  84      "output_type": "stream",
  85      "text": [
  86       "[1 2 3 4] 3"
  87      ]
  88     }
  89    ],
  90    "source": [
  91     "[1 2 3 4] 3 "
  92    ]
  93   },
  94   {
  95    "cell_type": "code",
  96    "execution_count": 3,
  97    "id": "e0c12f34",
  98    "metadata": {},
  99    "outputs": [
 100     {
 101      "name": "stdout",
 102      "output_type": "stream",
 103      "text": [
 104       "[1 2 4]"
 105      ]
 106     }
 107    ],
 108    "source": [
 109     "remo"
 110    ]
 111   },
 112   {
 113    "cell_type": "markdown",
 114    "id": "e34f9996",
 115    "metadata": {},
 116    "source": [
 117     "So far so good but I made a mistake.  The recursive part doesn't handle empty lists, so it's broken for the case of the item not being in the list:"
 118    ]
 119   },
 120   {
 121    "cell_type": "code",
 122    "execution_count": 4,
 123    "id": "ecb11a12",
 124    "metadata": {},
 125    "outputs": [
 126     {
 127      "name": "stdout",
 128      "output_type": "stream",
 129      "text": [
 130       "[1 2 4] 45"
 131      ]
 132     }
 133    ],
 134    "source": [
 135     "45"
 136    ]
 137   },
 138   {
 139    "cell_type": "code",
 140    "execution_count": null,
 141    "id": "fb6472f5",
 142    "metadata": {},
 143    "outputs": [],
 144    "source": [
 145     " remo"
 146    ]
 147   },
 148   {
 149    "cell_type": "markdown",
 150    "id": "fd33d021",
 151    "metadata": {},
 152    "source": [
 153     "## Second attempt\n",
 154     "\n",
 155     "    remove == [pop not] [pop] [R0] [R1] genrec\n",
 156     "    remove == [pop not] [pop] [R0 [remove] R1] ifte\n",
 157     "\n",
 158     "Non-empty:\n",
 159     "\n",
 160     "    [a b c] item R0 [remove] R1\n",
 161     "\n",
 162     "\n",
 163     "                       R0 [remove] R1\n",
 164     "    -----------------------------------------------------\n",
 165     "       [swap first =] [pop rest] [E1 [remove] E2] ifte\n",
 166     "\n",
 167     "Recursive branch:\n",
 168     "\n",
 169     "    [a b c] d E1 [remove] E2\n",
 170     "\n",
 171     "With:\n",
 172     "\n",
 173     "    E1 == [uncons] dip\n",
 174     "    E2 == i cons\n",
 175     "\n",
 176     "    [a b c] d [uncons] dip [remove] i cons\n",
 177     "    a [b c] d [remove] i cons\n",
 178     "    a [b c] d remove cons\n",
 179     "\n",
 180     "How to make it?\n",
 181     "\n",
 182     "    R0 == [swap first =] [pop rest]\n",
 183     "\n",
 184     "Then we want:\n",
 185     "\n",
 186     "    R1 == [[uncons] dip [remove] i cons] ifte\n",
 187     "\n",
 188     "But of course `[remove]` can't appear in there like that, we have to package it up:\n",
 189     "\n",
 190     "    R1 == [i cons] cons [[uncons] dip] swoncat ifte\n",
 191     "\n",
 192     "Or better yet:\n",
 193     "\n",
 194     "    [[uncons] dip remove cons] ifte\n",
 195     "\n",
 196     "    R1 == [cons] concat [[uncons] dip] swoncat ifte\n",
 197     "\n",
 198     "Clunky, but it works:\n",
 199     "\n",
 200     "    remove == [pop not] [pop] [[swap first =] [pop rest]] [[cons] concat [[uncons] dip] swoncat ifte] genrec\n",
 201     "    "
 202    ]
 203   },
 204   {
 205    "cell_type": "code",
 206    "execution_count": 6,
 207    "id": "891135c8",
 208    "metadata": {},
 209    "outputs": [
 210     {
 211      "name": "stdout",
 212      "output_type": "stream",
 213      "text": [
 214       "[1 2 4] 45"
 215      ]
 216     }
 217    ],
 218    "source": [
 219     "[remo2 [pop not] [pop] [[swap first =] [pop rest]] [[cons] concat [[uncons] dip] swoncat ifte] genrec] inscribe"
 220    ]
 221   },
 222   {
 223    "cell_type": "code",
 224    "execution_count": 7,
 225    "id": "c32ea032",
 226    "metadata": {},
 227    "outputs": [
 228     {
 229      "name": "stdout",
 230      "output_type": "stream",
 231      "text": [
 232       "[1 2 4]"
 233      ]
 234     }
 235    ],
 236    "source": [
 237     "remo2"
 238    ]
 239   },
 240   {
 241    "cell_type": "code",
 242    "execution_count": 8,
 243    "id": "6bd05f5b",
 244    "metadata": {},
 245    "outputs": [
 246     {
 247      "name": "stdout",
 248      "output_type": "stream",
 249      "text": [
 250       "[1 2 4] 2"
 251      ]
 252     }
 253    ],
 254    "source": [
 255     "2"
 256    ]
 257   },
 258   {
 259    "cell_type": "code",
 260    "execution_count": 9,
 261    "id": "20bdec4c",
 262    "metadata": {},
 263    "outputs": [
 264     {
 265      "name": "stdout",
 266      "output_type": "stream",
 267      "text": [
 268       "[1 4]"
 269      ]
 270     }
 271    ],
 272    "source": [
 273     "remo2"
 274    ]
 275   },
 276   {
 277    "cell_type": "markdown",
 278    "id": "7605e056",
 279    "metadata": {},
 280    "source": [
 281     "## Third attempt\n",
 282     "\n",
 283     "What if we let `[remove]` be on the stack instead of building the else-part each iteration?:\n",
 284     "\n",
 285     "    remove == [pop not] [pop] []        [[P] [THEN] [ELSE] ifte] genrec\n",
 286     "    remove == [pop not] [pop] [ [remove] [P] [THEN] [ELSE] ifte] ifte\n",
 287     "\n",
 288     "So:\n",
 289     "\n",
 290     "    [a b c] item [remove] [P] [THEN] [ELSE] ifte\n",
 291     "    \n",
 292     "    P == pop swap first =\n",
 293     "    \n",
 294     "    THEN == popop rest\n",
 295     "    \n",
 296     "    ELSE == ...\n",
 297     "\n",
 298     "Hmm...\n",
 299     "\n",
 300     "    [a b c] item [remove] ELSE\n",
 301     "    [a b c] item [remove] [uncons] dipd i cons\n",
 302     "    a [b c] item [remove] i cons\n",
 303     "    a [b c] item remove cons\n",
 304     "    ...\n",
 305     "    a [b c] cons\n",
 306     "    [a b c]\n",
 307     "\n",
 308     "So:\n",
 309     "\n",
 310     "    ELSE == [uncons] dipd i cons\n",
 311     "\n",
 312     "And:\n",
 313     "\n",
 314     "    remove == [pop not] [pop] [] [[pop swap first =] [popop rest] [[uncons] dipd i cons] ifte] genrec"
 315    ]
 316   },
 317   {
 318    "cell_type": "code",
 319    "execution_count": 10,
 320    "id": "acd3f326",
 321    "metadata": {},
 322    "outputs": [
 323     {
 324      "name": "stdout",
 325      "output_type": "stream",
 326      "text": [
 327       "[1 4]"
 328      ]
 329     }
 330    ],
 331    "source": [
 332     "[remo3 [pop not] [pop] [] [[pop swap first =] [popop rest] [[uncons] dipd i cons] ifte] genrec] inscribe"
 333    ]
 334   },
 335   {
 336    "cell_type": "code",
 337    "execution_count": 11,
 338    "id": "70178b16",
 339    "metadata": {},
 340    "outputs": [
 341     {
 342      "name": "stdout",
 343      "output_type": "stream",
 344      "text": [
 345       "[1 4 5 6]"
 346      ]
 347     }
 348    ],
 349    "source": [
 350     "[5 6] concat"
 351    ]
 352   },
 353   {
 354    "cell_type": "code",
 355    "execution_count": 12,
 356    "id": "f6cb0b12",
 357    "metadata": {},
 358    "outputs": [
 359     {
 360      "name": "stdout",
 361      "output_type": "stream",
 362      "text": [
 363       "[1 4 5 6] 5"
 364      ]
 365     }
 366    ],
 367    "source": [
 368     "5"
 369    ]
 370   },
 371   {
 372    "cell_type": "code",
 373    "execution_count": 13,
 374    "id": "d2e6aeb8",
 375    "metadata": {},
 376    "outputs": [
 377     {
 378      "name": "stdout",
 379      "output_type": "stream",
 380      "text": [
 381       "[1 4 6]"
 382      ]
 383     }
 384    ],
 385    "source": [
 386     "remo3"
 387    ]
 388   },
 389   {
 390    "cell_type": "code",
 391    "execution_count": 14,
 392    "id": "f2c8c0be",
 393    "metadata": {},
 394    "outputs": [
 395     {
 396      "name": "stdout",
 397      "output_type": "stream",
 398      "text": [
 399       "[1 4 6] 5"
 400      ]
 401     }
 402    ],
 403    "source": [
 404     "5"
 405    ]
 406   },
 407   {
 408    "cell_type": "code",
 409    "execution_count": 15,
 410    "id": "deb5e389",
 411    "metadata": {},
 412    "outputs": [
 413     {
 414      "name": "stdout",
 415      "output_type": "stream",
 416      "text": [
 417       "[1 4 6]"
 418      ]
 419     }
 420    ],
 421    "source": [
 422     "remo3"
 423    ]
 424   },
 425   {
 426    "cell_type": "code",
 427    "execution_count": 16,
 428    "id": "84fc4e3f",
 429    "metadata": {},
 430    "outputs": [
 431     {
 432      "name": "stdout",
 433      "output_type": "stream",
 434      "text": [
 435       "[] 5"
 436      ]
 437     }
 438    ],
 439    "source": [
 440     "pop [] 5"
 441    ]
 442   },
 443   {
 444    "cell_type": "code",
 445    "execution_count": 17,
 446    "id": "ee99b894",
 447    "metadata": {},
 448    "outputs": [
 449     {
 450      "name": "stdout",
 451      "output_type": "stream",
 452      "text": [
 453       "[]"
 454      ]
 455     }
 456    ],
 457    "source": [
 458     "remo3"
 459    ]
 460   },
 461   {
 462    "cell_type": "code",
 463    "execution_count": null,
 464    "id": "0518f168",
 465    "metadata": {},
 466    "outputs": [],
 467    "source": []
 468   }
 469  ],
 470  "metadata": {
 471   "kernelspec": {
 472    "display_name": "Joypy",
 473    "language": "",
 474    "name": "thun"
 475   },
 476   "language_info": {
 477    "file_extension": ".joy",
 478    "mimetype": "text/plain",
 479    "name": "Joy"
 480   }
 481  },
 482  "nbformat": 4,
 483  "nbformat_minor": 5
 484 }