Safe Haskell | None |
---|

This module exports main data types and functions of the adict library.

- data Trie a b = Trie {}
- type TrieD a b = Trie a (Maybe b)
- fromList :: Ord a => [([a], b)] -> TrieD a b
- implicitDAWG :: (Ord a, Ord b) => Trie a b -> Trie a b
- data DAWG a b = DAWG {}
- data Row a b = Row {}
- type DAWGD a b = DAWG a (Maybe b)
- fromTrie :: (Ord a, Ord b) => Trie a b -> DAWG a b
- fromDAWG :: Ord a => DAWG a b -> Trie a b

# Dictionary representation

The library provides two basic data structures used for dictionary
representation. The first one is a `Trie`

, which can be constructed
from a list of dictionary entries by using the `fromList`

function.

The trie can be translated into a directed acyclic word graph (`DAWG`

)
using the `fromTrie`

function (for the moment it is done in an
inefficient manner, though).

There is also a possibility of constructing an implicit DAWG, i.e. a DAWG
which is algebraically represented by a trie with sharing of common subtries,
by using the `implicitDAWG`

function (which is also inefficient right now;
in fact, the `fromTrie`

function uses this one underneath).

Finally, the DAWG can be transformed back to a trie (implicit DAWG) using
the `fromDAWG`

function.

## Trie

A trie of words with character type `a`

and entry type `b`

. It can be
thought of as a map of type `[a] -> b`

.

fromList :: Ord a => [([a], b)] -> TrieD a bSource

Construct the `Trie`

from the list of (word, value) pairs.

implicitDAWG :: (Ord a, Ord b) => Trie a b -> Trie a bSource

Elminate common subtries. The result is algebraically a trie but is represented as a DAWG in memory.

## Directed acyclic word graph

A directed acyclic word graph with character type `a`

and dictionary
entry type `b`

.

A Row represents one node of the DAWG.