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

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

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

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

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

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

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

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;
    }
}