{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Treating Trees II: `treestep`\n",
    "Let's consider a tree structure, similar to one described [\"Why functional programming matters\" by John Hughes](https://www.cs.kent.ac.uk/people/staff/dat/miranda/whyfp90.pdf), that consists of a node value followed by zero or more child trees.  (The asterisk is meant to indicate the [Kleene star](https://en.wikipedia.org/wiki/Kleene_star).)\n",
    "\n",
    "    tree = [] | [node tree*]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In the spirit of `step` we are going to define a combinator `treestep` which expects a tree and three additional items: a base-case function `[B]`, and two quoted programs `[N]` and `[C]`.\n",
    "\n",
    "    tree [B] [N] [C] treestep"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If the current tree node is empty then just execute `B`:\n",
    "\n",
    "       [] [B] [N] [C] treestep\n",
    "    ---------------------------\n",
    "       []  B"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Otherwise, evaluate `N` on the node value, `map` the whole function (abbreviated here as `K`) over the child trees recursively, and then combine the result with `C`.\n",
    "\n",
    "       [node tree*] [B] [N] [C] treestep\n",
    "    --------------------------------------- w/ K == [B] [N] [C] treestep\n",
    "           node N [tree*] [K] map C\n",
    "\n",
    "(Later on we'll experiment with making `map` part of `C` so you can use other combinators.)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Derive the recursive function.\n",
    "We can begin to derive it by finding the `ifte` stage that `genrec` will produce.\n",
    "\n",
    "    K == [not] [B] [R0]   [R1] genrec\n",
    "      == [not] [B] [R0 [K] R1] ifte\n",
    "\n",
    "So we just have to derive `J`:\n",
    "\n",
    "    J == R0 [K] R1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The behavior of `J` is to accept a (non-empty) tree node and arrive at the desired outcome.\n",
    "\n",
    "           [node tree*] J\n",
    "    ------------------------------\n",
    "       node N [tree*] [K] map C"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So `J` will have some form like:\n",
    "\n",
    "    J == ... [N] ... [K] ... [C] ..."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's dive in.  First, unquote the node and `dip` `N`.\n",
    "\n",
    "    [node tree*] uncons [N] dip\n",
    "    node [tree*]        [N] dip\n",
    "    node N [tree*]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Next, `map` `K` over the child trees and combine with `C`.\n",
    "\n",
    "    node N [tree*] [K] map C\n",
    "    node N [tree*] [K] map C\n",
    "    node N [K.tree*]       C"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So:\n",
    "\n",
    "    J == uncons [N] dip [K] map C"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Plug it in and convert to `genrec`:\n",
    "\n",
    "    K == [not] [B] [J                       ] ifte\n",
    "      == [not] [B] [uncons [N] dip [K] map C] ifte\n",
    "      == [not] [B] [uncons [N] dip]   [map C] genrec"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Extract the givens to parameterize the program.\n",
    "Working backwards:\n",
    "\n",
    "    [not] [B]          [uncons [N] dip]                  [map C] genrec\n",
    "    [B] [not] swap     [uncons [N] dip]                  [map C] genrec\n",
    "    [B]                [uncons [N] dip] [[not] swap] dip [map C] genrec\n",
    "                                        ^^^^^^^^^^^^^^^^\n",
    "    [B] [[N] dip]      [uncons] swoncat [[not] swap] dip [map C] genrec\n",
    "    [B] [N] [dip] cons [uncons] swoncat [[not] swap] dip [map C] genrec\n",
    "            ^^^^^^^^^^^^^^^^^^^^^^^^^^^"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Extract a couple of auxiliary definitions:\n",
    "\n",
    "    TS.0 == [[not] swap] dip\n",
    "    TS.1 == [dip] cons [uncons] swoncat"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "    [B] [N] TS.1 TS.0 [map C]                         genrec\n",
    "    [B] [N]           [map C]         [TS.1 TS.0] dip genrec\n",
    "    [B] [N] [C]         [map] swoncat [TS.1 TS.0] dip genrec\n",
    "\n",
    "The givens are all to the left so we have our definition."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### (alternate) Extract the givens to parameterize the program.\n",
    "Working backwards:\n",
    "\n",
    "    [not] [B]           [uncons [N] dip]            [map C] genrec\n",
    "    [not] [B] [N]       [dip] cons [uncons] swoncat [map C] genrec\n",
    "    [B] [N] [not] roll> [dip] cons [uncons] swoncat [map C] genrec\n",
    "            ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Define `treestep`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from notebook_preamble import D, J, V, define, DefinitionWrapper"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "DefinitionWrapper.add_definitions('''\n",
    "\n",
    "    _treestep_0 == [[not] swap] dip\n",
    "    _treestep_1 == [dip] cons [uncons] swoncat\n",
    "    treegrind == [_treestep_1 _treestep_0] dip genrec\n",
    "    treestep == [map] swoncat treegrind\n",
    "\n",
    "''', D)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Examples\n",
    "Consider trees, the nodes of which are integers.  We can find the sum of all nodes in a tree with this function:\n",
    "\n",
    "    sumtree == [pop 0] [] [sum +] treestep"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "define('sumtree == [pop 0] [] [sum +] treestep')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Running this function on an empty tree value gives zero:\n",
    "\n",
    "       [] [pop 0] [] [sum +] treestep\n",
    "    ------------------------------------\n",
    "               0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0\n"
     ]
    }
   ],
   "source": [
    "J('[] sumtree')  # Empty tree."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Running it on a non-empty node:\n",
    "\n",
    "    [n tree*]  [pop 0] [] [sum +] treestep\n",
    "    n [tree*] [[pop 0] [] [sum +] treestep] map sum +\n",
    "    n [ ... ]                                   sum +\n",
    "    n m                                             +\n",
    "    n+m\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "23\n"
     ]
    }
   ],
   "source": [
    "J('[23] sumtree')  # No child trees."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "23\n"
     ]
    }
   ],
   "source": [
    "J('[23 []] sumtree')  # Child tree, empty."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "32\n"
     ]
    }
   ],
   "source": [
    "J('[23 [2 [4]] [3]] sumtree')  # Non-empty child trees."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "49\n"
     ]
    }
   ],
   "source": [
    "J('[23 [2 [8] [9]] [3] [4 []]] sumtree')  # Etc..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "49\n"
     ]
    }
   ],
   "source": [
    "J('[23 [2 [8] [9]] [3] [4 []]] [pop 0] [] [cons sum] treestep')  # Alternate \"spelling\"."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[23 [23 [23] [23]] [23] [23 []]]\n"
     ]
    }
   ],
   "source": [
    "J('[23 [2 [8] [9]] [3] [4 []]] [] [pop 23] [cons] treestep')  # Replace each node."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1 [1 [1] [1]] [1] [1 []]]\n"
     ]
    }
   ],
   "source": [
    "J('[23 [2 [8] [9]] [3] [4 []]] [] [pop 1] [cons] treestep')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "6\n"
     ]
    }
   ],
   "source": [
    "J('[23 [2 [8] [9]] [3] [4 []]] [] [pop 1] [cons] treestep sumtree')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "6\n"
     ]
    }
   ],
   "source": [
    "J('[23 [2 [8] [9]] [3] [4 []]] [pop 0] [pop 1] [sum +] treestep')  # Combine replace and sum into one function."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3\n"
     ]
    }
   ],
   "source": [
    "J('[4 [3 [] [7]]] [pop 0] [pop 1] [sum +] treestep')  # Combine replace and sum into one function."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Redefining the Ordered Binary Tree in terms of `treestep`.\n",
    "\n",
    "    Tree = [] | [[key value] left right]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "What kind of functions can we write for this with our `treestep`?\n",
    "\n",
    "The pattern for processing a non-empty node is:\n",
    "\n",
    "    node N [tree*] [K] map C\n",
    "\n",
    "Plugging in our BTree structure:\n",
    "\n",
    "    [key value] N [left right] [K] map C"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Traversal\n",
    "    [key value] first [left right] [K] map i\n",
    "    key [value]       [left right] [K] map i\n",
    "    key               [left right] [K] map i\n",
    "    key               [lkey rkey ]         i\n",
    "    key                lkey rkey"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This doesn't quite work:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3 'B' 'B'\n"
     ]
    }
   ],
   "source": [
    "J('[[3 0] [[2 0] [][]] [[9 0] [[5 0] [[4 0] [][]] [[8 0] [[6 0] [] [[7 0] [][]]][]]][]]] [\"B\"] [first] [i] treestep')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Doesn't work because `map` extracts the `first` item of whatever its mapped function produces.  We have to return a list, rather than depositing our results directly on the stack.\n",
    "\n",
    "\n",
    "    [key value] N     [left right] [K] map C\n",
    "\n",
    "    [key value] first [left right] [K] map flatten cons\n",
    "    key               [left right] [K] map flatten cons\n",
    "    key               [[lk] [rk] ]         flatten cons\n",
    "    key               [ lk   rk  ]                 cons\n",
    "                      [key  lk   rk  ]\n",
    "\n",
    "So:\n",
    "\n",
    "    [] [first] [flatten cons] treestep"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[3 2 9 5 4 8 6 7]\n"
     ]
    }
   ],
   "source": [
    "J('[[3 0] [[2 0] [] []] [[9 0] [[5 0] [[4 0] [] []] [[8 0] [[6 0] [] [[7 0] [] []]] []]] []]]   [] [first] [flatten cons] treestep')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "There we go."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### In-order traversal\n",
    "\n",
    "From here:\n",
    "\n",
    "    key [[lk] [rk]] C\n",
    "    key [[lk] [rk]] i\n",
    "    key  [lk] [rk] roll<\n",
    "    [lk] [rk] key swons concat\n",
    "    [lk] [key rk]       concat\n",
    "    [lk   key rk]\n",
    "\n",
    "So:\n",
    "\n",
    "    [] [i roll< swons concat] [first] treestep"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[2 3 4 5 6 7 8 9]\n"
     ]
    }
   ],
   "source": [
    "J('[[3 0] [[2 0] [] []] [[9 0] [[5 0] [[4 0] [] []] [[8 0] [[6 0] [] [[7 0] [] []]] []]] []]]   [] [uncons pop] [i roll< swons concat] treestep')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## With `treegrind`?\n",
    "The `treegrind` function doesn't include the `map` combinator, so the `[C]` function must arrange to use some combinator on the quoted recursive copy `[K]`.  With this function, the pattern for processing a non-empty node is:\n",
    "\n",
    "    node N [tree*] [K] C\n",
    "\n",
    "Plugging in our BTree structure:\n",
    "\n",
    "    [key value] N [left right] [K] C"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['key' 'value'] 'N' [['left'] ['right']] [[not] ['B'] [uncons ['N'] dip] ['C'] genrec] 'C'\n"
     ]
    }
   ],
   "source": [
    "J('[[\"key\" \"value\"] [\"left\"] [\"right\"] ] [\"B\"] [\"N\"] [\"C\"] treegrind')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## `treegrind` with `step`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Iteration through the nodes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[3 0] 'N' [2 0] 'N' [9 0] 'N' [5 0] 'N' [4 0] 'N' [8 0] 'N' [6 0] 'N' [7 0] 'N'\n"
     ]
    }
   ],
   "source": [
    "J('[[3 0] [[2 0] [] []] [[9 0] [[5 0] [[4 0] [] []] [[8 0] [[6 0] [] [[7 0] [] []]] []]] []]]   [pop] [\"N\"] [step] treegrind')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Sum the nodes' keys."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "44\n"
     ]
    }
   ],
   "source": [
    "J('0 [[3 0] [[2 0] [] []] [[9 0] [[5 0] [[4 0] [] []] [[8 0] [[6 0] [] [[7 0] [] []]] []]] []]]   [pop] [first +] [step] treegrind')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Rebuild the tree using `map` (imitating `treestep`.)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[103 0] [[102 0] [] []] [[109 0] [[105 0] [[104 0] [] []] [[108 0] [[106 0] [] [[107 0] [] []]] []]] []]]\n"
     ]
    }
   ],
   "source": [
    "J('[[3 0] [[2 0] [] []] [[9 0] [[5 0] [[4 0] [] []] [[8 0] [[6 0] [] [[7 0] [] []]] []]] []]]   [] [[100 +] infra] [map cons] treegrind')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Do we have the flexibility to reimplement `Tree-get`?\n",
    "I think we do:\n",
    "\n",
    "    [B] [N] [C] treegrind"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We'll start by saying that the base-case (the key is not in the tree) is user defined, and the per-node function is just the query key literal:\n",
    "\n",
    "    [B] [query_key] [C] treegrind"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This means we just have to define `C` from:\n",
    "\n",
    "    [key value] query_key [left right] [K] C\n",
    " "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's try `cmp`:\n",
    "\n",
    "    C == P [T>] [E] [T<] cmp\n",
    "\n",
    "    [key value] query_key [left right] [K] P [T>] [E] [T<] cmp"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### The predicate `P`\n",
    "Seems pretty easy (we must preserve the value in case the keys are equal):\n",
    "\n",
    "    [key value] query_key [left right] [K] P\n",
    "    [key value] query_key [left right] [K] roll<\n",
    "    [key value] [left right] [K] query_key       [roll< uncons swap] dip\n",
    "\n",
    "    [key value] [left right] [K] roll< uncons swap query_key\n",
    "    [left right] [K] [key value]       uncons swap query_key\n",
    "    [left right] [K] key [value]              swap query_key\n",
    "    [left right] [K] [value] key                   query_key\n",
    "\n",
    "    P == roll< [roll< uncons swap] dip\n",
    "\n",
    "(Possibly with a swap at the end?  Or just swap `T<` and `T>`.)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So now:\n",
    "\n",
    "    [left right] [K] [value] key query_key [T>] [E] [T<] cmp\n",
    "\n",
    "Becomes one of these three:\n",
    "\n",
    "    [left right] [K] [value] T>\n",
    "    [left right] [K] [value] E\n",
    "    [left right] [K] [value] T<\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### `E`\n",
    "Easy.\n",
    "\n",
    "    E == roll> popop first"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### `T<` and `T>`\n",
    "\n",
    "    T< == pop [first] dip i\n",
    "    T> == pop [second] dip i"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Putting it together\n",
    "\n",
    "\n",
    "    T> == pop [first] dip i\n",
    "    T< == pop [second] dip i\n",
    "    E == roll> popop first\n",
    "    P == roll< [roll< uncons swap] dip\n",
    "    \n",
    "    Tree-get == [P [T>] [E] [T<] cmp] treegrind\n",
    "\n",
    "To me, that seems simpler than the `genrec` version."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [],
   "source": [
    "DefinitionWrapper.add_definitions('''\n",
    "\n",
    "    T> == pop [first] dip i\n",
    "    T< == pop [second] dip i\n",
    "    E == roll> popop first\n",
    "    P == roll< [roll< uncons swap] dip\n",
    "\n",
    "    Tree-get == [P [T>] [E] [T<] cmp] treegrind\n",
    "\n",
    "''', D)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "15\n"
     ]
    }
   ],
   "source": [
    "J('''\\\n",
    "\n",
    "[[3 13] [[2 12] [] []] [[9 19] [[5 15] [[4 14] [] []] [[8 18] [[6 16] [] [[7 17] [] []]] []]] []]]\n",
    "\n",
    "[] [5] Tree-get\n",
    "\n",
    "''')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "'nope'\n"
     ]
    }
   ],
   "source": [
    "J('''\\\n",
    "\n",
    "[[3 13] [[2 12] [] []] [[9 19] [[5 15] [[4 14] [] []] [[8 18] [[6 16] [] [[7 17] [] []]] []]] []]]\n",
    "\n",
    "[pop \"nope\"] [25] Tree-get\n",
    "\n",
    "''')"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}