پیش‌نویس:لیست تفاوت

در علوم کامپیوتر، اصطلاح لیست تفاوت به ساختار داده‌ای اشاره دارد که فهرستی را با عملیات الحاق O(1) کارآمد و تبدیل به لیست پیوندی در زمان متناسب با طول آن نشان می‌دهد. لیست‌های تفاوت را می‌توان با استفاده از توابع درجه یک یا با استفاده از یکسان‌سازی پیاده‌سازی کرد. اینکه آیا یک لیست تفاوت کارآمدتر از سایر نمایش‌های لیست است به الگوهای استفاده بستگی دارد. اگر یک الگوریتم با به هم پیوستن لیست‌های کوچک‌تر، که خود با به هم پیوستن فهرست‌های کوچک‌تر ساخته شده‌اند، فهرستی بسازد، آن‌گاه استفاده از فهرست‌های تفاوت می‌تواند با «مسطح کردن» محاسبات ساخت فهرست، عملکرد را بهبود بخشد.

پیاده‌سازی با استفاده از توابع

یک لیست تفاوت f یک تابع تک آرگومان الحاقی L است که وقتی یک لیست پیوندی X به عنوان آرگومان داده می‌شود، یک لیست پیوندی حاوی L که به X اضافه شده است را برمی‌گرداند. الحاق لیست‌های تفاوت به عنوان ترکیب تابع اجرا می‌شود. محتویات ممکن است با استفاده از f [] بازیابی شوند.

این پیاده‌سازی معمولاً در زبان‌های برنامه‌نویسی تابعی مانند Haskell استفاده می‌شود، اگرچه می‌توان از آن در زبان‌های امری نیز استفاده کرد.

به عنوان توابع، لیست‌های تفاوت، نمایشی از لیست‌ها به‌عنوان مونوئید یا به‌طور خاص‌تر مونوئید تبدیل آن‌ها ناشی از ضرب چپ هستند.

نمونه‌هایی از استفاده در نوع ShowS در Prelude of Haskell و در کتابخانه لیست تفاوت دونالد بروس استوارت برای Haskell هستند.

پیاده‌سازی با استفاده از یکسان‌سازی

اجرای دیگری در زبان برنامه‌نویسی منطقی Prolog از متغیرهای یکسان‌سازی استفاده می‌کند. یک لیست تفاوت یک جفت OpenList-Hole است که در آن اولین عنصر OpenList لیستی است که شامل یک متغیر یکسان‌سازی نامحدود (حفره) است و عنصر دوم Hole مرجعی به سوراخ است.