Поиск поддеревья по ребру в предиктивной реализации текста в OCaml - T9

Question

Я очень плохо знаком с OCaml, и мне трудно реализовать ряд функций для создания прогностической текстовой программы T9. Например, если мое слово "собака" - в качестве целочисленного списка будет [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>

Как мне пересечь ребра, чтобы добраться до данного узла? Функциональное программирование все еще дезориентирует меня, поэтому я не уверен в рекурсивных шагах, необходимых для достижения ожидаемой подпрограммы.

Answer 1

Мне кажется, что если вы не хотите изменять три, функциональное программирование такое же, как обычное старое императивное программирование. Функция поиска, которая не выполняет никакой реструктуризации, должна быть довольно простой. Может быть, вы просто продумываете проблему?

Трудно сказать больше, не видя примера того, что вы пробовали.

Обновить

Вот функция поиска, которую я только что написал для структуры 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 поддеревьев. (Эти поддеревья могут быть пустыми.)