时间戳

首页 > 解决方案 > 在 OCaml 中创建 char Trie

functional-programming - 在 OCaml 中创建 char Trie

问题描述

我正在尝试在 OCaml 中构建一个初始的 Trie 结构，其中边缘是字符。所以字符串“ESK”将被映射为：

[('E', [('S', [('K', [])])])]

我对此的定义是：

type trie = Trie of (char * trie) list

但是，在实现add功能时：

 let rec add_string str =
    let key = String.get str 0 in
    if String.length str = 1 then
      (key, empty_trie) :: []
    else
      (key, add_string (tail str)) :: []

因为add (tail str)编译器给了我：

Error: This expression has type (char * trie) list
       but an expression was expected of type trie

我对此有点困惑，因为我没有定义 a trieas (char * trie) list？

tail是简单的let tail str = String.slice str 1 (String.length str)并且empty_trie是let empty_trie = Trie([])

标签： functional-programmingocamlvariant

解决方案

请注意，编写函数的一种更惯用的方式是

let rec add_string str =
  let key = str.[0] in
  if String.length str = 1 then
    Trie [key, empty_trie]
  else
    Trie [key, add_string (tail str)]

然后还有两个问题add_string：首先它在每次迭代时重新分配一个新字符串。跟踪当前位置更简单、更高效：

let add_string str =
  let rec add_string_aux pos str =
    if pos = String.length str then empty_trie
    else
      let key = str.[pos] in
      Trie [key, add_string_aux (pos+1) str] in
  add_string_aux 0 str

第二个问题是该函数命名错误，因为它不会将字符串添加到现有的 trie，而是从字符串构建 trie：from_string或者of_string可能是更好的名称。

推荐阅读