implementing a basic search engine with prefix tree

Question

The problem is the implementing a prefix tree (Trie) in functional language without using any storage and iterative method.

I am trying to solve this problem. How should I approach this problem ? Can you give me exact algorithm or link which shows already implemented one in any functional language?

Why I am trying to do => creating a simple search engine with an feature of

• adding word to tree
• searching a word in tree
• deleting a word in tree

Why I want to use functional language => I want improve my problem-solving ability a bit further.

NOTE : Since it is my hobby project, I will first implement basic features.

EDIT:

i.) What I mean about "without using storage" => I don't want use variable storage ( ex int a ), reference to a variable, array . I want calculate the result by recursively then showing result to the screen.

ii.) I have wrote some line but then I have erased because what I wrote is made me angry. Sorry for not showing my effort.

Answer 1

Take a look at haskell's Data.IntMap. It is purely functional implementation of Patricia trie and it's source is quite readable.
bytestring-trie package extends this approach to ByteStrings

There is accompanying paper Fast Mergeable Integer Maps which is also readable and through. It describes implementation step-by-step: from binary tries to big-endian patricia trees.
Here is little extract from the paper.

At its simplest, a binary trie is a complete binary tree of depth equal to the number of bits in the keys, where each leaf is either empty, indicating that the corresponding key is unbound, or full, in which case it contains the data to which the corresponding key is bound. This style of trie might be represented in Standard ML as

datatype 'a Dict =
    Empty
  | Lf of 'a
  | Br of 'a Dict * 'a Dict

To lookup a value in a binary trie, we simply read the bits of the key, going left or right as directed, until we reach a leaf.

fun lookup (k, Empty) = NONE
  | lookup (k, Lf x) = SOME x
  | lookup (k, Br (t0,t1)) =
      if even k then lookup (k div 2, t0)
                else lookup (k div 2, t1)