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

Graph.Tree

This module provides a simple tree data type of arbitrary arity (a rose tree). There are primitives for building and traversing such a tree.

Data

type Tree label = MkTree Int (Maybe (label, List (Tree label)))

Data type representing an n-ary tree with node labels of type a Building such a tree is done with the empty, leaf and inner smart constructors. An example for a tree with three leafs and a root node:

tree = inner 1 [leaf 2, leaf 3, leaf 4]
type alias Forest label = List (Tree label)

This is just an alias for a list of trees, called a forest in the literature.

Building

empty : Tree label

Construct an empty tree with no nodes.

leaf : label -> Tree label

Construct a tree with a single node from a value for the node's label.

tree : Tree Int
tree = leaf 42
inner : label -> List (Tree label) -> Tree label

Construct a new tree by inner label children, combining a number of subtrees children with a label for the new inner node which will be the root of the tree. Empty subtrees are filtered out. An example:

tree1 = inner 1 [leaf 2, leaf 3, leaf 4]
tree2 = inner 1 [leaf 2, leaf 3, leaf 4, empty]
tree1 == tree2
unfoldTree : (seed -> (label, List seed)) -> seed -> Tree label

Construct a new tree with unfoldTree next seed, top to bottom. next will be called repeatedly with seeds, from which it should construct a label for the current tree node but also a list of seeds from which to unfold child nodes. This sort of works top to bottom compared to creating a tree bottom up by using the other primitives.

tree1 = inner 1 [leaf 2, leaf 3, leaf 4]
next seed = (seed, if seed == 1 then [2, 3, 4] else [])
tree2 = unfoldTree next 1
tree1 == tree2
unfoldForest : (seed -> (label, List seed)) -> List seed -> Forest label

Construct a new forest with unfoldForest next seeds by unfoldTree next seed for each seed in seeds. A simple specification would be

unfoldForest next seeds = List.map (unfoldTree next) seeds

Query

isEmpty : Tree label -> Bool

isEmpty tree returns true if and only if tree is empty.

isEmpty empty == True
isEmpty (leaf 42) == False
root : Tree label -> Maybe (label, Forest label)

root tree returns Nothing if tree is empty, otherwise it returns Just (label, childForest) of the root node.

tree = inner 1 [leaf 2, leaf 3, leaf 4]
root tree == Just (1, [leaf 2, leaf 3, leaf 4])
root empty == Nothing
size : Tree label -> Int

The size of the tree, e.g. the number of nodes.

tree = inner 0 [inner 1 [leaf 2, leaf 3], inner 4 [leaf 5, leaf 6]]
size tree == 7
height : Tree label -> Int

Computes the height of the tree in O(n) time.

tree = inner 0 [inner 1 [leaf 2, leaf 3], inner 4 [leaf 5, leaf 6]]
height tree == 3

Traversal

It is instructory to read the article on tree traversals on Wikipedia first if you are not familiar with the concept.

levelOrder : (label -> Forest label -> acc -> acc) -> acc -> Tree label -> acc

levelOrder visit acc tree is a breadth-first fold over tree, visiting each node and accumulating results with visit. Nodes are visited in level-order, e.g. for a tree like

tree = inner 0 [inner 1 [leaf 2, leaf 3], inner 4 [leaf 5, leaf 6]]

nodes would be visited in order [0, 1, 4, 2, 3, 5, 6]. This is in fact the list produced by levelOrderList, but through levelOrder you also get access to the children of the current node via the second parameter of visit.

levelOrderList : Tree label -> List label

See the documentation on levelOrder. levelOrderList tree produces a list of the nodes of the tree visited in level-order, e.g. breadth-first. So:

tree = inner 0 [inner 1 [leaf 2, leaf 3], inner 4 [leaf 5, leaf 6]]
levelOrderList tree == [0, 1, 4, 2, 3, 5, 6]

If you also need information on child trees instead of just the node labels, use levelOrder.

preOrder : (label -> Forest label -> acc -> acc) -> acc -> Tree label -> acc

preOrder visit acc tree is a (depth-first) pre-order traversal (fold) over tree where visit is called with the label and the child sub-forest of the current node in addition to a supplied accumulator value.

Post-order traversals work top-down: When visit is called for some node, acc already contains the value of all ancestral nodes. See preOrderList for an example on the order in which nodes are visited.

preOrderList : Tree label -> List label

See preOrder for an explanation of how post-order traversals work. Here is an example on visit order:

tree = inner 0 [inner 1 [leaf 2, leaf 3], inner 4 [leaf 5, leaf 6]]
preOrderList tree == [0, 1, 2, 3, 4, 5, 6]

If you also need information on child trees instead of just the node labels, use preOrder.

postOrder : (label -> Forest label -> acc -> acc) -> acc -> Tree label -> acc

postOrder visit acc tree is a (depth-first) post-order traversal (fold) over tree where visit is called with the label and the child sub-forest of the current node in addition to a supplied accumulator value.

When visit is called for some node, acc already contains the value of all sub-trees, so post-order traversal is a kind of bottom-up traversal, where all children are visited prior to their parent. See postOrderList for an example on the order in which nodes are visited.

postOrderList : Tree label -> List label

See postOrder for an explanation of how post-order traversals work. Here is an example on visit order:

tree = inner 0 [inner 1 [leaf 2, leaf 3], inner 4 [leaf 5, leaf 6]]
postOrderList tree == [2, 3, 1, 5, 6, 4, 0]

If you also need information on child trees instead of just the node labels, use postOrder.

module Graph.Tree exposing
  ( Tree, Forest
  -- BUILDING
  , empty, leaf, inner, unfoldTree, unfoldForest
  -- QUERY
  , isEmpty, root, size, height
  -- TRAVERSAL
  , levelOrder, levelOrderList
  , preOrder, preOrderList
  , postOrder, postOrderList
  )


{-| This module provides a simple tree data type of arbitrary arity (a rose tree).
There are primitives for building and traversing such a tree.

# Data
@docs Tree, Forest

# Building
@docs empty, leaf, inner, unfoldTree, unfoldForest

# Query
@docs isEmpty, root, size, height

# Traversal

It is instructory to read the article on [tree traversals on Wikipedia](https://en.wikipedia.org/wiki/Tree_traversal) first if you are not familiar with the concept.

@docs levelOrder, levelOrderList, preOrder, preOrderList, postOrder, postOrderList

-}


import Queue exposing (Queue)


{-| Data type representing an n-ary tree with node labels of type `a`
Building such a tree is done with the `empty`, `leaf` and `inner` smart
constructors. An example for a tree with three leafs and a root node:

    tree = inner 1 [leaf 2, leaf 3, leaf 4]
-}
type Tree label =
  MkTree Int (Maybe (label, List (Tree label)))


{-| This is just an alias for a list of trees, called a forest in the
literature.
-}
type alias Forest label =
  List (Tree label)


{- BUILDING -}


{-| Construct an empty tree with no nodes. -}
empty : Tree label
empty =
  MkTree 0 Nothing


{-| Construct a tree with a single node from a value for the node's label.

    tree : Tree Int
    tree = leaf 42
 -}
leaf : label -> Tree label
leaf val =
  inner val []


{-| Construct a new tree by `inner label children`, combining a number of
subtrees `children` with a `label` for the new inner node which will be
the root of the tree. Empty subtrees are filtered out. An example:

    tree1 = inner 1 [leaf 2, leaf 3, leaf 4]
    tree2 = inner 1 [leaf 2, leaf 3, leaf 4, empty]
    tree1 == tree2
-}
inner : label -> List (Tree label) -> Tree label
inner label children =
  let
    children' =
      List.filter (not << isEmpty) children

    size' =
      List.foldl (size >> (+)) 1 children'
  in
    MkTree size' (Just (label, children'))


{-| Construct a new tree with `unfoldTree next seed`, top to bottom. `next` will be
called repeatedly with seeds, from which it should construct a label for
the current tree node but also a list of seeds from which to unfold
child nodes. This sort of works top to bottom compared to creating a
tree bottom up by using the other primitives.

    tree1 = inner 1 [leaf 2, leaf 3, leaf 4]
    next seed = (seed, if seed == 1 then [2, 3, 4] else [])
    tree2 = unfoldTree next 1
    tree1 == tree2
-}
unfoldTree : (seed -> (label, List seed)) -> seed -> Tree label
unfoldTree next seed =
  let
    (label, seeds) = next seed
  in
    inner label (List.map (unfoldTree next) seeds)


{-| Construct a new forest with `unfoldForest next seeds` by `unfoldTree next seed`
for each `seed` in `seeds`. A simple specification would be

    unfoldForest next seeds = List.map (unfoldTree next) seeds
-}
unfoldForest : (seed -> (label, List seed)) -> List seed -> Forest label
unfoldForest next seeds =
  List.map (unfoldTree next) seeds


{- QUERY -}


{-| `isEmpty tree` returns true if and only if `tree` is `empty`.

    isEmpty empty == True
    isEmpty (leaf 42) == False
-}
isEmpty : Tree label -> Bool
isEmpty tree =
  tree == empty

{-| `root tree` returns `Nothing` if `tree` is `empty`, otherwise
it returns `Just (label, childForest)` of the root node.

    tree = inner 1 [leaf 2, leaf 3, leaf 4]
    root tree == Just (1, [leaf 2, leaf 3, leaf 4])
    root empty == Nothing
-}
root : Tree label -> Maybe (label, Forest label)
root tree =
  case tree of
    MkTree _ maybe -> maybe


{-| The size of the tree, e.g. the number of nodes.

    tree = inner 0 [inner 1 [leaf 2, leaf 3], inner 4 [leaf 5, leaf 6]]
    size tree == 7
-}
size : Tree label -> Int
size tree =
  case tree of
    MkTree n _ -> n


{-| Computes the height of the tree in O(n) time.

    tree = inner 0 [inner 1 [leaf 2, leaf 3], inner 4 [leaf 5, leaf 6]]
    height tree == 3
-}
height : Tree label -> Int
height tree =
  let
    go h t =
      case root t of
        Just (_, children) ->
          children
            |> List.foldl (go (h + 1) >> max) (h + 1)
        Nothing ->
          h
  in
    go 0 tree


{- TRAVERSAL -}


-- This is private. No type annotation for this, traversal is quite daunting.
listForTraversal traversal tree =
  -- we will compute a DList that we then can turn into a List.
  let
    f label children rest =
        (::) label >> rest
    acc = identity
  -- the call to postOrder returns a DList ([a] -> [a]), so [] turns it into a list
  in
    traversal f acc tree []


-- This is also not exported.
pushMany : List a -> Queue a -> Queue a
pushMany vals queue =
  List.foldl Queue.push queue vals


{-| `levelOrder visit acc tree` is a breadth-first fold over `tree`,
visiting each node and accumulating results with `visit`. Nodes are visited
in level-order, e.g. for a tree like

    tree = inner 0 [inner 1 [leaf 2, leaf 3], inner 4 [leaf 5, leaf 6]]

nodes would be visited in order `[0, 1, 4, 2, 3, 5, 6]`. This is in fact the
list produced by `levelOrderList`, but through `levelOrder` you also get access
to the children of the current node via the second parameter of visit.
-}
levelOrder : (label -> Forest label -> acc -> acc) -> acc -> Tree label -> acc
levelOrder visit acc tree =
  let
    go acc toVisit =
      case Queue.pop toVisit of
        Nothing -> acc
        Just (tree', toVisit') ->
          case root tree' of
            Nothing -> go acc toVisit'
            Just (label, children) ->
              go (visit label children acc) (pushMany children toVisit')
  in
    go acc (Queue.empty |> Queue.push tree)


{-| See the documentation on `levelOrder`. `levelOrderList tree` produces
a list of the nodes of the tree visited in level-order, e.g. breadth-first.
So:

    tree = inner 0 [inner 1 [leaf 2, leaf 3], inner 4 [leaf 5, leaf 6]]
    levelOrderList tree == [0, 1, 4, 2, 3, 5, 6]

If you also need information on child trees instead of just the node labels,
use `levelOrder`.
-}
levelOrderList : Tree label -> List label
levelOrderList =
  listForTraversal levelOrder


{-| `postOrder visit acc tree` is a (depth-first) post-order traversal (fold)
over `tree` where `visit` is called with the label and the child sub-forest of
the current node in addition to a supplied accumulator value.

When `visit` is called for some node, `acc` already contains the value of all
sub-trees, so post-order traversal is a kind of bottom-up traversal, where
all children are visited prior to their parent.
See `postOrderList` for an example on the order in which nodes are visited.
-}
postOrder : (label -> Forest label -> acc -> acc) -> acc -> Tree label -> acc
postOrder visit acc tree =
  let
    folder = flip (postOrder visit)
  in
    case root tree of
      Nothing -> acc
      Just (label, children) ->
        visit label children (List.foldl folder acc children)


{-| See `postOrder` for an explanation of how post-order traversals work.
Here is an example on visit order:

    tree = inner 0 [inner 1 [leaf 2, leaf 3], inner 4 [leaf 5, leaf 6]]
    postOrderList tree == [2, 3, 1, 5, 6, 4, 0]

If you also need information on child trees instead of just the node labels,
use `postOrder`.
-}
postOrderList : Tree label -> List label
postOrderList =
  listForTraversal postOrder


{-| `preOrder visit acc tree` is a (depth-first) pre-order traversal (fold)
over `tree` where `visit` is called with the label and the child sub-forest of
the current node in addition to a supplied accumulator value.

Post-order traversals work top-down: When `visit` is called for some node,
`acc` already contains the value of all ancestral nodes.
See `preOrderList` for an example on the order in which nodes are visited.
-}
preOrder : (label -> Forest label -> acc -> acc) -> acc -> Tree label -> acc
preOrder visit acc tree =
  let
    folder = flip (preOrder visit)
  in
    case root tree of
      Nothing -> acc
      Just (label, children) ->
        List.foldl folder (visit label children acc) children


{-| See `preOrder` for an explanation of how post-order traversals work.
Here is an example on visit order:

    tree = inner 0 [inner 1 [leaf 2, leaf 3], inner 4 [leaf 5, leaf 6]]
    preOrderList tree == [0, 1, 2, 3, 4, 5, 6]

If you also need information on child trees instead of just the node labels,
use `preOrder`.
-}
preOrderList : Tree label -> List label
preOrderList =
  listForTraversal preOrder