"cell_type": "markdown",
"metadata": {},
"source": [
+ "# Traversing Datastructures with Zippers\n",
"This notebook is about using the \"zipper\" with joy datastructures. See the [Zipper wikipedia entry](https://en.wikipedia.org/wiki/Zipper_%28data_structure%29) or the original paper: [\"FUNCTIONAL PEARL The Zipper\" by Gérard Huet](https://www.st.cs.uni-saarland.de/edu/seminare/2005/advanced-fp/docs/huet-zipper.pdf)\n",
"\n",
+ "\n",
"Given a datastructure on the stack we can navigate through it, modify it, and rebuild it using the \"zipper\" technique."
]
},
"cell_type": "markdown",
"metadata": {},
"source": [
- "### Preamble"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": 1,
- "metadata": {},
- "outputs": [],
- "source": [
- "from notebook_preamble import J, V, define"
- ]
- },
- {
- "cell_type": "markdown",
- "metadata": {},
- "source": [
"## Trees\n",
"In Joypy there aren't any complex datastructures, just ints, floats, strings, Symbols (strings that are names of functions) and sequences (aka lists, aka quoted literals, aka aggregates, etc...), but we can build [trees](https://en.wikipedia.org/wiki/Tree_%28data_structure%29) out of sequences."
]
},
{
"cell_type": "code",
- "execution_count": 2,
+ "execution_count": 1,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
- "[1 [2 [3 4 25 6] 7] 8]\n"
+ "[1 [2 [3 4 25 6] 7] 8]"
]
}
],
"source": [
- "J('[1 [2 [3 4 25 6] 7] 8]')"
+ "[1 [2 [3 4 25 6] 7] 8]"
]
},
{
},
{
"cell_type": "code",
+ "execution_count": 2,
+ "metadata": {},
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "[1 [2 [3 4 25 6] 7] 8]"
+ ]
+ }
+ ],
+ "source": [
+ "[z-down [] swap uncons swap] inscribe\n",
+ "[z-up swons swap shunt] inscribe\n",
+ "[z-right roll< cons swap uncons swap] inscribe\n",
+ "[z-left swons [uncons swap] dip swap] inscribe"
+ ]
+ },
+ {
+ "cell_type": "code",
"execution_count": 3,
"metadata": {},
- "outputs": [],
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ " [1 [2 [3 4 25 6] 7] 8] • z-down\n",
+ " [1 [2 [3 4 25 6] 7] 8] • [] swap uncons swap\n",
+ "[1 [2 [3 4 25 6] 7] 8] [] • swap uncons swap\n",
+ "[] [1 [2 [3 4 25 6] 7] 8] • uncons swap\n",
+ "[] 1 [[2 [3 4 25 6] 7] 8] • swap\n",
+ "[] [[2 [3 4 25 6] 7] 8] 1 • \n",
+ "\n",
+ "[] [[2 [3 4 25 6] 7] 8] 1"
+ ]
+ }
+ ],
"source": [
- "define('z-down == [] swap uncons swap')\n",
- "define('z-up == swons swap shunt')\n",
- "define('z-right == [swons] cons dip uncons swap')\n",
- "define('z-left == swons [uncons swap] dip swap')"
+ "[z-down] trace"
]
},
{
"name": "stdout",
"output_type": "stream",
"text": [
- " . [1 [2 [3 4 25 6] 7] 8] z-down\n",
- " [1 [2 [3 4 25 6] 7] 8] . z-down\n",
- " [1 [2 [3 4 25 6] 7] 8] . [] swap uncons swap\n",
- "[1 [2 [3 4 25 6] 7] 8] [] . swap uncons swap\n",
- "[] [1 [2 [3 4 25 6] 7] 8] . uncons swap\n",
- "[] 1 [[2 [3 4 25 6] 7] 8] . swap\n",
- "[] [[2 [3 4 25 6] 7] 8] 1 . \n"
+ "[] [[2 [3 4 25 6] 7] 8] 1 • z-right\n",
+ "[] [[2 [3 4 25 6] 7] 8] 1 • roll< cons swap uncons swap\n",
+ "[[2 [3 4 25 6] 7] 8] 1 [] • cons swap uncons swap\n",
+ " [[2 [3 4 25 6] 7] 8] [1] • swap uncons swap\n",
+ " [1] [[2 [3 4 25 6] 7] 8] • uncons swap\n",
+ " [1] [2 [3 4 25 6] 7] [8] • swap\n",
+ " [1] [8] [2 [3 4 25 6] 7] • \n",
+ "\n",
+ "[1] [8] [2 [3 4 25 6] 7]"
]
}
],
"source": [
- "V('[1 [2 [3 4 25 6] 7] 8] z-down')"
+ "[z-right] trace"
]
},
{
"name": "stdout",
"output_type": "stream",
"text": [
- " . [] [[2 [3 4 25 6] 7] 8] 1 z-right\n",
- " [] . [[2 [3 4 25 6] 7] 8] 1 z-right\n",
- " [] [[2 [3 4 25 6] 7] 8] . 1 z-right\n",
- " [] [[2 [3 4 25 6] 7] 8] 1 . z-right\n",
- " [] [[2 [3 4 25 6] 7] 8] 1 . [swons] cons dip uncons swap\n",
- "[] [[2 [3 4 25 6] 7] 8] 1 [swons] . cons dip uncons swap\n",
- "[] [[2 [3 4 25 6] 7] 8] [1 swons] . dip uncons swap\n",
- " [] . 1 swons [[2 [3 4 25 6] 7] 8] uncons swap\n",
- " [] 1 . swons [[2 [3 4 25 6] 7] 8] uncons swap\n",
- " [] 1 . swap cons [[2 [3 4 25 6] 7] 8] uncons swap\n",
- " 1 [] . cons [[2 [3 4 25 6] 7] 8] uncons swap\n",
- " [1] . [[2 [3 4 25 6] 7] 8] uncons swap\n",
- " [1] [[2 [3 4 25 6] 7] 8] . uncons swap\n",
- " [1] [2 [3 4 25 6] 7] [8] . swap\n",
- " [1] [8] [2 [3 4 25 6] 7] . \n"
+ "[1] [8] [] [[3 4 25 6] 7] 2"
]
}
],
"source": [
- "V('[] [[2 [3 4 25 6] 7] 8] 1 z-right')"
+ "z-down"
]
},
{
"name": "stdout",
"output_type": "stream",
"text": [
- "[1] [8] [] [[3 4 25 6] 7] 2\n"
+ "[1] [8] [2] [7] [3 4 25 6]"
]
}
],
"source": [
- "J('[1] [8] [2 [3 4 25 6] 7] z-down')"
+ "z-right"
]
},
{
"name": "stdout",
"output_type": "stream",
"text": [
- "[1] [8] [2] [7] [3 4 25 6]\n"
+ "[1] [8] [2] [7] [] [4 25 6] 3"
]
}
],
"source": [
- "J('[1] [8] [] [[3 4 25 6] 7] 2 z-right')"
+ "z-down"
]
},
{
"name": "stdout",
"output_type": "stream",
"text": [
- "[1] [8] [2] [7] [] [4 25 6] 3\n"
+ "[1] [8] [2] [7] [3] [25 6] 4"
]
}
],
"source": [
- "J('[1] [8] [2] [7] [3 4 25 6] z-down')"
+ "z-right"
]
},
{
"name": "stdout",
"output_type": "stream",
"text": [
- "[1] [8] [2] [7] [3] [25 6] 4\n"
+ "[1] [8] [2] [7] [4 3] [6] 25"
]
}
],
"source": [
- "J('[1] [8] [2] [7] [] [4 25 6] 3 z-right')"
+ "z-right"
]
},
{
"name": "stdout",
"output_type": "stream",
"text": [
- "[1] [8] [2] [7] [4 3] [6] 25\n"
+ "[1] [8] [2] [7] [4 3] [6] 625"
]
}
],
"source": [
- "J('[1] [8] [2] [7] [3] [25 6] 4 z-right')"
+ "sqr"
]
},
{
"name": "stdout",
"output_type": "stream",
"text": [
- "[1] [8] [2] [7] [4 3] [6] 625\n"
+ "[1] [8] [2] [7] [4 3] [6] 625 • z-up\n",
+ "[1] [8] [2] [7] [4 3] [6] 625 • swons swap shunt\n",
+ "[1] [8] [2] [7] [4 3] [625 6] • swap shunt\n",
+ "[1] [8] [2] [7] [625 6] [4 3] • shunt\n",
+ " [1] [8] [2] [7] [3 4 625 6] • \n",
+ "\n",
+ "[1] [8] [2] [7] [3 4 625 6]"
]
}
],
"source": [
- "J('[1] [8] [2] [7] [4 3] [6] 25 sqr')"
+ "[z-up] trace"
]
},
{
"name": "stdout",
"output_type": "stream",
"text": [
- " . [1] [8] [2] [7] [4 3] [6] 625 z-up\n",
- " [1] . [8] [2] [7] [4 3] [6] 625 z-up\n",
- " [1] [8] . [2] [7] [4 3] [6] 625 z-up\n",
- " [1] [8] [2] . [7] [4 3] [6] 625 z-up\n",
- " [1] [8] [2] [7] . [4 3] [6] 625 z-up\n",
- " [1] [8] [2] [7] [4 3] . [6] 625 z-up\n",
- " [1] [8] [2] [7] [4 3] [6] . 625 z-up\n",
- "[1] [8] [2] [7] [4 3] [6] 625 . z-up\n",
- "[1] [8] [2] [7] [4 3] [6] 625 . swons swap shunt\n",
- "[1] [8] [2] [7] [4 3] [6] 625 . swap cons swap shunt\n",
- "[1] [8] [2] [7] [4 3] 625 [6] . cons swap shunt\n",
- "[1] [8] [2] [7] [4 3] [625 6] . swap shunt\n",
- "[1] [8] [2] [7] [625 6] [4 3] . shunt\n",
- " [1] [8] [2] [7] [3 4 625 6] . \n"
+ "[1] [8] [2 [3 4 625 6] 7]"
]
}
],
"source": [
- "V('[1] [8] [2] [7] [4 3] [6] 625 z-up')"
+ "z-up"
]
},
{
"name": "stdout",
"output_type": "stream",
"text": [
- "[1] [8] [2 [3 4 625 6] 7]\n"
+ "[1 [2 [3 4 625 6] 7] 8]"
]
}
],
"source": [
- "J('[1] [8] [2] [7] [3 4 625 6] z-up')"
+ "z-up"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "metadata": {},
+ "source": [
+ "## `dip` and `infra`\n",
+ "In Joy we have the `dip` and `infra` combinators which can \"target\" or \"address\" any particular item in a Joy tree structure."
]
},
{
"name": "stdout",
"output_type": "stream",
"text": [
- "[1 [2 [3 4 625 6] 7] 8]\n"
+ "[1 [2 [3 4 390625 6] 7] 8]"
]
}
],
"source": [
- "J('[1] [8] [2 [3 4 625 6] 7] z-up')"
+ "[[[[[[sqr] dipd] infra] dip] infra] dip] infra"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
- "## `dip` and `infra`\n",
- "In Joy we have the `dip` and `infra` combinators which can \"target\" or \"address\" any particular item in a Joy tree structure."
+ "If you were to trace the program you would see that about half of it is the `dip` and `infra` combinators de-quoting programs and \"digging\" into the subject datastructure. Instead of maintaining temporary results on the stack they are pushed into the pending expression (continuation). When `sqr` has run the rest of the pending expression rebuilds the datastructure.\n",
+ "\n",
+ "## `Z`\n",
+ "Imagine a function `Z` that accepts a sequence of `dip` and `infra` combinators, a quoted program `[Q]`, and a datastructure to work on. It would effectively execute the quoted program as if it had been embedded in a nested series of quoted programs, e.g.:\n",
+ "\n",
+ " [...] [Q] [[dip] [dip] [infra] [dip] [infra] [dip] [infra]] Z\n",
+ " -------------------------------------------------------------------\n",
+ " [...] [[[[[[[Q] dip] dip] infra] dip] infra] dip] infra\n",
+ " \n",
+ "The `Z` function isn't hard to make."
]
},
{
"name": "stdout",
"output_type": "stream",
"text": [
- " . [1 [2 [3 4 25 6] 7] 8] [[[[[[sqr] dipd] infra] dip] infra] dip] infra\n",
- " [1 [2 [3 4 25 6] 7] 8] . [[[[[[sqr] dipd] infra] dip] infra] dip] infra\n",
- "[1 [2 [3 4 25 6] 7] 8] [[[[[[sqr] dipd] infra] dip] infra] dip] . infra\n",
- " 8 [2 [3 4 25 6] 7] 1 . [[[[[sqr] dipd] infra] dip] infra] dip [] swaack\n",
- " 8 [2 [3 4 25 6] 7] 1 [[[[[sqr] dipd] infra] dip] infra] . dip [] swaack\n",
- " 8 [2 [3 4 25 6] 7] . [[[[sqr] dipd] infra] dip] infra 1 [] swaack\n",
- " 8 [2 [3 4 25 6] 7] [[[[sqr] dipd] infra] dip] . infra 1 [] swaack\n",
- " 7 [3 4 25 6] 2 . [[[sqr] dipd] infra] dip [8] swaack 1 [] swaack\n",
- " 7 [3 4 25 6] 2 [[[sqr] dipd] infra] . dip [8] swaack 1 [] swaack\n",
- " 7 [3 4 25 6] . [[sqr] dipd] infra 2 [8] swaack 1 [] swaack\n",
- " 7 [3 4 25 6] [[sqr] dipd] . infra 2 [8] swaack 1 [] swaack\n",
- " 6 25 4 3 . [sqr] dipd [7] swaack 2 [8] swaack 1 [] swaack\n",
- " 6 25 4 3 [sqr] . dipd [7] swaack 2 [8] swaack 1 [] swaack\n",
- " 6 25 . sqr 4 3 [7] swaack 2 [8] swaack 1 [] swaack\n",
- " 6 25 . dup mul 4 3 [7] swaack 2 [8] swaack 1 [] swaack\n",
- " 6 25 25 . mul 4 3 [7] swaack 2 [8] swaack 1 [] swaack\n",
- " 6 625 . 4 3 [7] swaack 2 [8] swaack 1 [] swaack\n",
- " 6 625 4 . 3 [7] swaack 2 [8] swaack 1 [] swaack\n",
- " 6 625 4 3 . [7] swaack 2 [8] swaack 1 [] swaack\n",
- " 6 625 4 3 [7] . swaack 2 [8] swaack 1 [] swaack\n",
- " 7 [3 4 625 6] . 2 [8] swaack 1 [] swaack\n",
- " 7 [3 4 625 6] 2 . [8] swaack 1 [] swaack\n",
- " 7 [3 4 625 6] 2 [8] . swaack 1 [] swaack\n",
- " 8 [2 [3 4 625 6] 7] . 1 [] swaack\n",
- " 8 [2 [3 4 625 6] 7] 1 . [] swaack\n",
- " 8 [2 [3 4 625 6] 7] 1 [] . swaack\n",
- " [1 [2 [3 4 625 6] 7] 8] . \n"
+ "[sqr] [[dip] [dip] [infra] [dip] [infra] [dip] [infra]]"
+ ]
+ }
+ ],
+ "source": [
+ "clear\n",
+ "[sqr]\n",
+ "[[dip][dip][infra][dip][infra][dip][infra]]"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 16,
+ "metadata": {},
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "[[[[[[[[sqr] dip] dip] infra] dip] infra] dip] infra]"
]
}
],
"source": [
- "V('[1 [2 [3 4 25 6] 7] 8] [[[[[[sqr] dipd] infra] dip] infra] dip] infra')"
+ "[cons] step"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
- "If you read the trace carefully you'll see that about half of it is the `dip` and `infra` combinators de-quoting programs and \"digging\" into the subject datastructure. Instead of maintaining temporary results on the stack they are pushed into the pending expression (continuation). When `sqr` has run the rest of the pending expression rebuilds the datastructure.\n",
- "\n",
- "## `Z`\n",
- "Imagine a function `Z` that accepts a sequence of `dip` and `infra` combinators, a quoted program `[Q]`, and a datastructure to work on. It would effectively execute the quoted program as if it had been embedded in a nested series of quoted programs, e.g.:\n",
- "\n",
- " [...] [Q] [dip dip infra dip infra dip infra] Z\n",
- " -------------------------------------------------------------\n",
- " [...] [[[[[[[Q] dip] dip] infra] dip] infra] dip] infra\n",
- " \n",
- "The `Z` function isn't hard to make."
+ "To use it you need to run the resulting program with the `i` combinator."
]
},
{
"cell_type": "code",
- "execution_count": 16,
+ "execution_count": 17,
"metadata": {},
- "outputs": [],
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "[1 [2 [3 4 25 6] 7] 8] [[[[[[[[sqr] dip] dip] infra] dip] infra] dip] infra]"
+ ]
+ }
+ ],
"source": [
- "define('Z == [[] cons cons] step i')"
+ "[1 [2 [3 4 25 6] 7] 8] swap"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 18,
+ "metadata": {},
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "[1 [2 [3 4 625 6] 7] 8]"
+ ]
+ }
+ ],
+ "source": [
+ "i"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
- "Here it is in action in a simplified scenario."
+ "So let's define `Z` as:\n",
+ "\n",
+ " Z == [cons] step i"
]
},
{
"cell_type": "code",
- "execution_count": 17,
+ "execution_count": 19,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
- " . 1 [2 3 4] Z\n",
- " 1 . [2 3 4] Z\n",
- " 1 [2 3 4] . Z\n",
- " 1 [2 3 4] . [[] cons cons] step i\n",
- " 1 [2 3 4] [[] cons cons] . step i\n",
- " 1 2 [[] cons cons] . i [3 4] [[] cons cons] step i\n",
- " 1 2 . [] cons cons [3 4] [[] cons cons] step i\n",
- " 1 2 [] . cons cons [3 4] [[] cons cons] step i\n",
- " 1 [2] . cons [3 4] [[] cons cons] step i\n",
- " [1 2] . [3 4] [[] cons cons] step i\n",
- " [1 2] [3 4] . [[] cons cons] step i\n",
- " [1 2] [3 4] [[] cons cons] . step i\n",
- " [1 2] 3 [[] cons cons] . i [4] [[] cons cons] step i\n",
- " [1 2] 3 . [] cons cons [4] [[] cons cons] step i\n",
- " [1 2] 3 [] . cons cons [4] [[] cons cons] step i\n",
- " [1 2] [3] . cons [4] [[] cons cons] step i\n",
- " [[1 2] 3] . [4] [[] cons cons] step i\n",
- " [[1 2] 3] [4] . [[] cons cons] step i\n",
- "[[1 2] 3] [4] [[] cons cons] . step i\n",
- " [[1 2] 3] 4 [[] cons cons] . i i\n",
- " [[1 2] 3] 4 . [] cons cons i\n",
- " [[1 2] 3] 4 [] . cons cons i\n",
- " [[1 2] 3] [4] . cons i\n",
- " [[[1 2] 3] 4] . i\n",
- " . [[1 2] 3] 4\n",
- " [[1 2] 3] . 4\n",
- " [[1 2] 3] 4 . \n"
+ "[1 [2 [3 4 625 6] 7] 8]"
]
}
],
"source": [
- "V('1 [2 3 4] Z')"
+ "[Z [cons] step i] inscribe"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
- "And here it is doing the main thing."
+ "And here it is doing the thing."
]
},
{
"cell_type": "code",
- "execution_count": 18,
+ "execution_count": 20,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
- "[1 [2 [3 4 625 6] 7] 8]\n"
+ "[1 [2 [3 4 25 6] 7] 8] [sqr] [[dip] [dip] [infra] [dip] [infra] [dip] [infra]]"
]
}
],
"source": [
- "J('[1 [2 [3 4 25 6] 7] 8] [sqr] [dip dip infra dip infra dip infra] Z')"
+ "clear\n",
+ "[1 [2 [3 4 25 6] 7] 8]\n",
+ "[sqr]\n",
+ "[[dip][dip][infra][dip][infra][dip][infra]]"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 21,
+ "metadata": {},
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "[1 [2 [3 4 625 6] 7] 8]"
+ ]
+ }
+ ],
+ "source": [
+ "Z"
]
},
{
" [ n [ n [ n n x ...\n",
" i d i d i d d Bingo!"
]
- },
- {
- "cell_type": "code",
- "execution_count": 19,
- "metadata": {},
- "outputs": [],
- "source": []
}
],
"metadata": {
"kernelspec": {
- "display_name": "Python 2",
- "language": "python",
- "name": "python2"
+ "display_name": "Joypy",
+ "language": "",
+ "name": "thun"
},
"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.13"
+ "file_extension": ".joy",
+ "mimetype": "text/plain",
+ "name": "Joy"
}
},
"nbformat": 4,
OSDN Git Service
