实现带有前缀树的基本搜索引擎

Question

问题是在不使用任何存储和迭代方法的情况下在函数语言中实现前缀树(Trie).

我正在努力解决这个问题.我该如何处理这个问题？你能给我一个精确的算法或链接,它显示已经用任何功能语言实现了一个吗？

我为什么要这样做=>创建一个具有的功能的简单搜索引擎

• 在树上添加单词
• 在树中搜索一个单词
• 删除树中的单词

为什么我要使用函数式语言=>我想进一步提高我的解决问题的能力.

注意:由于这是我的爱好项目,我将首先实现基本功能.

编辑:

i.)我的意思是"不使用存储"=>我不想使用变量存储(ex int a),引用变量,数组.我想通过递归计算结果然后将结果显示到屏幕.

ii.)我已经写了一些内容,但后来我已经删除了,因为我写的内容让我很生气.很抱歉没有表现出我的努力.

Answer 1

看看 haskell 的Data.IntMap. 它是Patricia trie的纯函数实现 ，并且它的源代码非常可读。
bytestring-trie包扩展了这种方法ByteStrings

随附的论文《快速可合并整数映射》也具有可读性和通透性。它逐步描述了实现：从二进制尝试到大端帕特里夏树。
以下是论文的一些摘录。

最简单的是，二叉树是一个完整的二叉树，其深度等于键中的位数，其中每个叶子要么为空，表示相应的键未绑定，要么为满，在这种情况下，它包含要处理的数据。绑定了对应的key。这种类型的 trie 可能在标准 ML 中表示为

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

要在二进制 trie 中查找值，我们只需读取键的位，按照指示向左或向右，直到到达叶子。

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)