From a binary tree, I want to construct a zipper with a focus on the leftest leaf.
type ('a, 'b) bin_tree =
| Leaf of 'b
| Node of 'a * ('a, 'b) bin_tree * ('a, 'b) bin_tree
type ('a, 'b) bin_context =
| Top
| LContext of ('a * ('a, 'b) bin_context * ('a, 'b) bin_tree)
| RContext of ('a * ('a, 'b) bin_context * ('a, 'b) bin_tree)
type ('a, 'b) z = BZ of ('a, 'b) bin_context * ('a, 'b) bin_tree
This is what I have tried:
let go_down (BZ(c, t)) =
match t with
| Leaf(w) -> None
| Node(v, l, r) ->
match l with
| Leaf(w) -> Some (BZ(LContext(v, c, Leaf(w)), l))
| Node(u, u_l, u_r) -> Some (BZ(LContext(v, c, u_r), u_l))
(* val leftest_leaf_focus : ('a,'b) bin_tree -> ('a,'b) z *)
let leftest_leaf_focus t =
let zp = (BZ(Top, t)) in
(let rec leftest_leaf_focus_rec zpp =
match (go_down zpp) with
| None -> zpp
| Some z' -> leftest_leaf_focus_rec z'
in leftest_leaf_focus_rec zp)
It seems to work, but I don’t know if my implementation is correct, can you help with sharing what might be wrong with it? I mean by correct: output is a zipper with a focus on the left-most leaf.
It’s good practice to wait at least a nanosecond before cross-posting to other forums, and to link them, in order to avoid duplicating effort. Please don’t be a help vampire!
Thanks for the advice. I don’t think it was sneakily, I thought it was a good question anyways, wherever it got the answer, it would be helpful for learners
It’s much more helpful if learners who find this question are able to find an answer posted to Stack Overflow, for example. But even more so, it’s helpful for potential answerers who might spend significant time trying to understand and answer a question, that their time isn’t wasted when a thorough answer has already been posted elsewhere. Eventually this will lead to fatigue, which in turn leads to less time and energy spent answering, which leads to poorer answers or just not bothering to answer at all.
Rather the opposite perhaps. Since you seem to be looking more for advice and mentoring than a specific answer to a specific problem. Trying to force that into Stack Overflow’s format just ends up as a vague question without sufficient context to give a good answer.
I suggest writing this into a longer form where you explain your high-level goal, what you’ve done so far to achieve it and what’s confusing you.
I don’t think most people know what leaf zippers are, so explaining that would be a good start. Then, what do you want leftest_leaf_focus to return in the case where it returns None now?
Ah ok, I meant by leaf zipper, working on leaf nodes in zipper structures. In all cases, leftest_leaf_focus returns a zipper with a focus on the left-most leaf.
A good starting point is to try to put in words what “correct” is supposed to mean. In particular, you could try to describe what properties you expect from a zipper and try to test those.
As a hint: for navigation structure like the zipper, it should be always possible to reconstruct the initial tree from any zipper state.
I added a note about what I mean by correct. Also, sometimes, even when the code is working, feedback of other experts is always valuable, it addresses other aspects, or suggest an improvement, it helps in the learning process very much.
I can’t speak for others – the spirit of discuss.ocaml.org seems to be somewhat informal/relaxed in the time I’ve been here. Since you stated an opinion on @swissy’s post, I think it should be fair for me to do the same.
And my opinion is that I think it was a bit harsh to use works like “sneaky” and “help vampire” in reference to swissy. I think whatever grouse you had on cross posting, the way the question was stated etc. could have been stated in a more kindly way.
I’m sure we’re all busy doing our stuff so I personally will just let it be here, having expressed my feelings. I hope you can take my feedback in a positive spirit as swissy did to yours (he seems to be very new on this forum).
Thanks @sid. Though, I think that @glennsl didn’t intend anything, maybe that’s how he handles things always. I was not offended. He, as you, are already good human beings by being out there trying to help in the first place.
By “sneakily” I just mean that it’s cross-posted without mention. Perhaps a bad choice of word. “Help vampire” refers to asking questions in a way that is unnecessarily “sucking” the time and energy of those trying to help. It’s an established term that can be searched for, which I think is helpful.
I only just now learned what a zipper is. So maybe this isn’t the right way to go about thinking of things, but: maybe it’s worth writing down a set of properties of a zipper datastructure, and then using those to write tests ? For instance, I can imagine:
any series of down{left,right}, up operations followed by a “rebuild tree” should produce the same tree (up to equality)
BTW, instead of “None” for a “move left/right” on a leaf, maybe you should use the Result type? That seems more appropriate
any sequence of successful (returns OK) operations on a zipper has an inverse sequence, and when the two sequences are applied, you get back the original zipper datastructure
properties of replacement of the focus node
properties of how replacement of the focus node interacts with the rest of the zipper (the context)
Maybe a way to think of it is: put aside your implementation and try to imagine how to write tests so that you can start writing an implementation that will satisfy those tests.
Test-driven development (TDD) is a great way of proceeding in an area where you feel unsure of your knowledge. I recently rewrote a PPX rewriter for JSOO objects: I know nothing of JSOO, and didn’t really understand it. I had a PPX rewrier for JSOO objects that somebody had written, but I wanted to write it a different way. So I fed it the simplest inputs, and got outputs. I wrote a test for that, then wrote my rewriter that produce that same behaviour. And then I started adding more complexity to inputs, eventually getting to where I was able to deal with the original rewriter’s entire testsuite. Then I felt confident enough to extend past that testsuite, writing new tests that the original rewriter failed.
Seriously, try TDD.
P.S. Often I find that people skip really simple tests, in favor of more-complex tests. There’s a tendency to want to keep the number of tests smaller. I think this is a mistake, b/c tests are cheap, and bugs are unforeseeable. So if you leave out a test b/c “surely it’s covered by this other test” then you’re foreseeing where bugs will and will not arise. Much easier to just keep all those tests, in the knowledge that hey, they were cheap and cheerful, and what’s the downside?
