Taxo (Taxo v0.2.0)

Taxo builds and queries tag hierarchies.

It ports the derive and underive functions from Clojure's hierarchy system.

Summary

Types

t()

tag()

A node in a taxonomy. A tag can be any term, because Taxo stores it as a map key.

Functions

ancestors(taxo, child)

Returns the ancestors of child in taxo.

derive(taxo, child, parent)

Adds a parent/child relationship between child and parent in taxo.

descendants(taxo, child)

Returns the descendants of child in taxo.

is_a?(taxo, child, parent)

Returns true if child and parent are equal. Returns true if child is a direct or indirect descendant of parent. Returns false otherwise.

new()

Creates a new, empty taxonomy.

parents(taxo, child)

Returns the direct parents of child in taxo.

underive(taxo, child, parent)

Removes a parent/child relationship between child and parent in taxo.

Types

t()

@type t() :: %Taxo{
  ancestors: %{required(tag()) => MapSet.t(tag())},
  descendants: %{required(tag()) => MapSet.t(tag())},
  parents: %{required(tag()) => MapSet.t(tag())}
}

tag()

@type tag() :: term()

A node in a taxonomy. A tag can be any term, because Taxo stores it as a map key.

Functions

ancestors(taxo, child)

@spec ancestors(t(), tag()) :: MapSet.t(tag())

Returns the ancestors of child in taxo.

Examples

iex> Taxo.new |> Taxo.derive(:monkey, :mammal) |> Taxo.ancestors(:monkey)
MapSet.new([:mammal])

derive(taxo, child, parent)

@spec derive(t(), tag(), tag()) :: t()

Adds a parent/child relationship between child and parent in taxo.

This updates :parents directly, then updates :ancestors and :descendants for every tag the change affects: child, parent, and all their existing relatives.

Raises Taxo.CyclicDerivationError if parent is already a descendant of child. Adding the relationship would otherwise create a cycle.

Examples

iex> Taxo.new |> Taxo.derive(:monkey, :mammal)
%Taxo{
  ancestors: %{monkey: MapSet.new([:mammal])},
  parents: %{monkey: MapSet.new([:mammal])},
  descendants: %{mammal: MapSet.new([:monkey])}
}

descendants(taxo, child)

@spec descendants(t(), tag()) :: MapSet.t(tag())

Returns the descendants of child in taxo.

Examples

iex> Taxo.new |> Taxo.derive(:monkey, :mammal) |> Taxo.descendants(:mammal)
MapSet.new([:monkey])

is_a?(taxo, child, parent)

@spec is_a?(t(), tag(), tag()) :: boolean()

Returns true if child and parent are equal. Returns true if child is a direct or indirect descendant of parent. Returns false otherwise.

Examples

iex> Taxo.new |> Taxo.is_a?(:monkey, :monkey)
true

iex> Taxo.new |> Taxo.derive(:monkey, :mammal) |> Taxo.derive(:mammal, :vertebrate) |> Taxo.is_a?(:monkey, :vertebrate)
true

iex> Taxo.new |> Taxo.derive(:monkey, :mammal) |> Taxo.derive(:mammal, :vertebrate) |> Taxo.is_a?(:vertebrate, :monkey)
false

new()

@spec new() :: t()

Creates a new, empty taxonomy.

Use derive/3 to add parent/child relationships to it.

Examples

iex> Taxo.new
%Taxo{ancestors: %{}, parents: %{}, descendants: %{}}

parents(taxo, child)

@spec parents(t(), tag()) :: MapSet.t(tag())

Returns the direct parents of child in taxo.

Examples

iex> Taxo.new |> Taxo.derive(:monkey, :mammal) |> Taxo.parents(:monkey)
MapSet.new([:mammal])

underive(taxo, child, parent)

@spec underive(t(), tag(), tag()) :: t()

Removes a parent/child relationship between child and parent in taxo.

This drops the child/parent link, then rebuilds the whole taxonomy from the pairs that remain, calling derive/3 on each pair in turn.

The rebuild cost depends on the size of the whole taxonomy, not on the size of the link removed. underive/3 is not a cheap operation on a large hierarchy.

Examples

iex> Taxo.new |> Taxo.derive(:monkey, :mammal) |> Taxo.underive(:monkey, :mammal)
%Taxo{ancestors: %{}, parents: %{}, descendants: %{}}