Как можно закодировать простой древовидный алгоритм на функциональном языке?

Question

Предположим, я хочу реализовать достаточно эффективный «алгоритм распознавания ключевых слов», который сначала получает список ключевых слов, а затем должен ответить, есть ли в списке другое заданное слово.

В императивном языке я бы хранил ключевые слова в дереве (по одному узлу на символ).Затем, получая слово для проверки, я сканировал свое дерево, чтобы проверить, является ли это слово ключевым словом.

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

Answer 1

Я думаю, вы имеете в виду количество символов на узел...что-то вроде простой схемы хеш-дерева для поиска по ключевым словам.Предположим, это или даже другой вид дерева...представьте, что вы делаете что-то вроде этого (в псевдо-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 долгое время.

Но в теории языков программирования то, что мы подразумеваем под «без гражданства», в значительной степени удовлетворяется представленной здесь идеей.

Я думаю, что вышеизложенное является чем-то вроде договоренности, которую вы имеете в виду.

Answer 2

Я думаю, вам понадобится что-то вроде дерева со списком детей, как описано. здесь.