This is an alternative site for discovering Elm packages.
You may be looking for the
official Elm package site
instead.

A library for constructing multi-way trees. Each Tree carries two pieces of information, it's datum and children.

type Tree a
= Tree a (Forest a)

A type to keep track of datum and children.

type alias Forest a =
List (Tree a)

A list of Trees. Convenient for describing children.

datum : Tree a -> a

Access the datum of the current tree

children : Tree a -> Forest a

Access the children of the current tree

foldl : (a -> b -> b) -> b -> Tree a -> b

Reduce a Tree from the left.

foldr : (a -> b -> b) -> b -> Tree a -> b

Reduce a Tree from the right.

flatten : Tree a -> List a

Flattens a Tree into a List where the root is the first element of that list.

tuplesOfDatumAndFlatChildren : Tree a -> List ( a, List a )

A special version of flatten which flattens a Tree into a List of Tuples like (element, [all elements in subtree])

```
(Tree.tuplesOfDatumAndFlatChildren
Tree "a"
[ Tree "b" []
, Tree "c" []
, Tree "d" []
])
== [ ( "a", [ "b", "c", "d" ] ), ( "b", [] ), ( "c", [] ), ( "d", [] ) ]
```

filter : (a -> Bool) -> Tree a -> Maybe (Tree a)

Filter the MultiwayTree. Keep only elements whose datum satisfy the predicate.

filterWithChildPrecedence : (a -> Bool) -> Tree a -> Maybe (Tree a)

Filter the MultiwayTree. If the predicate is True for a Child the entire path to the root will be part of the result Tree.

length : Tree a -> Int

Return the length of the Tree. Calculated recusively as datum (1) + length of children (n) Since a MultiwayTree is never empty this function will never return Int < 1.

insertChild : Tree a -> Tree a -> Tree a

Inserts a Tree as the first child of a Tree

appendChild : Tree a -> Tree a -> Tree a

Inserts a Tree as the last child of a Tree

map : (a -> b) -> Tree a -> Tree b

Map over the MultiwayTree

mapListOverTree : (a -> b -> result) -> List a -> Tree b -> Maybe (Tree result)

Map a Function over a List and a MultiwayTree.

indexedMap : (Int -> a -> b) -> Tree a -> Maybe (Tree b)

Same as map but the function is also applied to the index of each element (starting at zero).

sortBy : (a -> comparable) -> Tree a -> Tree a

Sort values by a derived property. Does not alter the nesting structure of the Tree, that is it does not move Nodes up or down levels.

```
(sortBy identity
Tree "a"
[ Tree "b" []
, Tree "d" []
, Tree "c" []
])
== (Tree "a"
[ Tree "b" []
, Tree "c" []
, Tree "d" []
])
```

sortWith : (a -> a -> Order) -> Tree a -> Tree a

Sort values with a custom comparison function like:

```
flippedComparison a b =
case compare a b of
LT -> GT
EQ -> EQ
GT -> LT
This is also the most general sort function, allowing you
to define any other.
```

```
module MultiwayTree
exposing
( Tree(..)
, Forest
, datum
, children
, map
, mapListOverTree
, indexedMap
, filter
, filterWithChildPrecedence
, flatten
, tuplesOfDatumAndFlatChildren
, foldr
, foldl
, length
, insertChild
, appendChild
, sortBy
, sortWith
)
{-| A library for constructing multi-way trees. Each Tree carries two pieces of
information, it's datum and children.
# Types
@docs Tree, Forest
# Operations
@docs datum, children, foldl, foldr, flatten, tuplesOfDatumAndFlatChildren, filter, filterWithChildPrecedence, length, insertChild, appendChild
# Mapping
@docs map, mapListOverTree, indexedMap
# Sorting
@docs sortBy, sortWith
-}
{-| A type to keep track of datum and children.
-}
type Tree a
= Tree a (Forest a)
{-| A list of Trees. Convenient for describing children.
-}
type alias Forest a =
List (Tree a)
{-| Access the datum of the current tree
-}
datum : Tree a -> a
datum (Tree datum children) =
datum
{-| Access the children of the current tree
-}
children : Tree a -> Forest a
children (Tree datum children) =
children
{-| Inserts a Tree as the first child of a Tree
-}
insertChild : Tree a -> Tree a -> Tree a
insertChild childTree (Tree datum children) =
Tree datum (childTree :: children)
{-| Inserts a Tree as the last child of a Tree
-}
appendChild : Tree a -> Tree a -> Tree a
appendChild childTree (Tree datum children) =
Tree datum (children ++ [ childTree ])
{-| Reduce a Tree from the left.
-}
foldl : (a -> b -> b) -> b -> Tree a -> b
foldl f accu (Tree datum children) =
let
treeUnwrap (Tree datum_ children_) accu_ =
List.foldl treeUnwrap (f datum_ accu_) children_
in
List.foldl treeUnwrap (f datum accu) children
{-| Reduce a Tree from the right.
-}
foldr : (a -> b -> b) -> b -> Tree a -> b
foldr f accu (Tree datum children) =
let
treeUnwrap (Tree datum_ children_) accu_ =
f datum_ (List.foldr treeUnwrap accu_ children_)
in
f datum (List.foldr treeUnwrap accu children)
{-| Flattens a Tree into a List where the root is the first element of that list.
-}
flatten : Tree a -> List a
flatten tree =
foldr (::) [] tree
{-| A special version of flatten which flattens a Tree into a List of Tuples like (element, [all elements in subtree])
(Tree.tuplesOfDatumAndFlatChildren
Tree "a"
[ Tree "b" []
, Tree "c" []
, Tree "d" []
])
== [ ( "a", [ "b", "c", "d" ] ), ( "b", [] ), ( "c", [] ), ( "d", [] ) ]
-}
tuplesOfDatumAndFlatChildren : Tree a -> List ( a, List a )
tuplesOfDatumAndFlatChildren (Tree datum children) =
[ ( datum, List.concatMap flatten children ) ] ++ (List.concatMap tuplesOfDatumAndFlatChildren children)
{-| Return the length of the Tree. Calculated recusively as datum (1) + length of children (n)
Since a MultiwayTree is never empty this function will never return Int < 1.
-}
length : Tree a -> Int
length tree =
foldr (\_ accu -> accu + 1) 0 tree
{-| Map over the MultiwayTree
-}
map : (a -> b) -> Tree a -> Tree b
map fn (Tree datum children) =
let
mappedDatum =
fn datum
mappedChildren =
List.map (\child -> map fn child) children
in
(Tree mappedDatum mappedChildren)
{-| Map a Function over a List and a MultiwayTree.
-}
mapListOverTree : (a -> b -> result) -> List a -> Tree b -> Maybe (Tree result)
mapListOverTree fn list (Tree datum children) =
case list of
[] ->
Nothing
head :: [] ->
let
mappedDatum =
fn head datum
in
Just (Tree mappedDatum [])
head :: rest ->
let
mappedDatum =
fn head datum
listGroupedByLengthOfChildren =
splitByLength (List.map length children) rest
mappedChildren =
List.map2 (\l child -> mapListOverTree fn l child) listGroupedByLengthOfChildren children
|> List.filterMap identity
in
Just (Tree mappedDatum mappedChildren)
splitByLength : List Int -> List a -> List (List a)
splitByLength listOflengths list =
splitByLength_ listOflengths list []
splitByLength_ : List Int -> List a -> List (List a) -> List (List a)
splitByLength_ listOflengths list accu =
case listOflengths of
[] ->
List.reverse accu
currentLength :: restLengths ->
case list of
[] ->
List.reverse accu
head :: rest ->
splitByLength_ restLengths (List.drop currentLength list) ((List.take currentLength list) :: accu)
{-| Same as map but the function is also applied to the index of each element (starting at zero).
-}
indexedMap : (Int -> a -> b) -> Tree a -> Maybe (Tree b)
indexedMap f tree =
mapListOverTree f (List.range 0 (length tree - 1)) tree
{-| Filter the MultiwayTree. Keep only elements whose datum satisfy the predicate.
-}
filter : (a -> Bool) -> Tree a -> Maybe (Tree a)
filter predicate (Tree datum children) =
if predicate datum then
Just (Tree datum (List.filterMap (filter predicate) children))
else
Nothing
{-| Filter the MultiwayTree. If the predicate is True for a Child the entire path to the root will be part of the result Tree.
-}
filterWithChildPrecedence : (a -> Bool) -> Tree a -> Maybe (Tree a)
filterWithChildPrecedence predicate (Tree datum children) =
case List.filterMap (filterWithChildPrecedence predicate) children of
[] ->
if predicate datum then
Just (Tree datum [])
else
Nothing
children_ ->
Just (Tree datum children_)
{-| Sort values by a derived property. Does not alter the nesting structure of
the Tree, that is it does not move Nodes up or down levels.
(sortBy identity
Tree "a"
[ Tree "b" []
, Tree "d" []
, Tree "c" []
])
== (Tree "a"
[ Tree "b" []
, Tree "c" []
, Tree "d" []
])
-}
sortBy : (a -> comparable) -> Tree a -> Tree a
sortBy fn (Tree datum children) =
let
sortedChildren =
List.sortBy (\(Tree childDatum children_) -> fn childDatum) children
|> List.map (sortBy fn)
in
(Tree datum sortedChildren)
{-| Sort values with a custom comparison function like:
flippedComparison a b =
case compare a b of
LT -> GT
EQ -> EQ
GT -> LT
This is also the most general sort function, allowing you
to define any other.
-}
sortWith : (a -> a -> Order) -> Tree a -> Tree a
sortWith comperator (Tree datum children) =
let
sortedChildren =
List.sortWith (\(Tree first _) (Tree second _) -> comperator first second) children
|> List.map (sortWith comperator)
in
(Tree datum sortedChildren)
```