كيف يمكن ترميز خوارزمية شجرة بسيطة بلغة وظيفية؟

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

إذا كان هذا ما تقصده، فهذه برمجة وظيفية واضحة إلى حد ما.هل هو حقا عديم الجنسية؟هذه مسألة نقاش.قد يقول بعض الأشخاص بعض أشكال متجر البرمجة الوظيفية ما نسميه عادة "حالة" على المكدس.علاوة على ذلك ، كان لدى LISP الشائع حتى منذ الإصدار الأول من كتاب Steele Book بنيات تكرارية ، وكان Lisp قد SetQ لفترة طويلة وطويلة.

لكن في نظرية لغات البرمجة، فإن ما نعنيه بـ "عديم الجنسية" يتوافق إلى حد كبير مع الفكرة الموضحة هنا.

أعتقد أن ما ورد أعلاه يشبه الترتيب الذي تقصده.

Answer 2

أتخيل أنك تريد شيئًا مثل شجرة بها قائمة بالأطفال، كما هو موضح هنا.