-
+

Traversing Datastructures with Zippers¶

This notebook is about using the “zipper” with joy datastructures. See the Zipper wikipedia @@ -41,24 +42,24 @@ the original paper: 

from notebook_preamble import J, V, define
+
from notebook_preamble import J, V, define
 

 

-

+

 
Trees¶

 
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 out
 of sequences.

-
J('[1 [2 [3 4 25 6] 7] 8]')
+
J('[1 [2 [3 4 25 6] 7] 8]')
 

 

 
[1 [2 [3 4 25 6] 7] 8]
 

 

-

-

+

+

 
Zipper in Joy¶

 
Zippers work by keeping track of the current item, the already-seen
 items, and the yet-to-be seen items as you traverse a datastructure (the
@@ -74,13 +75,13 @@ datastructure used to keep track of these items is the zipper.)

 show the trace so you can see how it works. If we were going to use
 these a lot it would make sense to write Python versions for efficiency,
 but see below.

-
define('z-down == [] swap uncons swap')
+
define('z-down == [] swap uncons swap')
 define('z-up == swons swap shunt')
 define('z-right == [swons] cons dip uncons swap')
 define('z-left == swons [uncons swap] dip swap')
 

 

-
V('[1 [2 [3 4 25 6] 7] 8] z-down')
+
V('[1 [2 [3 4 25 6] 7] 8] z-down')
 

 

 
                          . [1 [2 [3 4 25 6] 7] 8] z-down
@@ -92,7 +93,7 @@ but see below.

 [] [[2 [3 4 25 6] 7] 8] 1 .
 

 

-
V('[] [[2 [3 4 25 6] 7] 8] 1 z-right')
+
V('[] [[2 [3 4 25 6] 7] 8] 1 z-right')
 

 

 
                                  . [] [[2 [3 4 25 6] 7] 8] 1 z-right
@@ -112,43 +113,43 @@ but see below.

          [1] [8] [2 [3 4 25 6] 7] .
 

 

-
J('[1] [8] [2 [3 4 25 6] 7] z-down')
+
J('[1] [8] [2 [3 4 25 6] 7] z-down')
 

 

 
[1] [8] [] [[3 4 25 6] 7] 2
 

 

-
J('[1] [8] [] [[3 4 25 6] 7] 2 z-right')
+
J('[1] [8] [] [[3 4 25 6] 7] 2 z-right')
 

 

 
[1] [8] [2] [7] [3 4 25 6]
 

 

-
J('[1] [8] [2] [7] [3 4 25 6] z-down')
+
J('[1] [8] [2] [7] [3 4 25 6] z-down')
 

 

 
[1] [8] [2] [7] [] [4 25 6] 3
 

 

-
J('[1] [8] [2] [7] [] [4 25 6] 3 z-right')
+
J('[1] [8] [2] [7] [] [4 25 6] 3 z-right')
 

 

 
[1] [8] [2] [7] [3] [25 6] 4
 

 

-
J('[1] [8] [2] [7] [3] [25 6] 4 z-right')
+
J('[1] [8] [2] [7] [3] [25 6] 4 z-right')
 

 

 
[1] [8] [2] [7] [4 3] [6] 25
 

 

-
J('[1] [8] [2] [7] [4 3] [6] 25 sqr')
+
J('[1] [8] [2] [7] [4 3] [6] 25 sqr')
 

 

 
[1] [8] [2] [7] [4 3] [6] 625
 

 

-
V('[1] [8] [2] [7] [4 3] [6] 625 z-up')
+
V('[1] [8] [2] [7] [4 3] [6] 625 z-up')
 

 

 
                              . [1] [8] [2] [7] [4 3] [6] 625 z-up
@@ -167,24 +168,24 @@ but see below.

   [1] [8] [2] [7] [3 4 625 6] .
 

 

-
J('[1] [8] [2] [7] [3 4 625 6] z-up')
+
J('[1] [8] [2] [7] [3 4 625 6] z-up')
 

 

 
[1] [8] [2 [3 4 625 6] 7]
 

 

-
J('[1] [8] [2 [3 4 625 6] 7] z-up')
+
J('[1] [8] [2 [3 4 625 6] 7] z-up')
 

 

 
[1 [2 [3 4 625 6] 7] 8]
 

 

-

-

+

+

 
dip and infra¶

 
In Joy we have the dip and infra combinators which can “target”
 or “address” any particular item in a Joy tree structure.

-
V('[1 [2 [3 4 25 6] 7] 8] [[[[[[sqr] dipd] infra] dip] infra] dip] infra')
+
V('[1 [2 [3 4 25 6] 7] 8] [[[[[[sqr] dipd] infra] dip] infra] dip] infra')
 

 

 
                                                                . [1 [2 [3 4 25 6] 7] 8] [[[[[[sqr] dipd] infra] dip] infra] dip] infra
@@ -222,8 +223,8 @@ 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.

-

-

+

+

 
Z¶

 
Imagine a function Z that accepts a sequence of dip and
 infra combinators, a quoted program [Q], and a datastructure to
@@ -235,11 +236,11 @@ been embedded in a nested series of quoted programs, e.g.:

The Z function isn’t hard to make.

-
define('Z == [[] cons cons] step i')
+
define('Z == [[] cons cons] step i')
 

 

 
Here it is in action in a simplified scenario.

-
V('1 [2 3 4] Z')
+
V('1 [2 3 4] Z')
 

 

 
                             . 1 [2 3 4] Z
@@ -272,14 +273,14 @@ been embedded in a nested series of quoted programs, e.g.:

 

 

 
And here it is doing the main thing.

-
J('[1 [2 [3 4 25 6] 7] 8] [sqr] [dip dip infra dip infra dip infra] Z')
+
J('[1 [2 [3 4 25 6] 7] 8] [sqr] [dip dip infra dip infra dip infra] Z')
 

 

 
[1 [2 [3 4 625 6] 7] 8]
 

 

-

-

+
+

 
Addressing¶

 
Because we are only using two combinators we could replace the list with
 a string made from only two characters.

@@ -290,8 +291,8 @@ a string made from only two characters.

 

 
The string can be considered a name or address for an item in the
 subject datastructure.

-

-

+
+

 
Determining the right “path” for an item in a tree.¶

 
It’s easy to read off (in reverse) the right sequence of “d” and “i”
 from the subject datastructure:

@@ -299,57 +300,85 @@ from the subject datastructure:

 i d i d i d d Bingo!
 

 

-
-
+ +