4

我正在尝试在 OCaml中构建一个trie ：

type ('a, 'b) trie = Nil | Cons of 'a * 'b option * ('a, 'b) trie list;;

(* find place to insert key in a list of tries *)
let rec findInsert key x  =
    match x with
    [] -> Nil
    | x::xs -> let Cons(k, _, _) = x in 
        if key = k then x else findInsert key xs;;

(* inser pair in a trie *)
let rec insert ( key, value ) trie =
    match trie with
    Nil -> Cons(key, value, [])
    | t -> let Cons(k, v, trieList) = t and
        subTree = insert (key, value) (findInsert key trieList) and
        newSubTree = subTree::trieList in
        Cons(k, v, newSubTree);;

但这给了我以下错误：

val findInsert : 'a -> ('a, 'b) trie list -> ('a, 'b) trie = <fun>
File "trie.ml", line 15, characters 54-62:
Error: Unbound value trieList

编辑:: 多亏了 Virgile，我现在有了一个可以编译的程序：

(* insert pair in a trie *)
let rec insert ( key, value ) trie =
    match trie with
    Nil -> Cons(key, value, [])
    | t -> 
        let Cons(k, v, trieList) = t in
            let subTree = insert (key, value) (findInsert key trieList) in
            Cons(k, v, subTree::trieList);;

但是当我尝试运行它时，我得到了这个：

# let t  = Cons(3, Some 4, []);;
val t : (int, int) trie = Cons (3, Some 4, [])
# insert (4, Some 5) t;;
Error: This expression has type (int, int) trie/1017
   but an expression was expected of type (int, int) trie/1260

这些数字代表什么？

4

2 回答 2

6

您不应该使用let x = ... and y = ... inwhen ydepends on x，因为由唯一绑定的所有标识符let都应该同时定义。改为使用let x = ... in let y = ... in，以确保x在定义y. 在你的情况下，这变成：

let Cons(k, v, trieList) = t in
let subTree = insert (key, value) (findInsert key trieList) in ...
于 2012-11-23T16:38:18.837 回答
3

在使用顶层时，如果你定义了两次相同的类型，ocaml 会看到两种类型，而不仅仅是一种。由于您的两种类型具有相同的名称trie，因此它们被重命名为trie/1017和trie/1260。如果您重新编译类型声明，则必须重新编译依赖此类型的所有其他声明，以便它们使用新类型而不是旧类型。

其他备注：你不应该写

match foo with
| a -> let PATTERN = a in

你应该改用这个：

match foo with
| PATTERN ->
于 2012-11-25T21:13:43.167 回答