# How to find the leftest leaf in a binary tree and focus there

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.

Sneakily cross-posted to Stack Overflow: functional programming - how to find the leftest leaf in a binary tree and focus there - Stack Overflow

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!

2 Likes

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

2 Likes

Youâ€™re absolutely right.

Do you suggest I remove this one from here?

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.

1 Like

I did remove it from SO. I made my question here also very clear. .

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.

Itâ€™s Ok, I made it work, but I am not sure if itâ€™s correct, it would be helpful if you can share what I might improve in that function.

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.

1 Like

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).

P.S. I donâ€™t know swissy personally.

1 Like

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.

Noted

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:

1. any series of down{left,right}, up operations followed by a â€śrebuild treeâ€ť should produce the same tree (up to equality)

2. BTW, instead of â€śNoneâ€ť for a â€śmove left/rightâ€ť on a leaf, maybe you should use the Result type? That seems more appropriate

3. 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

4. properties of replacement of the focus node

5. 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?

1 Like