PackagesReroutesAboutlamdera.com

allo-media/canopy/1.0.0

READMEAboutVersionsSourceModules

Canopy

A generic Rose Tree.

Note: This library is designed to work with unique values attached to tree nodes. This is usually achievable using records having a unique id, though unicity checks should be performed by consumers of this library.

type Node a
= Node a (List (Node a))

A Rose Tree. Each node contains a value and children, which are themselves Nodes:

myTree : Tree Int
myTree =
    Node 1
        [ Node 2
            [ Node 3 []
            , Node 4 []
            ]
        , Node 5 []
        ]

Building a tree

node : a -> List (Node a) -> Node a

Create a Node. Basically just an alias for the Node constructor.

leaf : a -> Node a

Create a node having no children (singleton).

leaf "foo"
--> Node "foo" []
append : a -> a -> Node a -> Node a

Append a new value to a Node identified by its value in a Tree.

node "foo" [ leaf "bar"]
    |> append "foo" "baz"
--> node "foo" [ leaf "bar", leaf "baz" ]
prepend : a -> a -> Node a -> Node a

Prepend a new value to a Node identified by its value in a Tree.

node "foo" [ leaf "bar"]
    |> prepend "foo" "baz"
--> node "foo" [ leaf "baz", leaf "bar" ]
remove : a -> Node a -> Node a

Deletes all occurrences of a value from a tree.

node "root" [ node "foo" [ leaf "bar" ] ]
    |> remove "bar"
--> node "root" [ leaf "foo" ]

Noop when the value doesn't exist in the tree:

node "root" [ leaf "foo" ]
    |> remove "non-existent"
--> node "root" [ leaf "foo" ]

Or when attempting to delete the tree itself:

leaf "root"
    |> remove "root"
--> leaf "root"
seed : (a -> List a) -> a -> Node a

Seed a tree.

seed (\x -> List.range 1 (x - 1)) 4
--> node 4
-->   [ leaf 1
-->   , node 2 [ leaf 1 ]
-->   , node 3
-->       [ leaf 1
-->       , node 2 [ leaf 1 ]
-->       ]
-->   ]

Querying a tree

value : Node a -> a

Extract the value of a Node.

leaf 2 |> value
--> 2
values : Node a -> List a

List all the values in a tree.

node 1 [ node 2 [ leaf 3 ] ]
    |> values
--> [ 1, 2, 3 ]
children : Node a -> List (Node a)

Extracts the children of a Node.

node "foo" [ leaf "bar" ]
    |> children
--> [ leaf "bar" ]
length : Node a -> Int

Count nodes in a tree.

node 1 [node 2 [ node 3 [ leaf 4 ] ] ]
|> length
--> 4
get : a -> Node a -> Maybe (Node a)

Get a Node holding a value from a tree, picking the first node found starting from the left.

node "root" [ leaf "bar" ]
    |> get "bar"
--> Just (leaf "bar")
getAll : a -> Node a -> List (Node a)

Get all nodes containing the provided value.

node 1 [ leaf 1 ]
    |> getAll 1
--> [ node 1 [ leaf 1 ], leaf 1 ]
leaves : Node a -> List a

Retrieve all leaves (singletons) from a tree.

node "root"
    [ leaf "a leaf"
    , node "branch"
        [ leaf "another leaf" ]
    ]
    |> leaves
--> [ "a leaf", "another leaf" ]
level : Int -> Node a -> List (Node a)

Retrieve all nodes at a given level in the tree.

node "root"
    [ node "1" [ node "1.1" [ leaf "1.1.1" ] ]
    , node "2" [ node "2.1" [ leaf "2.1.1" ] ]
    ]
    |> level 3
--> [ leaf "1.1.1"
--> , leaf "2.1.1"
--> ]


node "root"
    [ node "1" [ node "1.1" [ leaf "1.1.1" ] ]
    , node "2" [ node "2.1" [ leaf "2.1.1" ] ]
    ]
    |> level 2
--> [ node "1.1" [ leaf "1.1.1" ]
--> , node "2.1" [ leaf "2.1.1" ]
--> ]
maximum : Node comparable -> comparable

Compute the maximum value appearing in a tree.

node 1 [ leaf 100, node 2 [ leaf 3 ] ]
    |> maximum
--> 100
minimum : Node comparable -> comparable

Compute the minimum value appearing in a tree.

node 100 [ leaf 99, node 1 [ leaf 98 ] ]
    |> minimum
--> 1
parent : a -> Node a -> Maybe (Node a)

Retrieve the parent of a given node in a Tree, identified by its value.

node "root" [ node "foo" [ leaf "bar" ] ]
    |> parent "bar"
--> Just (node "foo" [ leaf "bar" ])
path : a -> Node a -> List (Node a)

Compute the path to a the first node holding the target value, from the root.

node "root"
    [ leaf "qux"
    , node "foo"
        [ node "bar"
            [ leaf "baz" ]
        ]
    ]
    |> path "baz"
    |> List.map value
--> [ "root", "foo", "bar", "baz" ]
seek : (a -> Bool) -> Node a -> List (Node a)

Retrieve all values from nodes containing those satisfying a provided condition.

node 1 [ node 2 [ leaf 3, leaf 4, leaf 5 ] ]
    |> seek (\x -> x > 3)
--> [ leaf 4, leaf 5 ]
siblings : a -> Node a -> List (Node a)

Retrieve siblings of a node identified by its value in a Tree.

node "foo" [ leaf "a", node "b" [ leaf "x" ], leaf "c" ]
    |> siblings "c"
--> [ leaf "a", node "b" [ leaf "x" ] ]

Checking a tree

all : (a -> Bool) -> Node a -> Bool

Check that all values satisfy a test in a tree.

node 1 [ leaf 2 ]
    |> all (\x -> x > 0)
--> True


node 1 [leaf -2]
    |> all (\x -> x > 0)
--> False
any : (a -> Bool) -> Node a -> Bool

Check that any value satisfy a test in a tree.

node 1 [ leaf -2 ]
    |> any (\x -> x > 0)
--> True


node -1 [ leaf -2 ]
    |> any (\x -> x > 0)
--> False
member : a -> Node a -> Bool

Check if a tree contains a value.

node "foo" [ node "bar" [ leaf "baz" ] ]
    |> member "baz"
--> True


leaf "no"
    |> member "yes"
--> False

Manipulating a tree

Single-level operations

mapChildren : (Node a -> Node a) -> Node a -> Node a

Map a Node's children.

node "root" [ leaf "foo", leaf "bar" ]
    |> mapChildren (map String.toUpper)
--> node "root" [ leaf "FOO", leaf "BAR" ]
replaceChildren : List (Node a) -> Node a -> Node a

Replace the children of a Node.

replaceValue : a -> Node a -> Node a

Replace the value of a Node.

updateValue : (a -> a) -> Node a -> Node a

Update a Node value using an update function. This is especially useful for updating record properties.

leaf { name = "root" }
    |> updateValue (\r -> { r | name = r.name ++ "!"})
--> leaf { name = "root!" }

Deep operations

mapChildrenAt : a -> (Node a -> Node a) -> Node a -> Node a

Map a targetted Node's children in a tree.

node 1 [ node 2 [ leaf 3, leaf 4 ] ]
    |> mapChildrenAt 2 (updateValue ((*) 2))
--> node 1 [ node 2 [ leaf 6, leaf 8 ] ]
replaceAt : a -> Node a -> Node a -> Node a

Replace all Nodes holding a given value with a new Node in a Tree.

node "root" [ node "foo" [ leaf "bar" ] ]
    |> replaceAt "foo" (leaf "bar")
--> node "root" [ leaf "bar" ]


node "root" [ leaf "foo", leaf "foo" ]
    |> replaceAt "foo" (leaf "bar")
--> node "root" [ leaf "bar", leaf "bar" ]
replaceChildrenAt : a -> List (Node a) -> Node a -> Node a

Replace a targetted Node's children in a tree.

node 1 [ node 2 [ leaf 3, leaf 4 ] ]
    |> replaceChildrenAt 2 [ leaf 5 ]
--> node 1 [ node 2 [ leaf 5 ] ]
replaceValueAt : a -> a -> Node a -> Node a

Replace a targetted Node value with another one in a Tree.

node "root" [ node "foo" [ leaf "bar" ] ]
    |> replaceValueAt "foo" "baz"
--> node "root" [ node "baz" [ leaf "bar" ] ]


node "root" [ leaf "foo", leaf "foo" ]
    |> replaceValueAt "foo" "bar"
--> node "root" [ leaf "bar", leaf "bar" ]
updateAt : a -> (Node a -> Node a) -> Node a -> Node a

Update a targetted Node in a tree, using an update function.

node 1 [ node 2 [ leaf 3 ] ]
    |> updateAt 3 (always (leaf 42))
--> node 1 [ node 2 [ leaf 42 ] ]
updateValueAt : a -> (a -> a) -> Node a -> Node a

Update a targetted Node value in a tree, using an update function.

node 1 [ node 2 [ leaf 3 ] ]
    |> updateValueAt 3 ((*) 2)
--> node 1 [ node 2 [ leaf 6 ] ]

Common operations

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

Filter a Tree strictly, removing all nodes failing the provided value test, including root, hence the resulting Maybe.

node 0 [ leaf 1 ]
    |> filter (\x -> x > 0)
--> Nothing


node 2 [ leaf 3, leaf 4 ]
    |> filter (\x -> modBy 2 x == 0)
--> Just (node 2 [ leaf 4 ])
flatMap : (Node a -> b) -> Node a -> List b

Map each node using a mapping function then flatten the result into a new list.

node "foo" [ node "bar" [ leaf "baz" ] ]
    |> flatMap (value >> String.toUpper)
--> [ "FOO", "BAR", "BAZ" ]
flatten : Node a -> List (Node a)

Flatten a Tree, from top to bottom and leftmost nodes to rightmost ones.

node "root" [ node "foo" [ leaf "bar", leaf "baz" ] ]
    |> flatten
--> [ node "root" [ node "foo" [ leaf "bar", leaf "baz" ] ]
--> , node "foo" [ leaf "bar", leaf "baz" ]
--> , leaf "bar"
--> , leaf "baz"
--> ]
foldl : (a -> b -> b) -> b -> Node a -> b

Reduce all tree values from top to bottom, left to right.

node 1 [ node 2 [ leaf 3 ] ]
    |> foldl (+) 0
--> 6


node "a"
    [ node "b" [ leaf "c" ]
    , node "d" [ node "e" [ leaf "f" ] ]
    , leaf "g"
    ]
    |> foldl (\value acc -> acc ++ value) ""
--> "abcdefg"
foldr : (a -> b -> b) -> b -> Node a -> b

Reduce all tree values from top to bottom, right to left.

node "a"
    [ node "b" [ leaf "c" ]
    , node "d" [ node "e" [ leaf "f" ] ]
    , leaf "g"
    ]
    |> foldr (\value acc -> acc ++ value) ""
--> "gfedcba"
map : (a -> b) -> Node a -> Node b

Map all Node values in a Tree.

node "root" [ leaf "foo", node "bar" [ leaf "baz" ] ]
    |> map String.toUpper
--> node "ROOT" [ leaf "FOO", node "BAR" [ leaf "BAZ" ] ]
refine : (a -> Bool) -> Node a -> Node a

Filter a Tree, keeping only nodes which attached leaves satisfy the provided test and preserving their ancestors, up to the tree root, which is always kept.

node 2
    [ node 4
        [ leaf 6
        , leaf 7
        , node 8
            [ leaf 10
            , leaf 11
            , leaf 12
            , leaf 13
            ]
        ]
    ]
    |> refine (\x -> modBy 2 x == 0)
--> node 2
-->    [ node 4
-->        [ leaf 6
-->        , node 8
-->            [ leaf 10
-->            , leaf 12
-->            ]
-->        ]
-->    ]
sortBy : (a -> comparable) -> Node a -> Node a

Recursively sort node children from a tree using a sorter.

node 0 [ leaf 3, leaf 1, leaf 2 ]
    |> sortBy identity
--> node 0 [ leaf 1, leaf 2, leaf 3 ]
sortWith : (a -> a -> Order) -> Node a -> Node a

Recursively sort node children from a tree using a comparator.

node 0 [ leaf 3, leaf 1, leaf 2 ]
    |> sortWith (\a b -> if a == b then EQ else if a < b then GT else LT)
--> node 0 [ leaf 3, leaf 2, leaf 1 ]
tuple : Node a -> Node a -> ( a, Maybe a )

Turn a Node into a tuple containing the value and the parent value, if any.

Importing and exporting

fromList : List ( a, Maybe a ) -> Maybe (Node a)

Build a tree from a list of hierarchy descriptors, which are tuples of value and parent value, starting with the root.

[ ( "root", Nothing )
, ( "foo", Just "root" )
, ( "bar", Just "foo" )
]
    |> fromList
--> Just (node "root" [ node "foo" [ leaf "bar" ] ])
toList : Node a -> List ( a, Maybe a )

Turn a tree of node into a list of tuples.

node "root" [ node "foo" [ leaf "bar" ], leaf "baz" ]
    |> toList
--> [ ( "root", Nothing )
--> , ( "foo", Just "root")
--> , ( "bar", Just "foo")
--> , ( "baz", Just "root")
--> ]
decode : Decoder a -> Decoder (Node a)

A JSON Node decoder. You must specify a decoder for values.

import Json.Decode as Decode


json : String
json = "{\"value\":\"foo\",\"children\":[{\"value\":\"bar\",\"children\":[]}]}"


Decode.decodeString (decode Decode.string) json
--> Ok (node "foo" [ leaf "bar" ])
encode : (a -> Value) -> Node a -> Value

Encode a Node to JSON. You must provide an encoder for values.

import Json.Encode as Encode


node "foo" [ leaf "bar" ]
    |> encode Encode.string
    |> Encode.encode 0
--> "{\"value\":\"foo\",\"children\":[{\"value\":\"bar\",\"children\":[]}]}"

Modules

About this package serverReroutesreroutes.json
Pages and docs rendering from package.elm-lang.org, © 2012-2020 Evan Czaplicki. © 2026 Lamdera