docs/sphinx_docs/notebooks/Zipper.rst

   1 Traversing Datastructures with Zippers
   2 ======================================
   3
   4 This notebook is about using the “zipper” with joy datastructures. See
   5 the `Zipper wikipedia
   6 entry <https://en.wikipedia.org/wiki/Zipper_%28data_structure%29>`__ or
   7 the original paper: `“FUNCTIONAL PEARL The Zipper” by Gérard
   8 Huet <https://www.st.cs.uni-saarland.de/edu/seminare/2005/advanced-fp/docs/huet-zipper.pdf>`__
   9
  10 Given a datastructure on the stack we can navigate through it, modify
  11 it, and rebuild it using the “zipper” technique.
  12
  13 .. code:: ipython2
  14
  15     from notebook_preamble import J, V, define
  16
  17 Trees
  18 -----
  19
  20 In Joypy there aren’t any complex datastructures, just ints, floats,
  21 strings, Symbols (strings that are names of functions) and sequences
  22 (aka lists, aka quoted literals, aka aggregates, etc…), but we can build
  23 `trees <https://en.wikipedia.org/wiki/Tree_%28data_structure%29>`__ out
  24 of sequences.
  25
  26 .. code:: ipython2
  27
  28     J('[1 [2 [3 4 25 6] 7] 8]')
  29
  30
  31 .. parsed-literal::
  32
  33     [1 [2 [3 4 25 6] 7] 8]
  34
  35
  36 Zipper in Joy
  37 -------------
  38
  39 Zippers work by keeping track of the current item, the already-seen
  40 items, and the yet-to-be seen items as you traverse a datastructure (the
  41 datastructure used to keep track of these items is the zipper.)
  42
  43 In Joy we can do this with the following words:
  44
  45 ::
  46
  47    z-down == [] swap uncons swap
  48    z-up == swons swap shunt
  49    z-right == [swons] cons dip uncons swap
  50    z-left == swons [uncons swap] dip swap
  51
  52 Let’s use them to change 25 into 625. The first time a word is used I
  53 show the trace so you can see how it works. If we were going to use
  54 these a lot it would make sense to write Python versions for efficiency,
  55 but see below.
  56
  57 .. code:: ipython2
  58
  59     define('z-down == [] swap uncons swap')
  60     define('z-up == swons swap shunt')
  61     define('z-right == [swons] cons dip uncons swap')
  62     define('z-left == swons [uncons swap] dip swap')
  63
  64 .. code:: ipython2
  65
  66     V('[1 [2 [3 4 25 6] 7] 8] z-down')
  67
  68
  69 .. parsed-literal::
  70
  71                               . [1 [2 [3 4 25 6] 7] 8] z-down
  72        [1 [2 [3 4 25 6] 7] 8] . z-down
  73        [1 [2 [3 4 25 6] 7] 8] . [] swap uncons swap
  74     [1 [2 [3 4 25 6] 7] 8] [] . swap uncons swap
  75     [] [1 [2 [3 4 25 6] 7] 8] . uncons swap
  76     [] 1 [[2 [3 4 25 6] 7] 8] . swap
  77     [] [[2 [3 4 25 6] 7] 8] 1 .
  78
  79
  80 .. code:: ipython2
  81
  82     V('[] [[2 [3 4 25 6] 7] 8] 1 z-right')
  83
  84
  85 .. parsed-literal::
  86
  87                                       . [] [[2 [3 4 25 6] 7] 8] 1 z-right
  88                                    [] . [[2 [3 4 25 6] 7] 8] 1 z-right
  89               [] [[2 [3 4 25 6] 7] 8] . 1 z-right
  90             [] [[2 [3 4 25 6] 7] 8] 1 . z-right
  91             [] [[2 [3 4 25 6] 7] 8] 1 . [swons] cons dip uncons swap
  92     [] [[2 [3 4 25 6] 7] 8] 1 [swons] . cons dip uncons swap
  93     [] [[2 [3 4 25 6] 7] 8] [1 swons] . dip uncons swap
  94                                    [] . 1 swons [[2 [3 4 25 6] 7] 8] uncons swap
  95                                  [] 1 . swons [[2 [3 4 25 6] 7] 8] uncons swap
  96                                  [] 1 . swap cons [[2 [3 4 25 6] 7] 8] uncons swap
  97                                  1 [] . cons [[2 [3 4 25 6] 7] 8] uncons swap
  98                                   [1] . [[2 [3 4 25 6] 7] 8] uncons swap
  99              [1] [[2 [3 4 25 6] 7] 8] . uncons swap
 100              [1] [2 [3 4 25 6] 7] [8] . swap
 101              [1] [8] [2 [3 4 25 6] 7] .
 102
 103
 104 .. code:: ipython2
 105
 106     J('[1] [8] [2 [3 4 25 6] 7] z-down')
 107
 108
 109 .. parsed-literal::
 110
 111     [1] [8] [] [[3 4 25 6] 7] 2
 112
 113
 114 .. code:: ipython2
 115
 116     J('[1] [8] [] [[3 4 25 6] 7] 2 z-right')
 117
 118
 119 .. parsed-literal::
 120
 121     [1] [8] [2] [7] [3 4 25 6]
 122
 123
 124 .. code:: ipython2
 125
 126     J('[1] [8] [2] [7] [3 4 25 6] z-down')
 127
 128
 129 .. parsed-literal::
 130
 131     [1] [8] [2] [7] [] [4 25 6] 3
 132
 133
 134 .. code:: ipython2
 135
 136     J('[1] [8] [2] [7] [] [4 25 6] 3 z-right')
 137
 138
 139 .. parsed-literal::
 140
 141     [1] [8] [2] [7] [3] [25 6] 4
 142
 143
 144 .. code:: ipython2
 145
 146     J('[1] [8] [2] [7] [3] [25 6] 4 z-right')
 147
 148
 149 .. parsed-literal::
 150
 151     [1] [8] [2] [7] [4 3] [6] 25
 152
 153
 154 .. code:: ipython2
 155
 156     J('[1] [8] [2] [7] [4 3] [6] 25 sqr')
 157
 158
 159 .. parsed-literal::
 160
 161     [1] [8] [2] [7] [4 3] [6] 625
 162
 163
 164 .. code:: ipython2
 165
 166     V('[1] [8] [2] [7] [4 3] [6] 625 z-up')
 167
 168
 169 .. parsed-literal::
 170
 171                                   . [1] [8] [2] [7] [4 3] [6] 625 z-up
 172                               [1] . [8] [2] [7] [4 3] [6] 625 z-up
 173                           [1] [8] . [2] [7] [4 3] [6] 625 z-up
 174                       [1] [8] [2] . [7] [4 3] [6] 625 z-up
 175                   [1] [8] [2] [7] . [4 3] [6] 625 z-up
 176             [1] [8] [2] [7] [4 3] . [6] 625 z-up
 177         [1] [8] [2] [7] [4 3] [6] . 625 z-up
 178     [1] [8] [2] [7] [4 3] [6] 625 . z-up
 179     [1] [8] [2] [7] [4 3] [6] 625 . swons swap shunt
 180     [1] [8] [2] [7] [4 3] [6] 625 . swap cons swap shunt
 181     [1] [8] [2] [7] [4 3] 625 [6] . cons swap shunt
 182     [1] [8] [2] [7] [4 3] [625 6] . swap shunt
 183     [1] [8] [2] [7] [625 6] [4 3] . shunt
 184       [1] [8] [2] [7] [3 4 625 6] .
 185
 186
 187 .. code:: ipython2
 188
 189     J('[1] [8] [2] [7] [3 4 625 6] z-up')
 190
 191
 192 .. parsed-literal::
 193
 194     [1] [8] [2 [3 4 625 6] 7]
 195
 196
 197 .. code:: ipython2
 198
 199     J('[1] [8] [2 [3 4 625 6] 7] z-up')
 200
 201
 202 .. parsed-literal::
 203
 204     [1 [2 [3 4 625 6] 7] 8]
 205
 206
 207 ``dip`` and ``infra``
 208 ---------------------
 209
 210 In Joy we have the ``dip`` and ``infra`` combinators which can “target”
 211 or “address” any particular item in a Joy tree structure.
 212
 213 .. code:: ipython2
 214
 215     V('[1 [2 [3 4 25 6] 7] 8] [[[[[[sqr] dipd] infra] dip] infra] dip] infra')
 216
 217
 218 .. parsed-literal::
 219
 220                                                                     . [1 [2 [3 4 25 6] 7] 8] [[[[[[sqr] dipd] infra] dip] infra] dip] infra
 221                                              [1 [2 [3 4 25 6] 7] 8] . [[[[[[sqr] dipd] infra] dip] infra] dip] infra
 222     [1 [2 [3 4 25 6] 7] 8] [[[[[[sqr] dipd] infra] dip] infra] dip] . infra
 223                                                8 [2 [3 4 25 6] 7] 1 . [[[[[sqr] dipd] infra] dip] infra] dip [] swaack
 224             8 [2 [3 4 25 6] 7] 1 [[[[[sqr] dipd] infra] dip] infra] . dip [] swaack
 225                                                  8 [2 [3 4 25 6] 7] . [[[[sqr] dipd] infra] dip] infra 1 [] swaack
 226                       8 [2 [3 4 25 6] 7] [[[[sqr] dipd] infra] dip] . infra 1 [] swaack
 227                                                      7 [3 4 25 6] 2 . [[[sqr] dipd] infra] dip [8] swaack 1 [] swaack
 228                                 7 [3 4 25 6] 2 [[[sqr] dipd] infra] . dip [8] swaack 1 [] swaack
 229                                                        7 [3 4 25 6] . [[sqr] dipd] infra 2 [8] swaack 1 [] swaack
 230                                           7 [3 4 25 6] [[sqr] dipd] . infra 2 [8] swaack 1 [] swaack
 231                                                            6 25 4 3 . [sqr] dipd [7] swaack 2 [8] swaack 1 [] swaack
 232                                                      6 25 4 3 [sqr] . dipd [7] swaack 2 [8] swaack 1 [] swaack
 233                                                                6 25 . sqr 4 3 [7] swaack 2 [8] swaack 1 [] swaack
 234                                                                6 25 . dup mul 4 3 [7] swaack 2 [8] swaack 1 [] swaack
 235                                                             6 25 25 . mul 4 3 [7] swaack 2 [8] swaack 1 [] swaack
 236                                                               6 625 . 4 3 [7] swaack 2 [8] swaack 1 [] swaack
 237                                                             6 625 4 . 3 [7] swaack 2 [8] swaack 1 [] swaack
 238                                                           6 625 4 3 . [7] swaack 2 [8] swaack 1 [] swaack
 239                                                       6 625 4 3 [7] . swaack 2 [8] swaack 1 [] swaack
 240                                                       7 [3 4 625 6] . 2 [8] swaack 1 [] swaack
 241                                                     7 [3 4 625 6] 2 . [8] swaack 1 [] swaack
 242                                                 7 [3 4 625 6] 2 [8] . swaack 1 [] swaack
 243                                                 8 [2 [3 4 625 6] 7] . 1 [] swaack
 244                                               8 [2 [3 4 625 6] 7] 1 . [] swaack
 245                                            8 [2 [3 4 625 6] 7] 1 [] . swaack
 246                                             [1 [2 [3 4 625 6] 7] 8] .
 247
 248
 249 If you read the trace carefully you’ll see that about half of it is the
 250 ``dip`` and ``infra`` combinators de-quoting programs and “digging” into
 251 the subject datastructure. Instead of maintaining temporary results on
 252 the stack they are pushed into the pending expression (continuation).
 253 When ``sqr`` has run the rest of the pending expression rebuilds the
 254 datastructure.
 255
 256 ``Z``
 257 -----
 258
 259 Imagine a function ``Z`` that accepts a sequence of ``dip`` and
 260 ``infra`` combinators, a quoted program ``[Q]``, and a datastructure to
 261 work on. It would effectively execute the quoted program as if it had
 262 been embedded in a nested series of quoted programs, e.g.:
 263
 264 ::
 265
 266       [...] [Q] [dip dip infra dip infra dip infra] Z
 267    -------------------------------------------------------------
 268       [...] [[[[[[[Q] dip] dip] infra] dip] infra] dip] infra
 269
 270
 271 The ``Z`` function isn’t hard to make.
 272
 273 .. code:: ipython2
 274
 275     define('Z == [[] cons cons] step i')
 276
 277 Here it is in action in a simplified scenario.
 278
 279 .. code:: ipython2
 280
 281     V('1 [2 3 4] Z')
 282
 283
 284 .. parsed-literal::
 285
 286                                  . 1 [2 3 4] Z
 287                                1 . [2 3 4] Z
 288                        1 [2 3 4] . Z
 289                        1 [2 3 4] . [[] cons cons] step i
 290         1 [2 3 4] [[] cons cons] . step i
 291               1 2 [[] cons cons] . i [3 4] [[] cons cons] step i
 292                              1 2 . [] cons cons [3 4] [[] cons cons] step i
 293                           1 2 [] . cons cons [3 4] [[] cons cons] step i
 294                            1 [2] . cons [3 4] [[] cons cons] step i
 295                            [1 2] . [3 4] [[] cons cons] step i
 296                      [1 2] [3 4] . [[] cons cons] step i
 297       [1 2] [3 4] [[] cons cons] . step i
 298           [1 2] 3 [[] cons cons] . i [4] [[] cons cons] step i
 299                          [1 2] 3 . [] cons cons [4] [[] cons cons] step i
 300                       [1 2] 3 [] . cons cons [4] [[] cons cons] step i
 301                        [1 2] [3] . cons [4] [[] cons cons] step i
 302                        [[1 2] 3] . [4] [[] cons cons] step i
 303                    [[1 2] 3] [4] . [[] cons cons] step i
 304     [[1 2] 3] [4] [[] cons cons] . step i
 305       [[1 2] 3] 4 [[] cons cons] . i i
 306                      [[1 2] 3] 4 . [] cons cons i
 307                   [[1 2] 3] 4 [] . cons cons i
 308                    [[1 2] 3] [4] . cons i
 309                    [[[1 2] 3] 4] . i
 310                                  . [[1 2] 3] 4
 311                        [[1 2] 3] . 4
 312                      [[1 2] 3] 4 .
 313
 314
 315 And here it is doing the main thing.
 316
 317 .. code:: ipython2
 318
 319     J('[1 [2 [3 4 25 6] 7] 8] [sqr] [dip dip infra dip infra dip infra] Z')
 320
 321
 322 .. parsed-literal::
 323
 324     [1 [2 [3 4 625 6] 7] 8]
 325
 326
 327 Addressing
 328 ----------
 329
 330 Because we are only using two combinators we could replace the list with
 331 a string made from only two characters.
 332
 333 ::
 334
 335       [...] [Q] 'ddididi' Zstr
 336    -------------------------------------------------------------
 337       [...] [[[[[[[Q] dip] dip] infra] dip] infra] dip] infra
 338
 339 The string can be considered a name or address for an item in the
 340 subject datastructure.
 341
 342 Determining the right “path” for an item in a tree.
 343 ---------------------------------------------------
 344
 345 It’s easy to read off (in reverse) the right sequence of “d” and “i”
 346 from the subject datastructure:
 347
 348 ::
 349
 350    [ n [ n [ n n x ...
 351    i d i d i d d Bingo!
 352