Lesson 8 – Missing Links


Introduction

Now that we have a fairly good understanding of how recursion works, we should look at ways of creatively using our newfound tool to do something interesting.

The goal of this series of tutorials, afterall is to give you a toolkit with which you can make your own fun and interesting things on Urbit.

In this lesson, we’ll also introduce some new tools for working with lists, in this case tapes (or strings of text), that might also help you to do creative things

Goal

Write a generator that takes a tape and produces a copy with every nth character removed. e.g. from “this is a tape” to (assuming every third character is removed) “ths s  tpe”. That is, remove 'i', 'i', 'a', 'a' from the tape and return the product as those values are in the multiples-of-three positions (3, 6, 9, 12)

Standard Library Function List


lent

SyntaxSummary
(lent <list>)Standard Library function which returns the number of items in a list

Standard Library function which returns the number of items in a list


Exercise

Try this in dojo:

(lent ~[1 2 3 4])
4
(lent ~[[1 2] [3 4] [5 6] [7 8]])
4

Note: both of these return 4 because there are 4 terms in each - the second list is a list of 4 cells

oust

SyntaxSummary
(oust [<position> <number of items>] <list>)Standard Library function to remove <number of items> items from a list, starting at <position>

Standard Library function to remove <number of items> items from a list, starting at <position>


Exercise

Try this in dojo:

=test ~[1 2 3 4]
(oust [1 2] `(list @ud)`test)
[1 4]

Note: the numbering of positions in a list starts with 0, as with many things in computer science and Urbit more generally - thus the positions of the list ~[1 2 3 4] are 0, 1, 2, and 3, respectively - this is exceedingly important to remember.


Walkthrough


|=  [long-tape=tape n=@ud]
=|  removals=@ud
=/  remover=@ud  n
^-  tape
|-
?:  (gth (sub remover removals) (lent long-tape))
  long-tape
$(remover (add n remover), removals +(removals), long-tape (oust [(dec (sub remover removals)) 1] long-tape))

  • |= [long-tape=tape n=@ud]
    |= creates a gate and requests a cell of a tape and a number, specifically an unsigned decimal, @ud argument

    • =| removals=@ud
      =| creates an @ud with a face named removals and gives it a value of 0 (the bunt value). This will be used to count the number of times we’ve gone through recursion/removed an element from the list.
      Given that we are removing one character from the tape each recursion, we will need to take a multiple of our n value (remove the 3rd, 6th, 9th term) and subtract the number of times we’ve gone through recursion to identify the proper term to remove. If we did not, we would progressively remove one more than our indicated position (removing the 3rd, 7th, 11th term), as the index numbering of each element will change as we remove items.

      • =/ remover=@ud n
        =/ creates an @ud with a face of remover and sets it equal to our input value n
        We will use remover to do the actual removal of terms from the tape, and will modify it by n on each recursion. Note that we will need to decrement this by one, each time we remove a value, as list indexing starts at 0, so if we say to remove the first element, we need to remove the 0 index element, and so on (however, also note that if we actually asked to remove every 1 item, we would remove every element from the list).

        • ^- tape
          ^- casts our output as a tape

          • |-
            |- creates a trap, which will be the point to which our generator recurses, when $ is called. Again, and technically, the trap creates its own small core that doesn't take a sample. The trap is a part of the arm buc of the gate, but when we call to recurse the arm buc at the bottom, we are speaking of this arm buc.

            • ?: (gth (sub remover removals) (lent long-tape))
              ?: creates a test with branching outcomes. This test is somewhat harder to read than our prior examples -- the purpose is to make sure the item we’re trying to remove each recursion actually exists.
              If the test is true, we will print long-tape as it has been modified
              If the test is false, we will proceed to $ and after making some modifications to values with various faces.
            • long-tape
              long-tape prints the tape that we input, post modifications from $ (below)
            • $(remover (add n remover), removals +(removals), long-tape (oust [(dec (sub remover removals)) 1] long-tape))
              In prior iterations of recursion, we’ve used %= to effect recursion. Here we’re using a shorthand for the same operation $(a change-to-a, b change-to-b) is the same as:

              %= $
              a change-to-a
              b change-to-b
              ==

              Given the shorthand identified above, this call to $ is equivalent to:

              %=  $
                remover    (add n remover)
                removals   +(removals)
                long-tape  (oust [(dec (sub remover  removals)) 1] long-tape)
              ==

              These equivalent constructions of the call to buc perform the following changes:

              • Sets remover equal to remover + (current value of) n
              • Increments removals by one
              • Takes long-tape modifies it by ousting from the position:
                ➼ One less than (remover - removals)
                the following number of elements from the tape called long-tape:
                ➼ 1
              • Note: We use 1 less than (remover - removals) here because the terms in a list (or tape) are addressed 0 through n, so the 4th item in the list in common parlance is in position 3, and so on
  1. Request an input of a cell of a tape and an @ud and form a gate
    |=  [long-tape=tape n=@ud]
  2. Evaluate the $ arm of the gate
    Add a default (bunt) value with a face of “remove” that is an @ud to the subject
    =|  removals=@ud
  3. Declare a value with a face of “remover” that is an @ud and give it the value of our input @ud, called n
    =/  remover=@ud  n
  4. Cast the output of the evaluation of $ as a tape
    ^-  tape
  5. Form a trap, with one arm called $, which is evaluated immediately
    |-
  6. Create a branching test, checking whether remover minus removals is longer than the length of (note) the length of the remaining tape, each recursion, and branch based on the results
    ?:  (gth (sub remover removals) (lent long-tape))
  7. If remover minus removals is greater than the length of the tape, we print the tape, as there are no more removals to complete
     long-tape
  8. If remover minus removals is equal to or less than the length of long-tape, then we make the changes prescribed and repeat the generator from the trap (Step 6)
    $(remover (add n remover), removals +(removals), long-tape (oust [(dec (sub remover removals)) 1] long-tape))

Readings

Homework

  1. Do Exercises 1.5(b) and (g) from the reading 1.5 Lists above, and check your answers against the solutions at the bottom of the page.
  2. Submit the provided solution after adding your own comments to explain each line.
  3. Write a version of the above code that removes every nth position, counting from the left, but operating from right to left
    • For example, remove the 3rd item from the following list (the items are numbered in the order in which they should be removed):
      ~[0 0 3 0 0 2 0 0 1 0]