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

Я новичок в OCaml, и мне трудно реализовать ряд функций для создания программы прогнозирования текста T9. Например, если мое слово «Собака» — список целых чисел будет [3;6;4]. У меня уже есть функция сопоставления с образцом для связывания слов со списками int. Я использую тип данных try для сопоставления чисел с возможными вариантами слов:

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

Дерево с ребрами, помеченными ключами типа 'a, и узлами, помеченными списками слов типа 'b.

Мне нужно написать функцию с параметрами trie и edge label, которая возвращает trie в конце ребра.

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

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


trie ocaml t9
person Solsma Dev    schedule 19.10.2014    source источник
comment
Возможно, было бы неплохо опубликовать часть вашего существующего кода, связанного с этим вопросом. Поможет нам в дальнейшем помочь   -  person Jackson Tale    schedule 20.10.2014

Ответы (1)


arrow_upward
1
arrow_downward

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

person Jeffrey Scofield    schedule 19.10.2014
comment
Как в этом случае будет работать императивная функция поиска? У меня есть функция let branches trie = match trie with Node (_, branches) -> branches для возврата списка ассоциаций меток ребер и функция, которая возвращает значение для данного ключа в списке ассоциаций. - person Solsma Dev; 19.10.2014
comment
Кажется, у вас есть все, что вам нужно. Возможно ли, что вы просто боретесь с рекурсией? Если это так, возможно, согрейтесь, написав более простой поиск по дереву. Затем перейдите к дереву, а затем покажите нам свой код поиска с ошибкой, если вам нужна дополнительная помощь. Я не хочу предоставлять код, потому что это похоже на школьное задание. - person Jeffrey Scofield; 19.10.2014
comment
Да, это часть гораздо большего школьного задания. Рекурсия - это то, с чем я слаб. Я начал с более простого поиска в дереве, который мы определили ранее в классе. Я сообщу, если найду решение / добьюсь прогресса. - person Solsma Dev; 19.10.2014