trie_again - v1.1.2

trie

Types

Trie

</>

A Trie(k, v) is a data structure that allows to store values of type v indexed by lists of values of type k.

pub opaque type Trie(k, v)

Functions

delete

</> 
pub fn delete(
  from trie: Trie(a, b),
  at path: List(a),
) -> Trie(a, b)

Deletes from a trie the value associated with a given path.

Examples

> [#([1, 2], "a"), #([1], "b")]
> |> from_list
> |> delete(at: [1, 2])
> |> to_list
[#([1], "b")]

> new()
> |> delete(at: [1, 2])
> |> to_list
[]

fold

</> 
pub fn fold(
  over trie: Trie(a, b),
  from initial: c,
  with fun: fn(c, List(a), b) -> c,
) -> c

Combines all the trie’s values into a single one by calling a given function on each one.

The function takes as input the accumulator, the path of a value and the corresponding value.

Examples

> [#([1, 2], 10), #([1], 1)]
> |> from_list
> |> fold(from: 0, with: fn(sum, _, value) { sum + value })
11

from_list

</> 
pub fn from_list(list: List(#(List(a), b))) -> Trie(a, b)

Creates a new trie from a list of path-value pairs.

Examples

> [#([1, 2], "a"), #([1], "b")]
> |> from_list
> |> to_list
[#([1, 2], "a"), #([1], "b")]

get

</> 
pub fn get(from: Trie(a, b), at path: List(a)) -> Result(b, Nil)

Fetches a value from a trie for a given path. If a value is present at the given path it returns it wrapped in an Ok, otherwise it returns Error(Nil).

Examples

> new()
> |> get(at: [1, 2])
Result(Nil)

> singleton([1, 2], "a")
> |> get(at: [1, 2])
Ok("a")

has_path

</> 
pub fn has_path(trie: Trie(a, b), path: List(a)) -> Bool

Determines wether a trie contains a value associated with the given path.

Examples

> singleton([1, 2], "a")
> |> has_path([1, 2])
True

> singleton([1, 2], "a")
> |> has_path([1])
False

insert

</> 
pub fn insert(
  into trie: Trie(a, b),
  at path: List(a),
  value value: b,
) -> Trie(a, b)

Inserts a value in a trie at a given path. If there already is a value at the given path it is replaced by the new one.

Examples

> new()
> |> insert(at: [1, 2], value: "a")
> |> insert(at: [1], value: "b")
> |> to_list
[#([1, 2], "a"), #([1], "b")]

> new()
> |> insert(at: [1, 2], value: "a")
> |> insert(at: [1, 2], value: "b")
> |> to_list
[#([1, 2], "b")]

is_empty

</> 
pub fn is_empty(trie: Trie(a, b)) -> Bool

Determines wether or not the trie is empty.

Examples

> new()
> |> is_empty
True

> singleton([1, 2], "a")
> |> is_empty
False

map

</> 
pub fn map(
  over trie: Trie(a, b),
  with fun: fn(b) -> c,
) -> Trie(a, c)

Updates all the values in a given trie by calling a function on each value.

Examples

> [#([1, 2], "a"), #([1], "b")]
> |> from_list
> |> map(fn(s) { s <> "!" })
> |> to_list
[#([1, 2], "a!"), #([1], "b!")]

new

</> 
pub fn new() -> Trie(a, b)

Creates a new empty trie.

Examples

> new()
> |> to_list
[]

paths

</> 
pub fn paths(trie: Trie(a, b)) -> List(List(a))

Gets a list of all the valid paths in the trie. That is all the paths associated with a value.

Tries are not ordered so the paths are not returned in any specific order. Do not write code that relies on the order paths are returned by this function as it may change in later versions of the library.

Examples

> [#([1, 2], "a"), #([1], "b")]
> |> from_list
> |> paths
[[1, 2], [1]]

> new()
> |> paths
[]

singleton

</> 
pub fn singleton(path: List(a), value: b) -> Trie(a, b)

Creates a new trie with a single value associated to the given path.

Examples

> singleton([1, 2], "a")
> |> to_list
[#([1, 2], "a")]

size

</> 
pub fn size(trie: Trie(a, b)) -> Int

Gets the number of elements in the trie.

Examples

> [#([1, 2], "a"), #([1], "b")]
> |> from_list
> |> size
2

subtrie

</> 
pub fn subtrie(
  trie: Trie(a, b),
  at prefix: List(a),
) -> Result(Trie(a, b), Nil)

Gets the subtrie whose elements all share a common given prefix.

Examples

> [#([1, 2, 3], "a"), #([1, 2, 4, 5], "b"), #([3, 4], "c")]
> |> from_list
> |> subtrie(at: [1, 2])
> |> to_list
[#([1, 2, 3], "a"), #([1, 2, 4, 5], "b")]

to_list

</> 
pub fn to_list(trie: Trie(a, b)) -> List(#(List(a), b))

Turns a trie into a list of path-value pairs.

Examples

> singleton([1, 2], "a")
> |> to_list
[#([1, 2], "a")]

> new()
> |> to_list
[]

update

</> 
pub fn update(
  trie: Trie(a, b),
  at path: List(a),
  with fun: fn(Option(b)) -> Option(b),
) -> Trie(a, b)

Updates the value associated with a path applying it the given function. If there is no value associated with the given path the function is passed None.

If the function returns None any value associated with the path is deleted from the trie. If the function returns Some(value) then the new value is associated to the given path.

Examples

> singleton([1, 2], "a")
> |> update(at: [1, 2], with: fn(n) { n |> option.map(fn(_) { "b" }) })
> |> to_list
[#([1, 2], "b")]

> singleton([1, 2], "a")
> |> update(at: [1, 2], with: fn(_) { None })
> |> to_list
[]

> singleton([1, 2], "a")
> |> update(at: [1], with: fn(_) { Some("b") })
> |> to_list
[#([1, 2], "a"), #([1], "b")]

values

</> 
pub fn values(trie: Trie(a, b)) -> List(b)

Gets a list of all the values in a given trie.

Tries are not ordered so the values are not returned in any specific order. Do not write code that relies on the order values are returned by this function as it may change in later versions of the library.

Examples

> [#([1, 2], "a"), #([1], "b")]
> |> from_list
> |> values
["a", "b"]

> new()
> |> values
[]
✨ Search Document