Lazy (rose) tree with zipper - pre-publish review

[turboMaCk]

Hi folks
I’m working on multiway tree implementation. The library starts getting the shape in which I think I might be able to release it publically. I would like to offer anybody chance to review and send me feedback before I do so though. I’m not going to explain any more details about implementation - hopefully it’s clear from documentation or it should be improved which is one of the reasons I’m posting in here first in first place. Therefore I will focus just on explanation of why i’m posting it in here.

I’m not sure how many if any of you are interested in having a look. I’m just offering space to do so. In my experience debates can get a bit heated sometimes and I would like to prevent it if possible. I can’t promise I will make all the changes one might request however I’m willing to make reasonable compromises to try make everyone as happy as possible. All constructive (including negative) feedback is welcome though. Goal is to discuss technical and practical things and criticism is valuable as well.

I’m not rushing to make it public. I like to think that putting is publicaly out is more like handing it to community so I’ll listen to all of you as much as possible. Anyway we also need to use this library in my company to solve real things we’re facing so there is also certain pressure to get it out so we can use it (even though it’s not that high at this point). Therefore right now I’m thinking about releasing it on Friday. I’m willing to postpone this deadline if there is constructive feedback and work to be done before release (I’ll can deal with my PM if necessary).

I’m also accepting issues and PRs if you want to prefer submit feedback that way.

there is documentation json: https://www.dropbox.com/s/6kpvqdgwhm27ivs/tree-with-zipper.json?dl=0
this is repository: https://github.com/turboMaCk/tree-with-zipper

[rupert]

Does your implementation differ much from this one:

http://package.elm-lang.org/packages/tomjkidd/elm-multiway-tree-zipper/latest

I’ve used “tomjkidd/elm-multiway-tree-zipper” in a number of projects and it is a very useful data structure when working with tree structures and being able to make updates to the tree.

[turboMaCk]

Shame on me - I didn’t even know that package exists. I must have forgot to look for multiway when doing research within the ecosystem. I knew only about now old rose tree package.

Main defferences are described in README though. See Performance and Background parts (please see readme, I don’t want to spam too much here and I also seeking feedback for improvements of whole documentation including README)

Despite laziness, implementations is quite similar. There are some differences in type definitions but they’re equivalent. We’re both using Zipper similar to one described in Learn You Haskell.

There are also differences in API. As readme says my implementation has some specialized functions for building Forest from List using custom constructor defined. This is the thing that led to many decisions including Laziness. Also my implementation misses things that would require evaluation of the Tree as that might potentially blow in stack. Anyway it would be possible to add lazyFolder : (a -> Lazy b -> Lazy b) -> Lazy b -> Tree a -> Lazy b and let decision when to evaluate to user (similarly to LList.lazyFoldr).

I’m pretty happy there is solid Strict implementation. I thought if I shouldn’t implement both Lazy and Strict versions (hence Lazy.Tree structure). I see I don’t have to. Maybe it would be nice to make both implementations easily switchable but I’m not sure if it would be possible due to different characteristic).

Now I think it would be appropriate to add lazy- prefix to name of the package.

[rupert]

I didn’t even know that package exists.

Part of the reason why I asked ;-).

But it looks like your implementation is different because of the performance/lazy aspect.

Looks great, and with a focus on performance I think it really adds something beyond “tomjkidd/elm-multiway-tree-zipper”. My only suggestion would be to mention how and why it differs from that implementation (or any others) right at the start of the README, to help people understand why they might choose your implementation.

I think also the name is good “lazy-tree-with-zipper” because searches for the terms “lazy”, “tree” or “zipper” will find it on the packages site; its nice and literal.

===

I have to admit, I don’t yet understand how laziness helps it perform better. The scenario in which I was using “tomjkidd/elm-multiway-tree-zipper”, was to have a tree of data which was rendered as a collapsable tree view. I added animation when opening/closing sections of the tree and this required updating the animation state held against the node that was being animated. This means quite a few events/second for smooth animation with every event updating the tree, then walking back to the root on that Zipper to produce the new tree in the Model. It seemed to work ok with the strict implementation, although I never tried it with trees beyond a dozen or so nodes. It would be interesting for me to try and much larger tree and see how well animation works with that, and then compare with your implementation.

[turboMaCk]

Laziness as how it is implemented by this package is just a lazy construction of lists. Tree is still defined as type Tree a = Tree a (Forest a). The thing which is different is Forest which is defined as type alias Forest a = Lazy (List (Tree a)) instead of type alias Forest = List (Tree a) and as such sub-trees aren’t evaluated if they aren’t needed.

Not sure how much I understand your use-case but I believe it is almost like the example in README - just includes animation which should be simple to add imho.

In example sub-trees are evaluated only in cases here parent is opened (Tuple.first --> True). This part is just updating item in zipper and view is calling evaluation of forest only for open items.

One problem with strict evaluation is that it’s danger (can go to too much recursion) and slow (exponential). Defining RoseTree in Haskell is easier due to the laziness of the language.

Of course, this all depends on the amount of data you’re dealing with. In our case, we have 4192 items in the tree and those items might have more than one parent so the tree has over 4192 nodes.

I’ve just tested tomjkidd/elm-multiway-tree-zipper within our app quickly to get the feel of its API. It takes over 3s to construct the tree. For different data it fails because construction I’ve hacked together isn’t tail recursive optimized. In comparison with Lazy I got 50ms.

strict:

lazy:

Strict version still makes quite some sense in situations where there are not that much data but for building big Trees is quite slow.

(Tested on Arch Linux, AMD Ryzen 1800x (16 thread 3.6GHz), 32GB RAM, Chromium)

[turboMaCk]

Edited: not 200ms but 50ms probably. I was looking on a bad call. 200ms is decoding which happens in both cases (as you can see A2 call in both screenshots. I think this is probably the Tree construction:

[turboMaCk]

oh almost forgot… sorry I’m a bit in hurry right now.

Looks great, and with a focus on performance I think it really adds something beyond “tomjkidd/elm-multiway-tree-zipper”. My only suggestion would be to mention how and why it differs from that implementation (or any others) right at the start of the README, to help people understand why they might choose your implementation.

This is really great idea! Thanks, I’ll add more info to REAME as well as a link to tomjkidd/elm-multiway-tree-zipper.

[turboMaCk]

Looks like there won’t be more feedback - I’m going to publish it tomorrow as planned. Once again thx @rupert for feedback and sory for bumping this.