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

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 даже после первого издания книги Стила конструкции, и LISP долгое время занимался setq.

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

Я думаю, что вышеупомянутое - что-то вроде того, что вы имеете в виду.

Answer 2

Полагаю, вам нужно что-то вроде дерева со списком детей, как описано здесь .