docs/Zipper.rst

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