Как можно закодировать простой древовидный алгоритм на функциональном языке?
-
09-06-2019 - |
Вопрос
Предположим, я хочу реализовать достаточно эффективный «алгоритм распознавания ключевых слов», который сначала получает список ключевых слов, а затем должен ответить, есть ли в списке другое заданное слово.
В императивном языке я бы хранил ключевые слова в дереве (по одному узлу на символ).Затем, получая слово для проверки, я сканировал свое дерево, чтобы проверить, является ли это слово ключевым словом.
Я хотел бы понять, как такой алгоритм будет закодирован на функциональном языке.Как получить преимущества программирования без сохранения состояния, сохраняя при этом эффективность «императивных» алгоритмов?Разве не обязательно хранить дерево где-нибудь между поисками, если вы не хотите каждый раз перестраивать его?
Решение
Я думаю, вы имеете в виду количество символов на узел...что-то вроде простой схемы хеш-дерева для поиска по ключевым словам.Предположим, это или даже другой вид дерева...представьте, что вы делаете что-то вроде этого (в псевдо-LISP):
(defun buildtree (wordlist) ...code to build tree recursively returns the tree...)
(define lookup (tree word) ...code to look up word using tree, returns t or nil...)
(defun lookupmany (tree querylist)
(if (eq querylist nil)
nil
(cons (lookup tree (car querylist)) (lookupmany tree (cdr querylist))
)
)
(defun main (wordlist querylist) ; the main entry point
(lookupmany (buildtree wordlist) querylist)
)
если вы это имеете в виду, то это довольно простое функциональное программирование.Действительно ли это лицо без гражданства?Это предмет дискуссии.Некоторые люди сказали бы, что некоторые формы функционального программирования хранят то, что мы обычно называем «состоянием» в стеке.Более того, Common Lisp даже с тех пор, как первое издание The Steele Book имело итерационные конструкции, и LISP долгое время.
Но в теории языков программирования то, что мы подразумеваем под «без гражданства», в значительной степени удовлетворяется представленной здесь идеей.
Я думаю, что вышеизложенное является чем-то вроде договоренности, которую вы имеете в виду.
Другие советы
Я думаю, вам понадобится что-то вроде дерева со списком детей, как описано. здесь.