zwilias / elm-rosetree

Rosetree/multiway trees in Elm

Multiway trees and a zipper

This library provides a multiway tree (also known as rosetree) datastructure, and a zipper to navigate through it.

A multiway tree is a non-empty tree where every node has a label and a list of children, each of which is a tree.

The basic structure looks like this:

type Tree a = Tree { label : a, children : List (Tree a) }

You can think of it as a multidimensional non-empty list. The root always has a label and may branch out in multiple directions.

A tree zipper is a datastructure that allows navigating through a tree. It represents a waypoint along walking the tree. It can focus on an arbitratry part of the tree, be used to modify and transform that part of the tree, and rebuild the entire tree back up to the root.

Performance and stack-safety

Since trees can grow pretty large, a lot of effort has gone into making all the functions in the Tree module work stack-safely. All the iteration functions in that module are written to make use of Elm's support for tail call elimination.

Making these functions highly performant without losing out on the safety is a continuous effort.

Contributing

Contributions are preferred to take the form of collaboration. Questions, bug reports and feature requests are welcome as GitHub issues. Before starting any concrete work, opening a discussion is very much appreciated.

---

Made with love and released under the BSD-3 license.

elm-rosetree's Issues

Keep the Zipper in place, but change the label types?

Is there a way to map over the Tree that a Zipper keeps, while preserving the Zipper?

The elm-search results for (a -> b) -> Zipper a -> Zipper b aren't encouraging; miyamoen/tree-with-zipper and turboMaCk/lazy-tree-with-zipper are both lazy implementations, which I'd like to avoid for now.

Alternatively, is there a way to start at the base of a Tree, knowing which nodes are ancestors of the focus of a Zipper on the same tree?

---

For context, I'm trying to render a menu that includes data about whether a node is directly reachable by any ancestor of the "selected" node. That is, given:

root
├──file
│   └──open
│       ├──foo
│       │   └──baz
│       └──bar
├──edit
│   └──qux
|
└──about

where open is the focus of the Zipper, I'd like to output something like:

ROOT
├──FILE
│   └──OPEN
│       ├──foo »
│       └──bar
├──edit »
|
└──about

• ROOT, FILE & OPEN are capitalized because they're direct ancestors
  of the focus of the Zipper
• baz & qux are gone, because they're more than 1 step away from the direct
  ancestors of the focus
• foo & edit indicate that there are children below them

Runtime error (maximum call stack size exceeded)

I'm porting my (very large) app to Elm 0.19, and I've just got it to compile and its giving me this runtime error:

index.ts:109 RangeError: Maximum call stack size exceeded
    at Function.f (index.ts:168)
    at A2 (index.ts:168)
    at zwilias$elm_rosetree$Tree$Zipper$forward (index.ts:168)
    at Function.f (index.ts:168)
    at A3 (index.ts:168)
    at Function.f (index.ts:168)
    at A2 (index.ts:168)
    at Function.f (index.ts:168)
    at A2 (index.ts:168)
    at Function.f (index.ts:168)

I'm about to try and investigate more deeply, but I thought it was worth posting it here in case anyone had an idea what might be going on!

foldl : ((a, Zipper/Tree a) -> b -> b) -> b -> Tree a -> b

I need a fold implmenetation which iterates through each (parent, children) tuple in the tree.
Am I correct in saying that this needs to be implemented within the project (as opposed to via the exposed API)?

How to remove a subtree / have children return a list of zippers.

Hey. What's a good way to remove the currently focused tree? Would it make sense to add a removeFocused : Zipper a -> Maybe (Zipper a) that would remove the focused tree and return the parent or root. In case you try to remove the root, it would return Nothing.

Also, would it make sense to change children to children : Zipper a -> List (Zipper a). I'm traversing my tree by using children and in certain cases I need to figure out if the current node has a specific parent.