وظيفة الفرق القائمة العودية خطيا في LISP المشتركة

Question

كنت أعود هذه البرنامج التعليمي من أجل المتعة ، وعلق في آخر شيء يقوله ، "ممارسة: إعطاء تنفيذ عودية خطيا للاتحاد والاختلاف." (للحصول على قائمة)

الاتحاد ، لا عرق.

الفرق ، العرق.

محاولة تبدو هكذا. . .

(defun list-diff (L1 L2)
  (cond
    ((null L1) L2) 
    ((null (member (first L1) L2)) (cons (first L1) (list-diff (rest L1) L2)))
    (t (list-diff (rest L1) L2))
  )
)

الآن ، هذا يعيد جميع العناصر الموجودة في L1 غير الموجودة في L2 ، ولكنها تعيد فقط كل L2 (من الواضح). وبالمثل ، إذا قمت بتغيير L2 في السطر 3 إلى "لا شيء" ، فإنه يعيد كل L1 فقط غير في L2 ، ولكن لا شيء من L2.

لا تبدو محاولاتي في عمليات العمل متكررة ، وعندما تكون كذلك ، ينتهي بي الأمر إلى الحصول على تدفقات مكدس (مثل إذا حاولت الاتصال (List-diff L2 L1) في مكان ما).

أي من تمارينه الأخرى ، مثل القائمة-لا يتطلب سوى الركض من خلال عناصر L1. هنا ، أريد أن أضرب العناصر الحاسمة من L2 ، أو الركض (List-Diff L2 L1) ثم أؤتي النتائج من كليهما ، لكن هذا لم يعد محظوظًا خطيًا بعد الآن.

أفكار؟

(وليس الواجب المنزلي ، حقًا. اعتقدت فقط أنني أحاول أن أنظر إلى بعض Lisp من أجل المتعة.)

تحرير: وظيفة تقوم بذلك بشكل صحيح ، بناءً على الردود هي:

(defun list-diff (L1 L2)
  (cond
    ((null L1) nil)
    ((null (member (first L1) L2)) (cons (first L1) (list-diff (rest L1) L2)))
    (t (list-diff (rest L1) L2))
  )
)

Answer 1

ال حدد الاختلاف يتم تعريف العملية L1 L2 على أنها جميع العناصر e بحيث تكون E في L1 ولكن ليس في L2. لذلك يبدو لي أن محاولتك الثانية صحيحة في الواقع:

وبالمثل ، إذا قمت بتغيير L2 في السطر 3 إلى "لا شيء" ، فإنه يعيد كل L1 فقط غير في L2 ، ولكن لا شيء من L2.

يبدو أنك تحاول حساب اختلاف متماثل, ، على الرغم من أنه ليس من الواضح بالنسبة لي أن هذا هو ما يطلبه التمرين.

إذا كنت تريد أن تكون ذكيًا حيال ذلك ، فربما يمكنك تمرير قائمة ثالثة في الوظيفة لتكون بمثابة تراكم. عندما يكون لدى L1 عناصر ، ادفع العنصر الأول إلى المجمع (واتصل بشكل متكرر) عندما (null (member (first L1) L2)). عندما يكون L1 فارغًا ، تحقق من عناصر L2 مقابل قائمة التراكم ، وفعل الشيء نفسه. عندما يكون L1 و L2 فارغًا ، أعد قائمة التراكم.

Answer 2

في LISP هذا هو تعريف "الفرق المحدد":

set-difference list1 list2 &key (test #'eql) test-not (key #'identity)
   Function
   Returns a list of elements of list1 that do not appear in list2. 

هذا هو تطبيقك المعدل:

(defun list-diff (L1 L2)
  (cond
    ((null L1) L1)
    ((member (first L1) L2) (list-diff (rest L1) L2))
    (t (cons (first l1) (list-diff (rest l1) l2)))))