Zipper instructions need to be replaced with the following:
# Description
Creating a zipper for a [binary tree][binary tree].
[Zippers][zipper] are a purely functional way of navigating within a data structure and manipulating it.
They essentially contain a data structure and a pointer into that data structure (called the focus).
For example given a rose tree (where each node contains a value and a list of child nodes) a zipper might support these operations:
- `from_tree` (get a zipper out of a rose tree, the focus is on the root node)
- `to_tree` (get the rose tree out of the zipper)
- `value` (get the value of the focus)
- `left` (if the focus has a left child, move the focus there and return the zipper)
- `right` (if the focus has a left child, move the focus there and return the zipper)
- `up` (if the focus has a parent, move the focus there and return the zipper)
- `set_value` (set the value of the focus and return the zipper)
- `set_left` (set the left child of the focus and return the zipper)
- `set_right` (set the left child of the focus and return the zipper)
- `delete` (remove the focus and all subtrees, move focus to parent if possible, return the zipper)
[zipper]: https://en.wikipedia.org/wiki/Zipper_%28data_structure%29
[binary tree]: https://en.wikipedia.org/wiki/Binary_tree
Zipper tests need to be updated with deletion, for example:
The above have to be done in the problem-specifications repo and on each track that features the Zipper exercise (where the test must be adjusted to each language). These are the tracks concerned:
Ruby
Haskell
Tcl
Python
Visual Basic
F#
Powershell
C#
Cairo
Clojure
Elixir
Erlang
Gleam
Go
Java
OCaml
Odin
Scala
Unison
I might be able to help with some of these, but not many >.>
That looks like a lot of work… I think problem specifications should be very thoroughly checked before uploading, because otherwise it’s a pain to fix. Unless there’s some automation in place?
Short answer: Look at what the changes are, and it tells you why they’re needed.
Long answer: There are three problems here.
The names of the functions in the instructions don’t match the names of the functions tested.
Function delete is not tested.
MOST IMPORTANTLY: The instructions say that left and right (also see set_left, set_right and delete) refer to siblings, but the tests expect that left and right refer to children. Personally, that threw me for a loop. I kept going through the test code trying to figure out what the tests actually wanted, and still couldn’t; until someone else figured it out and told me what the actual expectations were.
The names used in the test suite are track-dependent so that’s to be expected. We probably shouldn’t be highlighting the names in the instructions like they were code given we’re giving example behaviors of a zipper. That is a bit confusing.
This would be a separate discussion from rewriting the instructions since we’re updating the expected behavior.
Individual maintainers are responsible for syncing their tracks’ canonical tests so you don’t need to worry about that. Some tracks have test generators, some do it manually. A few might even decide to opt out of adding new tests. Most tracks also have a GH action that alerts if there are changes in the problem specifications repo.
Like I said earlier, the main problem here is that instructions specify moving the focus to siblings but tests expect moving the focus to children (which is not obvious by looking at the tests themselves).
The operations listed in description.md and in the canonical data are out of sync. I think there’s value in syncing them.
problem-specifications/exercises/zipper » jq -r '.cases[]|.input.operations[].operation' canonical-data.json | sort -u
left
right
set_left
set_right
set_value
to_tree
up
value
» grep -o -e '- `.*`' description.md | tr -dc 'a-z_\n' | sort
delete
from_tree
insert_after
insert_before
next
prev
set_value
to_tree
up
value
At the very least, (1) all operations in the canonical data ought to be listed in the description. At a lesser importance, (2) operations in the description not in the canonical data should be (2a) removed from the description, (2b) added to the canonical data, (2c) flagged as probably not in the tests or (2d) moved to an append file.
At the risk of sounding like a broken record… you guys realise that changing the description of each operation is more important than changing its name, right?
It’s easy for a student to realise that the names are different. The difficult part is knowing what is being asked of them.
Please keep in mind that all of this change in problem specs doesn’t guarantee that all tracks will update quickly (or at all). Everyone does their best, but sometimes maintainers get busy or overwhelmed.
I’d be okay with overhauling the introduction completely. Most of the introduction covers an example zipper tree implementation that isn’t necessarily the same as the one in the test suite. So let’s ditch it and describe the general categories of operations like navigating, accessing data, and modifying that data. Then, students can go to the test suite for specifics.
I can noodle on it this weekend. It might be useful to put some ASCII art in here too like we did in Relative Distance. I had trouble visualizing the zipper from just the text.
# Description
Creating a zipper for a [binary tree][binary tree].
[Zippers][zipper] are a purely functional way of navigating within a data structure and manipulating it.
They essentially contain a data structure and a pointer into that data structure (called the focus).
For example given a rose tree (where each node contains a value and a list of child nodes) a zipper might support these operations:
- create a zipper out of a rose tree, with the focus initially on the root node
- get the underlying rose tree from the zipper
- get the value of the focus
- move the focus to its left child, if it exists
- move the focus to its right child, if it exists
- move the focus to its parent, if it exists
- set the value of the focus
- set the left child of the focus
- set the right child of the focus
- remove the focus (with all its subtrees); new focus should go to the parent if possible
Apart from the first three operations, all others should return the zipper on success.
[zipper]: https://en.wikipedia.org/wiki/Zipper_%28data_structure%29
[binary tree]: https://en.wikipedia.org/wiki/Binary_tree
We could patch the existing instructions but starting from scratch and being more generic in the instructions leads to docs that better stand the test of time.
Oops, I did say introduction earlier. I meant we should rewrite the instructions specifically from scratch. I figured we could come back later for the introduction separately, but now that I opened that door, we might as well go through it and see what’s on the other side.
