لیست تفاوت
 | این مقاله، لیست تفاوت، اخیراً بهواسطهٔ فرایند ایجاد مقاله ایجاد شدهاست. بازبینیکننده در حال بستن درخواست است و این برچسب احتمالاً بهزودی برداشته می‌شود.
ابزارهای بازبینی: پیشبارگیری بحث اعلان به نگارنده |
خطای اسکریپتی: پودمان «AfC submission catcheck» وجود ندارد. در علوم کامپیوتر، اصطلاح لیست تفاوت به ساختار داده‌ای اشاره دارد که فهرستی را با عملیات الحاق O(1) کارآمد و تبدیل به لیست پیوندی در زمانی متناسب با طول آن نشان می‌دهد. لیست‌های تفاوت را می‌توان با استفاده از توابع درجه یک یا با استفاده از یکسان‌سازی پیاده‌سازی کرد. اینکه آیا یک لیست تفاوت کارآمدتر از سایر نمایش‌های لیست است به الگوهای استفاده بستگی دارد. اگر یک الگوریتم با به هم پیوستن لیست‌های کوچک‌تر، که خود با به هم پیوستن فهرست‌های کوچک‌تر ساخته شده‌اند، فهرستی بسازد، آن‌گاه استفاده از فهرست‌های تفاوت می‌تواند با «مسطح کردن» محاسبات ساخت فهرست، عملکرد را بهبود بخشد.
پیاده‌سازی با استفاده از توابع[ویرایش]
یک لیست تفاوت f یک تابع تک آرگومان الحاقی L است که وقتی یک لیست پیوندی X به عنوان آرگومان داده می‌شود، یک لیست پیوندی حاوی L که به X اضافه شده است را برمی‌گرداند. الحاق لیست‌های تفاوت به عنوان ترکیب تابع اجرا می‌شود. محتویات ممکن است با استفاده از f [] بازیابی شوند.[۱]
این پیاده‌سازی معمولاً در زبان‌های برنامه‌نویسی تابعی مانند Haskell استفاده می‌شود، اگرچه می‌توان از آن در زبان‌های دیگر نیز استفاده کرد.
به عنوان توابع، لیست‌های تفاوت، نمایشی از لیست‌ها به‌عنوان مونوئید یا به‌طور خاص‌تر مونوئید تبدیل آن‌ها ناشی از ضرب چپ هستند.
نمونه‌هایی از استفاده در نوع ShowS در Prelude of Haskell و در کتابخانه لیست تفاوت دونالد بروس استوارت برای Haskell هستند.[۲]
پیاده‌سازی با استفاده از یکسان‌سازی[ویرایش]
اجرای دیگری در زبان برنامه‌نویسی منطقی Prolog از متغیرهای یکسان‌سازی استفاده می‌کند.[۳] یک لیست تفاوت یک جفت OpenList-Hole است که در آن اولین عنصر OpenList لیستی است که شامل یک متغیر یکسان‌سازی نامحدود (حفره) است و عنصر دوم Hole مرجعی به سوراخ است.
منابع[ویرایش]
- ↑ A Novel Representation of Lists and Its Application to the Function "Reverse" by John Hughes (1986)
- ↑ Difference Lists in Haskell (programming language)
- ↑ Open Lists and Difference Lists in Prolog Retrieved 2019-02-17
This article "لیست تفاوت" is from Wikipedia. The list of its authors can be seen in its historical and/or the page Edithistory:لیست تفاوت. Articles copied from Draft Namespace on Wikipedia could be seen on the Draft Namespace of Wikipedia and not main one.
