Bir listenin tüm öneklerini oluşturmak için en etkili tamamen işlevsel algoritma nedir?

Question

prefixes ls = zipWith take [1 .. length ls] (repeat ls) 

Bundan daha iyisini yapmanın bir yolu var mı? Sezgisel olarak bana öyle geliyor ki, tersine ya da ek uygulamasının n kez uygulanması gerektiğinden, tamamen işlevsel bir dilde O (n²) 'nin altında bir algoritma elde edilemiyor. Bunu nasıl kanıtlayacağımı bilmiyorum.

Answer 1

Sanırım haklısınız. Listenin omurgaları paylaşılamaz, çünkü tüm kuyruklar farklıdır. Bu nedenle, tam olarak değerlendirildiyse, öneklerin listesi, oluşturmak için Ω (n) alması gereken tam Θ (n) boşluğunu alacaktır.

Yazdığınız işlevin (lazier sürümü) Data.Listinits olarak bulunduğunu unutmayın.

Yapabildiğiniz temiz bir optimizasyon var. Bu denklem tutan: doğrusal zamanda

map (foldl f z) . inits = scanl f z 

Ve scanl çalışır. Böylece, her bir önek için yapmak istediğiniz şeyi sol kat olarak ifade ederseniz, öneklerin listesini oluşturmanın karesel karmaşıklığından kaçınabilirsiniz.

Answer 2

Bu temsile bağlı değil mi? Listeleri bitişik depolama alanı artı başlatma ve bitiş dizini olarak gösterirseniz (bytestrings öğesine benzer), depolamayı paylaşabilir ve yalnızca indeks listesini oluşturmak için bir kez geçiş yapmanız gerekir. Algoritma sadece temsil değil, değişmeyecekti. Bu özel kullanım durumu için, snoc listelerini (ikili listeler, ancak listenin başlangıcı değil, sondan yuvalanmış) kullanarak, alt listelerin paylaşılmasına da izin verilir, değil mi?