0

我对 OCaml 非常陌生，并且很难实现一系列功能来构建 T9 预测文本程序。例如，如果我的词是“Dog” - 作为整数列表将是 [3;6;4]。我已经有一个模式匹配函数来将单词与 int 列表相关联。我正在使用数据类型 trie 将数字映射到可能的单词结果：

type ('a, 'b) trie = Node of 'b list * ('a * ('a, 'b) trie) list

边缘用 'a 类型的键标记的树和用 'b 类型的单词列表标记的节点

我需要编写一个带有参数 trie 和边缘标签的函数，该函数在边缘的末尾返回一个 trie。

val trie_of_key : (’a, ’b) trie -> ’a -> (’a, ’b) trie = <fun>

如何遍历边缘到达给定节点？函数式编程仍然让我迷惑，所以我不确定到达预期的子树所需的递归步骤。

4

1 回答 1

1

在我看来，如果您不想修改 trie，函数式编程与常规的旧命令式编程相同。在此过程中不进行任何重组的查找函数应该非常简单。也许你只是想多了这个问题？

如果没有看到您尝试过的示例，很难说更多。

更新

这是我刚刚为 B-Tree 结构编写的查找函数。与您要解决的问题有一些相似之处，所以也许它会给您一些想法。

type ('a, 'b) btree = Node of ('a * 'b) list * ('a, 'b) btree list

let rec lookup bt k =
    match bt with
    | Node ([], _) -> raise Not_found
    | Node (keyvals, subtrees) ->
        let rec look kvs sts =
            match kvs with
            | [] ->
                lookup (List.hd sts) k (* Rightmost subtree *)
            | (hdk, hdv) :: tlkv ->
                if hdk = k then hdv
                else if hdk < k then look tlkv (List.tl sts)
                else lookup (List.hd sts) k
        in  
        look keyvals subtrees

我不认为细节很重要，但如果你想仔细理解代码，它基于不变量，没有键/值对的节点是没有子树的叶节点。否则，如果节点中有 n 个键/值对，则正好有 n + 1 个子树。（这些子树可以是空的。）

于 2014-10-19T17:04:27.297 回答