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

# MultiwayTree

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

# Types

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.

# Operations

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

# Mapping

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).

# Sorting

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)
```
```