간단한 트리 알고리즘을 함수형 언어로 어떻게 코딩할 수 있나요?

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)
)

이것이 당신이 의미하는 것이라면 이것은 상당히 간단한 함수형 프로그래밍입니다.정말 무국적인가요?그것은 논쟁의 문제입니다.어떤 사람들은 우리가 일반적으로 스택에서 "상태"라고 부르는 일부 형태의 기능 프로그래밍 저장소를 말할 것입니다.또한, Steele Book의 첫 번째 판이 반복적 인 구성을 가지고 있었으며 LISP는 오랫동안 오랫동안 SetQ를 가지고있었습니다.

그러나 프로그래밍 언어 이론에서 "상태 비저장"이 의미하는 바는 여기에 표시된 아이디어에 거의 만족됩니다.

위의 내용은 말씀하신 배열과 비슷하다고 생각합니다.

Answer 2

나는 당신이 설명된 대로 아이들의 목록이 있는 나무 같은 것을 원할 것이라고 상상합니다. 여기.