قائمة الاختلافات

في علوم الحاسوب ، يشير مصطلح " قائمة الفرق" إلى بنية بيانات تمثل قائمةً بعملية دمج فعّالة ذات زمن ثابت O(1)، وتحويلها إلى قائمة مرتبطة في زمن يتناسب مع طولها. يمكن تنفيذ قوائم الفرق باستخدام الدوال من الدرجة الأولى أو باستخدام التوحيد. يعتمد مدى كفاءة قائمة الفرق مقارنةً بتمثيلات القوائم الأخرى على أنماط الاستخدام. فإذا كانت الخوارزمية تبني قائمةً بدمج قوائم أصغر، والتي بدورها تُبنى بدمج قوائم أصغر منها، فإن استخدام قوائم الفرق يُحسّن الأداء من خلال "تبسيط" عمليات بناء القائمة.

قائمة الفروق f هي دالة ذات وسيط واحد تُسمى append L ، والتي عند إعطائها قائمة مرتبطة X كوسيط ، تُعيد قائمة مرتبطة تحتوي على L مُضافةً إلى X. يتم تنفيذ دمج قوائم الفروق باستخدام تركيب الدوال . يمكن استرجاع المحتويات باستخدام f[] . ^{[ 1 ]}

يُستخدم هذا التطبيق عادةً في لغات البرمجة الوظيفية مثل Haskell ، على الرغم من أنه يمكن استخدامه في اللغات الإجرائية أيضًا.

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

ومن أمثلة الاستخدام نوع ShowS في مقدمة Haskell، ومكتبة قائمة الفرق الخاصة بدونالد بروس ستيوارت للغة Haskell . ^{[ 2 ]}

يستخدم تطبيق آخر في لغة البرمجة المنطقية برولوج متغيرات التوحيد. ^{[ 3 ]} قائمة الفرق هي زوج OpenList-Hole ، حيث يكون العنصر الأول OpenList عبارة عن قائمة تحتوي على متغير توحيد غير مرتبط (hole)، والعنصر الثاني Hole عبارة عن مرجع إلى الـhole.