▼Functional Data Structures in Typed Racket
On this page:
Trie
tries
trie
insert
bind
lookup
7.7
  top  ← prev  up  next → 

8 Tries

 (require pfds/trie) package: pfds

A Trie (also known as a Digital Search Tree) is a data structure which takes advantage of the structure of aggregate types to achieve good running times for its operations. Our implementation provides Tries in which the keys are lists of the element type; this is sufficient for representing many aggregate data structures. In our implementation, each trie is a multiway tree with each node of the multiway tree carrying data of base element type. Tries provide lookup and insert operations with better asymptotic running times than hash tables. This data structure is very useful when used for an aggregate type like strings.

syntax

(Trie K V)

A trie with keys of type K and values of type V.

procedure

(tries values keys) → (Trie K V)

  values : (Listof V)
  keys : (Listof (Listof K))
Function tries creates a trie with each value assigned to the list in keys at the corresponding location.

Example:
> (tries (list 1 2 3 4 5)
         (map string->list (list "abc" "xyz" "abcfg" "abxyz" "xyz12")))

- : (Trie Char Positive-Byte)

#<Trie>

In the above example, "abc" will have the value 1, "xyz" will get 2 and so on.

procedure

(trie keys) → (Trie K Integer)

  keys : (Listof (Listof K))
Function trie creates a trie by assigning a integer value to each list in keys.

Example:
> (trie (map string->list (list "abc" "xyz" "abcfg" "abxyz" "xyz12")))

- : (Trie Char Integer)

#<Trie>

In the above example, "abc" will have the value 1, "xyz" will get 2 and so on.

procedure

(insert values keys trie) → (Trie K V)

  values : (Listof V)
  keys : (Listof (Listof K))
  trie : (Trie K V)
Inserts multiple keys into the trie.

Example:
> (insert (list 4 5)
          (map string->list (list "abcfg" "abxyz"))
          (tries (list 1 2)
                 (map string->list (list "abc" "xyz"))))

- : (Trie Char Positive-Byte)

#<Trie>

In the above example, "abcfg" will have the value 4, "abxyz" will get 5

procedure

(bind key value trie) → (Trie K V)

  key : (Listof K)
  value : V
  trie : (Trie K V)
Inserts a key into the trie.

Example:
> (bind (string->list "abcfg") 3
        (tries (list 1 2)
               (map string->list (list "abc" "xyz"))))

- : (Trie Char Positive-Byte)

#<Trie>

procedure

(lookup key trie) → V

  key : (Listof K)
  trie : (Trie K V)
Looks for the given key. If found, the value corresponding to the key is returned. Else throws an error.

Examples:
> (lookup (string->list "abcde")
          (tries (list 1 2 3 4)
                 (map string->list (list "123" "abc" "xyz" "abcde"))))

- : Integer [more precisely: Positive-Byte]

4

> (lookup (string->list "abc")
          (tries (list 1 2 3 4)
                 (map string->list (list "123" "abc" "xyz" "abcde"))))

- : Integer [more precisely: Positive-Byte]

2

> (lookup (string->list "abcd")
          (tries (list 1 2 3 4)
                 (map string->list (list "123" "abc" "xyz" "abcde"))))

lookup: given key not found in the trie

  top  ← prev  up  next →