turbomack / lazy-tree-with-zipper

Lazy rose tree (multiway tree) with zipper. In Elm

Lazy Tree with Zipper

This is pure Elm rose tree with zipper implementation. In the context of Elm, this data structure is mostly useful for building hierarchical interfaces like menus, data browsers or filters.

Main features of this library are things like easy building tree structure from flat Lists with very good performance characteristics, powerful and extensible zipper and feature-rich API.

Performance

Tree is using custom List like implementation (LList) to enable lazy level after level evaluation of tree. In fact LList is just a function that constructs plain old List. This approach is the main performance optimization used in this library.

There is another library implementing same idea in slightly different way tomjkidd/elm-multiway-tree-zipper. The main difference is that elm-multiway-tree-zipper implementation is strict so the whole Tree is immediately evaluated. Implementation provided by this package is optimized for situations in which it isn't necessary to construct the whole structure immediately. In situations where Tree is expanded level by level this implementation yields much better performance than strict implementation, especially for large trees. You can find basic comparison in performance.

Feedback and contributions to both code and documentation are very welcome.

Usage

To install this package run:

$ elm install turboMaCk/lazy-tree-with-zipper

This is an example application that renders levels of items as nested tree with toggling between open and closed state in every level:

module Main exposing (main)

import Browser
import Html exposing (Html)
import Html.Events as Events
import Lazy.Tree as Tree exposing (Tree(..))
import Lazy.Tree.Zipper as Zipper exposing (Zipper)


main : Program () Model Msg
main =
    Browser.sandbox
        { init = init
        , update = update
        , view = view
        }



-- Model


type alias Item =
    { id : Int
    , name : String
    , parent : Maybe Int
    }


items : List Item
items =
    [ { id = 1, name = "Foo", parent = Nothing }
    , { id = 2, name = "Bar", parent = Nothing }
    , { id = 3, name = "Baz", parent = Nothing }
    , { id = 4, name = "Foobar", parent = Just 1 }
    , { id = 5, name = "Bar child", parent = Just 2 }
    , { id = 6, name = "Foobar child", parent = Just 4 }
    ]


{-| Zipper of pair where first value means `isOpen` and second contain Item details.
-}
type alias Model =
    Zipper ( Bool, Item )


init : Model
init =
    let
        root =
            { id = -1, name = "root", parent = Nothing }
    in
    List.map (\b -> ( False, b )) items
        |> Tree.fromList (\p ( _, i ) -> Maybe.map (.id << Tuple.second) p == i.parent)
        |> Tree ( False, root )
        |> Zipper.fromTree



-- Update


type Msg
    = Toggle (Zipper ( Bool, Item ))


update : Msg -> Model -> Model
update (Toggle zipper) _ =
    Zipper.updateItem (\( s, i ) -> ( not s, i )) zipper



-- View


view : Model -> Html Msg
view zipper =
    Html.ul [] [ viewLevel (Zipper.root zipper) ]


viewLevel : Zipper ( Bool, Item ) -> Html Msg
viewLevel zipper =
    let
        ( isOpen, item ) =
            Zipper.current zipper
    in
    Html.li []
        [ Html.a [ Events.onClick <| Toggle zipper ]
            [ if not (Zipper.isEmpty zipper) then
                Html.span []
                    [ if isOpen then
                        Html.text "- "

                      else
                        Html.text "+ "
                    ]

              else
                Html.text ""
            , Html.text item.name
            ]
        , Html.ul [] <|
            if isOpen then
                Zipper.openAll zipper
                    |> List.map viewLevel

            else
                []
        ]

Background

I've spent about a year experimenting with different ideas of Rose Tree implementation optimized for needs of building UIs for recursive data. The biggest problem turned out to be performance. Usually, data for web applications are coming from a server which uses SQL database as storage. API usually then renders flat JSON or any other data format which uses references to describe recursive relationships. Therefore one of the main features that are needed is an efficient and easy way to build tree from a list of data. This usually results in quadratic complexity. Since one item might be a child of multiple other things there has to be at least one iteration over the whole list of data. Also by definition using such data for building rose tree might result in infinitely deep resulting tree.

Those are the things I've experimented with over time:

• Strict based (Tree a (List a)) - not that great performance but OK until you hit too much recursion.
• Lazy List based implementation (Tree a (LazyList a)) - runs into too much recursion even on simpler data.
• Continuation Passing / CPS - very slow (hitting scripts runs for too long) - might have been an issue with a particular algorithm.
• Lazy List construction - this is what this package is using - very best performance.

License

This package is released under BSD-3-Clause license. See LICENSE file for more info.

lazy-tree-with-zipper's Issues

implement missing handy functions

• Tree.foldr (lazy)
• Tree.foldl (lazy)
• LList.sortBy
• LList.sortWith
• Tree.sortBy
• Tree.sortWith

package name to lazy-tree-with-zipper

• rename repository
• update readme

fix ci

When I was working on this Travis has experienced some incidents so CI wasn't working. Now it seems to be working but not properly stopped - we should fix it.

missing comonadic operations

2.0.0 release

List of things that I want to change in next release:

• Breadcrumbs to opaque type
• Zipper to opaque type <- not sure yet
• Expose Tree constructor

exposing Lazy

Hey @turboMaCk!

I would like to be able to use Lazy.map in order to lift regular list functions (such as take) into LList. Would you mind exposing the Lazy module to users?

My immediate use case is to implement a trunk tree function that prunes all but the first children. I can do that like

trunk : Tree a -> Tree a
trunk (Tree a branches) =
    case LList.head branches of
        Just tree ->
            Tree a <| LList.singleton <| trunk tree

        Nothing ->
            Tree a LList.empty

But with Lazy.map I would be able to

trunk : Tree a -> Tree a
trunk (Tree a branches) =
    Tree a <| Lazy.map (List.map trunk << List.take 1) branches

which would not only be terser, but actually keep laziness too.

If exposing the entirety of Lazy seems like an overkill, an alternative I see is exposing a function like LList.liftLazy or some such, which would be just Lazy.map for LLists.

Also, I saw lazy fold functions in LList, but they are not exposed. They would solve my problem, but exposing a more general interface would obviate the need for exposing such lazy-lifted list functions one by one.

Tree construction is based on algorithm with quadratic complexity

Summary: This is not an immediate issue for us, just an idea for addition of more efficient tree-constructing function.

The implementation of Lazy.Tree.fromList (

lazy-tree-with-zipper/src/Lazy/Tree.elm

Lines 460 to 467 in ad09ba6

	fromList : (Maybe a -> a -> Bool) -> List a -> Forest a
	fromList isParent =
	fromList_ Nothing isParent
	fromList_ : Maybe a -> (Maybe a -> a -> Bool) -> List a -> Forest a
	fromList_ parent isParent list =
	LL.llist (List.map (constructTree isParent list) << List.filter (isParent parent)) list

) has quadratic complexity.

Most of the time this is not an issue, because you rarely need to expand (force) the whole (sub)tree, so the complexity is spread over time as each node is being expanded. But there are usecases, where such expansion is needed (remember unwindAllDatapoints from pro-next?).

To illustrate the issue imagine a pathological example: a tree that looks like a long path of 1000 nodes with no branching (1 -> 2 -> 3 -> 4 -> ... -> 1000). Expanding each level does linear traversal of the whole list, so expanding the whole tree will need to traverse the list 1000 times IF the tree is fully expanded.

An idea how this could be improved is that you could have less general function for constructing the tree, where the "thunk" in each node wouldn't have linear complexity, but just logarithmic. Something like

fromListFaster : (item -> comparable) -> (item -> Maybe comparable) -> List item -> Forest item
fromListFaster getItemId getParentId  =
    let dictFromParentIdToListOfChildren :: Dict comparable (LList item) 
         -- The point: this dict ^ is just created ONCE with n*log n complexity;
         -- The benefit: function that is hidden behind the lazy thunk would just be `log n` lookup in this dict instead of linear traversal of the whole list
        -- forest roots would be special-cased here, as their parent is Nothing so they wouldn't be in the above dict
        forestRoots = ...
        lookupChildren item = Dict.get (getItemId item) dictFromParentIdToListOfChildren |> Maybe.withDefault EMPTY_LIST
    in 
    -- call some helper function using lookupChildren

Anyway this is just an idea. Feel free to close it if you don't think it would be worth it.

missing filterMap on Zipper