Instructions for Zipper exercise are misleading.

[xxylem]

Hi,

Issue:

I don't know if this is the right place to report this but I found the instructions for Zipper on the Javascript track to be misleading.

The instructions say "Zippers 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)."

In a purely functional setting, the data structure is immutable. The pointer into the data structure could read from inside the structure, but it couldn't modify it in any way. The only way to set a new value is to build new structure with the modified value based on the old data.

The linked Wikipedia page says of list-zippers: "Consequently, a list-zipper is a pair consisting of both the location as a context or starting point, and a recording or path that permits reconstruction from that starting location." And the reference that Wikipedia uses says (in a mythological setting about exploring a labyrinth): "The zipper is a pair of Ariadne's thread and the current sub-labyrinth that the player stands on top."

The point being the Zipper does not contain the full data structure and a pointer. It is two things:

1. The steps (thread) leading up to the focused node (Did I go left or right here? What was the value of the node here? What was the other subtree?)
2. The rest of the structure, from the focused node down (In this case the subtree starting at the focused node).

From these two things, you can rebuild the full structure, including making modifications by creating new subtrees with modified values as you reverse the steps.

Now, I managed to implement a Zipper according to the description on Wikipedia but I am not sure it makes sense to do this in Javascript. As the Wikipedia says, "In a non-purely-functional programming language, it may be more convenient to simply traverse the original data structure and modify it directly (perhaps after deep cloning it, to avoid affecting other code that might hold a reference to it)." But doing this is not a Zipper.

Potential Solutions:

1. Update problem statement to better reflect what a Zipper is. (Recorded thread + rest of structure)

2. Modify the test suite: If we still want a Zipper in Javascript, then the test suite needs to be more detailed. First, the input tree should be frozen/immutable. It should check that all output is also immutable and all intermediate stages do not have side effects (i.e a new Zipper with a new thread and a new tree is created at every stage).

3. Add guiding tests: Have tests that check what the current thread is in the Zipper after running different methods and what the current subtree is. E.g. if zipper is Zipper.fromTree(bt(1, bt(2, null, leaf(3)), leaf(4))), the Zipper returned by zipper.left() will have subtree bt(2, null, leaf(3)) and thread will be something like [{direction: "left", value: 1, otherSubtree: leaf(4)}] This will make the exercise much easier, since the nature of what a Zipper is will be clear. You may not want to do this though since the problem is specified as Hard; a suitable description on the problem page may be sufficient.

4. Change the problem to making a copy of the tree and maintaining a pointer into the tree. The problem would need a different name and couldn't refer to the Zipper data structure.

Anyway, I haven't contributed here before so I don't know what the procedure is for this sort of thing. Also I'm not particularly familiar with Javascript so there might be better solutions than my suggestions above. Please let me know your thoughts and if I should do anything.

Thanks,

Josh

[SleeplessByte]

Hi Josh.

I don't necessarily agree that the current instructions are misleading. The list of functions to implement is pretty conclusive. However, I absolutely agree that we should test for immutability.

I've responded as such in #838.

In general, you can follow the CONTRIBUTING.md document. In this case I would accept a PR that adds tests to test for immutability. I also think it's okay to freeze the input, but that is in no way necessary for this exercise. The input data can be mutable. It doesn't matter.

In short: I agree on 3 + 4 and I also think the wording of the readme could be better, but that's handled in the repository problem-descriptions.

[Upinder123]

can i write a test case ?

[SleeplessByte]

@Upinder123 sorry I never responded. I missed your comment (had notifications turned off due to COVID). Since your comment @joshgoebel has made some changes via #839 ;