داده ساختارهای تابعی محض

در علوم رایانه، یک داده ساختار تابعی محض، داده‌ساختاری است که امکان پیاده‌سازی آن به وسیله یک زبان برنامه‌نویسی تابعی محض وجود دارد. تفاوت اصلی یک داده ساختار دلخواه با تابعی محض در این است که دومی حتماً باید تغییرناپذیر باشد. این محدودیت تضمین می‌کند که داده ساختار از مزایای اشیا تغییرناپذیر برخوردار است از جمله: ساختار داده‌های ماندگار، کپی سریع از اشیا و ایمنی چندنخی.

داده ساختارهای تابعی محض بهینه در صورت نیاز ممکن است از ارزیابی کندرو و مموایز کردن استفاده کنند.

تعریف

داده ساختارهای تابعی محض اغلب متفاوت از همتای برنامه‌نویسی دستوری خود ارائه داده می‌شوند. برای نمونه، یک آرایه با زمان دسترسی و بروزرسانی ثابت بخش پایه‌ای بسیاری از زبان‌های برنامه‌نویسی دستوری است. اساس بسیاری از داده ساختارهای دستوری مانند هرم دودویی و جدول درهم‌سازی آرایه‌ها هستند. آرایه می‌تواند با یک آرایه انجمنی یا لیست با دسترسی تصادفی که تابعی محض پیاده‌سازی شده‌است جایگزین شود، اما دسترسی و بروزرسانی ممکن است در پیچیدگی زمانی لگاریتمی انجام شود.

این داده ساختارها می‌توانند در زبان‌های دستوری و شی گرا پیاده‌سازی شوند، اما عملکرد حافظه و زمان‌شان ممکن است از به لحاظ نداشتن همه ویژگی‌های داده ساختارهای تابعی محض پایین‌تر باشد.

ضمانت اینکه داده ساختاری کاملاً تابعی باشد

هیچ داده ساختاری ذاتاً تابعی نیست، به عنوان مثال یک پشته می‌تواند با یک لیست پیوندی یک طرفه پیاده‌سازی شود. این پیاده‌سازی تا زمانی تابعی محض است که عملیات‌های روی پشته، پشته جدیدی بدون ایجاد تغییری در پشته قدیمی بازگرداند. گرچه اگر زبان برنامه‌نویسی تابعی محض نباشد ممکن است در حال اجرا نتواند اصل تغییرناپذیری را ضمانت کند.

برای اطمینان از این که داده ساختارها به صورت کاملاً تابعی در یک زبان تابعی نامناسب مورد استفاده قرار می‌گیرد، می‌توان از ماژول‌ها و کلاس (برنامه‌نویسی)‌ها برای اطمینان از دستکاری توابع مجاز استفاده کرد.

مثال‌ها

لیستی از داده ساختارهای انتزاعی با پیاده‌سازی کاملاً تابعی آن‌ها در زیر آورده شده‌است:

• پشته به عنوان لیست پیوندی پیاده‌سازی می‌شود.
• صف (نوع داده انتزاعی)، به عنوان صف بلا درنگ پیاده‌سازی می‌شود.
• صف دو طرفه، به عنوان صف دو طرفه بلا درنگ پیاده‌سازی می‌شود.
• مجموعه‌ای عناصر منظم و نگاشت درایه‌بندی شده با کلیدهای منظم به عنوان درخت قرمز- سیاه، یا به‌طور کلی با درخت جستجو پیاده‌سازی می‌شود.
• صف اولویت‌دار به عنوان صف برودال پیاده‌سازی می‌شود.
• لیست با دسترسی تصادفی، به عنوان لیست تصافی دودویی نامتوازن پیاده‌سازی می‌شود.

public class Stack<E> {
    private final E head;
    private final Stack<E> tail;

    private Stack(){
        head = null;
        tail = null;
    }

    private Stack(E head, Stack<E> tail){
        this.head = head;
        this.tail = tail;
    }

    public Stack<E> push(E element){
        return new Stack<E>(element, this);
    }

    public Stack<E> pop(){
        return tail;
    }

    public E top(){
        return head;
    }

    public boolean isEmpty(){
        return tail == null;
    }
}