Tamamen işlevsel veri yapısı - Purely functional data structure

Gelen bilgisayar bilimleri , bir salt işlevsel veri yapısı bir olan veri yapısı bir uygulanabilir tamamen işlevsel dili . Rastgele bir veri yapısı ile tamamen işlevsel olan arasındaki temel fark, ikincisinin (kesinlikle) değişmez olmasıdır . Bu kısıtlama, veri yapısının değişmez nesnelerin avantajlarına sahip olmasını sağlar: (tam) kalıcılık , nesnelerin hızlı kopyalanması ve iş parçacığı güvenliği . Verimli, tamamen işlevsel veri yapıları, tembel değerlendirme ve memoization kullanımını gerektirebilir .

Tanım

Kalıcı veri yapıları , kendilerinin önceki sürümlerini değiştirilmeden tutma özelliğine sahiptir. Öte yandan, örneğin yapılar diziler bir itiraf yıkıcı güncelleştirme olduğunu, geri alınamaz bir güncelleme. Bir program dizinin bazı indekslerine bir değer yazdığında, önceki değeri artık alınamaz.

Resmi olarak, tamamen işlevsel bir veri yapısı , Haskell gibi tamamen işlevsel bir dilde uygulanabilen bir veri yapısıdır . Pratikte, veri yapılarının yalnızca tanımlama grupları, toplam türleri , ürün türleri ve tamsayılar, karakterler, dizeler gibi temel türler gibi kalıcı veri yapıları kullanılarak oluşturulması gerektiği anlamına gelir . Böyle bir veri yapısı mutlaka kalıcıdır. Ancak, tüm kalıcı veri yapıları tamamen işlevsel değildir. Örneğin, kalıcı bir dizi , kalıcı olan ve bir dizi kullanılarak uygulanan, dolayısıyla tamamen işlevsel olmayan bir veri yapısıdır.

Tamamen işlevsel veri yapıları kitabında Okasaki, yıkıcı güncellemeleri usta şefin bıçaklarıyla karşılaştırıyor. Yıkıcı güncellemeler geri alınamaz ve bu nedenle önceki değerin artık gerekli olmadığı kesin olmadıkça kullanılmamalıdır. Ancak yıkıcı güncellemeler, diğer teknikler kullanılarak elde edilemeyen verimliliğe de izin verebilir. Örneğin, bir dizi ve yıkıcı güncellemeler kullanan bir veri yapısı, dizinin yerini bir harita , bir rastgele erişim listesi veya tamamen işlevsel bir uygulamaya izin veren dengeli bir ağaç ile değiştirildiği benzer bir veri yapısı ile değiştirilebilir . Ancak erişim maliyeti sabit zamandan logaritmik zamana yükselebilir .

Bir veri yapısının tamamen işlevsel olmasını sağlama

Bir veri yapısı hiçbir zaman doğası gereği işlevsel değildir. Örneğin, bir yığın, tek bağlantılı bir liste olarak uygulanabilir . Bu uygulama, yığındaki tek işlemler eski yığını değiştirmeden yeni bir yığın döndürdüğü sürece tamamen işlevseldir. Ancak, dil tamamen işlevsel değilse, çalışma zamanı sistemi değişmezliği garanti edemeyebilir. Bu, Okasaki tarafından gösterilmektedir, burada tek başına bağlantılı iki listenin birleştirilmesinin hala zorunlu bir ayar kullanılarak yapılabileceğini göstermektedir.

Bir veri yapısının saf olmayan bir işlevsel dilde tamamen işlevsel bir şekilde kullanılmasını sağlamak için, yalnızca yetkili işlevler aracılığıyla manipülasyonu sağlamak için modüller veya sınıflar kullanılabilir.

Tamamen İşlevsel Veri Yapılarını Kullanma

Tamamen işlevsel veri yapılarını kullanmak için mevcut kodu uyarlamanın temel zorluklarından biri, değişebilir veri yapılarının onları kullanan işlevler için "gizli çıktılar" sağlaması gerçeğinde yatmaktadır. Tamamen işlevsel veri yapılarını kullanmak için bu işlevleri yeniden yazmak, bu veri yapılarının açık çıktılar olarak eklenmesini gerektirir.

Örneğin, değiştirilebilir bir listeyi kabul eden, listeye bir öğe ekleyen ve yeni listenin uzunluğunu döndüren bir işlev düşünün. Tamamen işlevsel bir ortamda, listeye yeni bir öğe eklemek yeni bir liste oluşturur, ancak orijinali güncellemez. Bu nedenle, kullanışlı olması için, bu işlevin tamamen işlevsel bir sürümünün, hem listenin uzunluğunu hem de yeni listenin kendisini döndürmesi gerekir. En genel durumda, bu şekilde dönüştürülen bir program, her işlev çağrısından ek bir sonuç olarak programın "durumunu" veya "saklamasını" döndürmelidir. Böyle bir programın mağaza geçme tarzında yazıldığı söylenir .

Örnekler

Tamamen işlevsel uygulamalara sahip soyut veri yapılarının bir listesi:

Tasarım ve Uygulama

Bilgisayar bilimcisi Chris Okasaki , Purely Functional Data Structures adlı kitabında , küçük bir alt kümesi aşağıda özetlenen tamamen işlevsel veri yapılarını tasarlamak ve uygulamak için kullanılan teknikleri açıklar.

Tembellik ve not tutma

Tembel değerlendirme, tamamen işlevsel bir dilde özellikle ilginçtir çünkü değerlendirmenin sırası bir işlevin sonucunu asla değiştirmez. Bu nedenle, tembel değerlendirme doğal olarak tamamen işlevsel veri yapılarının inşasının önemli bir parçası haline gelir. Bir hesaplamanın yalnızca sonucu gerçekten gerekli olduğunda yapılmasına izin verir. Bu nedenle, tamamen işlevsel bir veri yapısının kodu, verimlilik kaybı olmadan, etkin olarak kullanılacak verileri ve göz ardı edilecek verileri benzer şekilde değerlendirebilir. Gereken tek hesaplama birinci tür veriler içindir; aslında yapılacak olan budur.

Verimli, tamamen işlevsel veri yapıları oluşturmanın en önemli araçlarından biri notlandırmadır. Bir hesaplama yapıldığında kaydedilir ve ikinci kez yapılması gerekmez. Bu özellikle tembel uygulamalarda önemlidir; ek değerlendirmeler aynı sonucu gerektirebilir, ancak önce hangi değerlendirmenin gerektireceğini bilmek imkansızdır.

İtfa edilmiş analiz ve zamanlama

Bazı veri yapıları, hatta dinamik diziler gibi tamamen işlevsel olmayanlar bile , çoğu zaman verimli (örneğin, dinamik diziler için sabit zaman) ve nadiren verimsiz (örneğin, dinamik diziler için doğrusal zaman) işlemleri kabul eder. Amortisman daha sonra operasyonların ortalama çalışma süresinin verimli olduğunu kanıtlamak için kullanılabilir. Başka bir deyişle, birkaç verimsiz işlem yeterince nadirdir ve bir işlem dizisi düşünüldüğünde zaman karmaşıklığının asimptotik evrimini değiştirmez.

Genel olarak, kalıcı veri yapıları için verimsiz işlemlere sahip olmak kabul edilemez, çünkü bu işlem birçok kez çağrılabilir. Kullanıcının operasyon için geçen sürenin tahmin edilebilir olmasını gerektirebileceği gerçek zamanlı veya zorunlu sistemler için kabul edilemez. Ayrıca, bu öngörülemezlik paralellik kullanımını zorlaştırmaktadır .

Bu sorunlardan kaçınmak için, bazı veri yapıları verimsiz operasyonun ertelenmesine izin verir - buna zamanlama denir . Tek gereklilik, verimsiz işlemin hesaplanmasının, sonuca gerçekten ihtiyaç duyulmadan önce sona ermesi gerektiğidir. Verimsiz operasyonun sabit bir kısmı, aşağıdaki verimli operasyon çağrısı ile eşzamanlı olarak gerçekleştirilir, böylece verimsiz operasyon, ihtiyaç duyulduğunda zaten tamamen yapılır ve her bir bireysel operasyon verimli kalır.

Örnek: sıra

İtfa edilmiş kuyruklar , tek bağlantılı iki listeden oluşur: ön ve ters arka. Öğeler arka listeye eklenir ve ön listeden çıkarılır. Ayrıca, ön sıra boş olduğunda, arka sıra tersine çevrilir ve ön sıra olur, arka sıra boşalır. Her işlemin itfa edilmiş zaman karmaşıklığı sabittir. Listenin her hücresi en fazla bir defa eklenir, ters çevrilir ve çıkarılır. Arka listenin tersine çevrildiği verimsiz bir işlemden kaçınmak için, gerçek zamanlı sıralar , arka listenin yalnızca ön liste kadar uzun olduğu kısıtlamasını ekler. Arka listenin ön listeden daha uzun olmasını sağlamak için ön liste arka listeye eklenir ve tersine çevrilir. Bu işlem verimsiz olduğu için hemen yapılmaz. Bunun yerine, sonraki işlemlere yayılır. Böylece, her hücre ihtiyaç duyulmadan önce hesaplanır ve yeni bir verimsiz operasyon çağrılmadan önce yeni ön liste tamamen hesaplanır.

Ayrıca bakınız

Referanslar

Dış bağlantılar