Looking for persistent/immutable tree structure

help
1

I don't mean an indexed tree, I mean an arbitrary hierarchal structure such as what might be used to represent filesystem in memory.

To this point I've been using ego-tree (a Vec and using indexes into the vec to represent links) to represent my tree. Now I also want fast cloning to create versions of the tree with structural sharing.

Does such a thing already exist?

If not any suggestions on how to best to implement?

1 Like
2

It looks like you are looking for ::im

1 Like
3

Thanks.

I'm actually working on my own version of ego-tree, but backed by an im::vector::Vector right now. This seems to be working well enough... but I'm not sure that approach is the best way to do things.

In my naive idea of how immutable data-structures work I think tree shaped data should be the easiest structure to implement. Using im::vector::Vector as a backing store for tree data for the purpose of immutability seems like it might be doing a lot of unnecessary work? (representing a tree in a vector that's represented by a tree behind the scenes?)

As I continue to work in my im::vector::Vector backed tree implementation I though I should ask and see if there's already a immutable tree out there before I reinvent things badly.

Here's the performance that I'm seeing comparing a Vec backed tree to an immutable Vector backed tree:

Create 3 level tree with 100,000 ints:

  • Tree::new 3.8841 ms
  • im_tree::Tree::new ms 11.720 ms

Iterate over those tree with 100,000 ints:

  • Tree::iterate 608.27 us
  • im_tree::Tree::iterate 6.0513 ms

Clone tree with 100,000 ints:

  • Tree::clone 749.31 us
  • im_tree::Tree::clone 48.152 ns
1 Like
4

This does not directly answer your question but may be helpful: https://www.cs.cmu.edu/~rwh/theses/okasaki.pdf

There is a book by the same title by the same author.

1 Like
5

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.