Структура данных Trie в OCaml

Я пытаюсь создать trie в OCaml:

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

EDIT:: Благодаря 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

Что представляют эти числа?


trie ocaml
person Ihmahr    schedule 23.11.2012    source источник
comment
Если ответ на ваш существующий вопрос вызывает новый вопрос, задайте его в другом сообщении. Задать его в том же посте означает, что хорошие ответы станут плохими ответами. Кроме того, на ваш второстепенный вопрос может никогда не быть ответа, потому что все уже просмотрели ваш пост.   -  person Pascal Cuoq    schedule 01.01.2013

Ответы (2)


arrow_upward
6
arrow_downward

Вы не должны использовать let x = ... and y = ... in, когда y зависит от 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 ...
person Virgile    schedule 23.11.2012
comment
Спасибо! Я забыл о том, что порядок не должен иметь значения. - person Ihmahr; 23.11.2012

arrow_upward
3
arrow_downward

При использовании верхнего уровня, если вы определяете один и тот же тип дважды, ocaml увидит два типа, а не только один. Поскольку два ваших типа имеют одинаковое имя trie, они переименовываются в trie/1017 и trie/1260. Если вы перекомпилируете объявление типа, вы должны перекомпилировать все другие объявления, которые полагаются на этот тип, чтобы они использовали новый тип, а не старый.

Другое замечание: вы никогда не должны писать

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

вы должны использовать это вместо этого:

match foo with
| PATTERN ->
person Thomash    schedule 25.11.2012