Haskell'in tembelliği Python jeneratörlerine zarif bir alternatif mi?

Question

Bir programlama alıştırmasında, önce faktoriyel fonksiyonun programlanması ve daha sonra toplamı hesaplaması istendi: 1! + 2! + 3! +... n!O(n) çarpımlarında (bu yüzden faktörü doğrudan kullanamıyoruz). Çözümü bu özel (önemsiz) sorun için araştırmıyorum, Haskell yeteneklerini keşfetmeye çalışıyorum ve bu problem oynamak istediğim bir oyuncak.

Python jeneratörleri bu problem için güzel bir çözüm olabilir diye düşündüm. Örneğin: Orada bu jeneratörün daha benzer bir davranışa sahip Haskell bir şey oldu ve ben tembellik herhangi bir ek kavram olmadan tüm personel yapmak düşündüm eğer

from itertools import islice 
def ifact(): 
    i , f = 1, 1 
    yield 1 
    while True: 
     f *= i 
     i += 1 
     yield f 

def sum_fact(n): 
    return sum(islice(ifact(),5)) 

Sonra anlamaya çalıştık.

Örneğin,

fact = scan1 (*) [1..] 

ile benim Python ifact değiştirmek Ve sonra aşağıdaki ile egzersiz çözebilir:

sum n = foldl1 (+) (take n fact) 

ben bu çözüm Python'un birine gerçekten "eşdeğer" olup olmadığını merak Zaman karmaşıklığı ve bellek kullanımı ile ilgili. Haskell'in çözümünün, tüm unsurları bir zamanlar bir kez kullanıldığından asla saklayamayacağını söyleyebilirim.

Doğru veya tamamen yanlış mıyım?

---

DÜZENLEME: Ben daha doğrusu kontrol olmalıdır:

Prelude> foldl1 (+) (take 4 fact) 
33 
Prelude> :sprint fact 
fact = 1 : 2 : 6 : 24 : _ 

Yani (benim uygulaması) Haskell artık kullanılmamaktadır olsa bile, sonucunu saklamak.

Answer 1

Kişisel örnekler bellek kullanımında eşdeğer değil bulunmaktadır. O (sayılar çok çabuk büyüdün kalmamak) Bir + ile * yerine görmek ve sonra büyük bir n böyle 10 olarak^7 her iki örneklerini çalıştırmak kolaydır. Haskell sürümünüz çok fazla bellek tüketecek ve python onu düşük tutacaktır.

Python jeneratör sonra değerlerinin bir listesini oluşturmak Özetle olmaz. Bunun yerine, sum işlevi, üreteçten birer birer değerler alacak ve bunları biriktirecektir. Böylece, bellek kullanımı sabit kalacaktır.

Haskell tembel fonksiyonlarını değerlendirmek, ancak hesaplamak için tamamlanmadan ifadeyi değerlendirmek zorunda kalacaktır foldl1 (+) (take n fact) derler. Büyük n için bu, (foldl (+) 0 [0..n])'un yaptığı gibi büyük bir ifadeye dönüşecektir. Değerlendirme ve azaltma hakkında daha fazla bilgi için buraya bir göz atın: https://www.haskell.org/haskellwiki/Foldr_Foldl_Foldl%27.

sum n'nu, yukarıdaki bağlantıda belirtildiği gibi foldl1 yerine foldl1' kullanarak düzeltebilirsiniz. @ User2407038 yorumunda da açıkladığı gibi, fact'u da yerel olarak tutmanız gerekir. Aşağıdaki sabit bellek kullanımı ile ghc içinde çalışır:

let notfact = scanl1 (+) [1..] 
let n = 20000000 
let res = foldl' (+) 0 (take n notfact) 

Not notfact hafıza hususlar yerine gerçek faktöriyele durumunda bir endişe daha az olduğunu. Rakamlar çok hızlı olacak, keyfi doğruluk aritmetiği şeyleri yavaşlatır, böylece farkı görmek için n'un büyük değerlerine ulaşamazsınız.

Answer 2

Temel olarak, evet: Haskell'in tembel listeleri, Python'un jeneratörlerine çok benziyor, eğer bu jeneratörler zahmetsizce klonlanabilir, önbelleklenebilir ve birleştirilebilir. StopIteration'u yükseltmek yerine, []'u özyinelemeli işlevinizden döndürerek, üretime iş parçacığı girebilirsiniz.

Kendinden özyineleme nedeniyle bazı daha soğuk şeyler yaparlar. Herhangi bir iteratif döngü ilmek durumunu teşvik ederek yinelemeli algoritma dönüştürülebilir Genel olarak

fibs = 1 : 1 : zipWith (+) fibs (tail fibs) 

: olarak

facts = 1 : zipWith (*) facts [1..] 

veya Fibonaccis: Örneğin, faktör jeneratörü daha deyimsel gibi üretilir Bir fonksiyonun argümanları ve sonra bir sonraki döngü döngüsünü elde etmek için tekrar tekrar çağırmak. Jeneratörler öyle gibidir, ancak bazı elemanlar her yineleme fonksiyonunun yinelemesini başlatırız, 'go ____ = (şeyler): go ____.

mükemmel eşdeğer nedenle: En hızlı ne açısından

ifact :: [Integer] 
ifact = go 1 1 
    where go f i = f : go (f * i) (i + 1) 

sum_fact n = sum (take n ifact) 

, Haskell mutlak hızlı muhtemelen "döngü" olacaktır:

sum_fact n = go 1 1 1 
    where go acc fact i 
      | i <= n = go (acc + fact) (fact * i) (i + 1) 
      | otherwise = acc 

bu "olması kuyruk özyinelemeli "(go bir çağrı borusu (+) veya (*) gibi başka fonksiyona go için herhangi bir alt aramaları değil) derleyici gerçekten sıkı bir döngü içine paket anlamına gelir, ve ben onu karşılaştırıyorum yüzden" döngüler için "bu gerçekten Haskell için yerli bir fikir değil.

yukarıdaki sum_fact n = sum (take n ifact)

biraz bundan daha yavaş fakat facts zipWith ile tanımlanır sum (take n facts) daha hızlıdır. Hız farklılıkları çok büyük değil ve çoğunlukla tekrar kullanılmayan bellek ayırmalarına düştüğümü düşünüyorum.

Answer 3

Gerçekten de, tembel listeler bu şekilde kullanılabilir. Ancak bazı ince farklar vardır:

• Listeler veri yapılarıdır. Yani (@ChrisDrost hafıza yayınlanmamış tutmak pahasına, anlatıldığı gibi değerlerin ve özyinelemeli hilelere yeniden hesaplamaya önleyebilirsiniz) hem iyi hem kötü olabilir ki, onları değerlendirdikten sonra tutabilirsiniz.
• Listeler saftır. Jeneratörlerdeki yan etkilerle ilgili hesaplamalar yapabilirsiniz, bunu listelerde yapamazsınız (ki bu çoğu zaman arzu edilir).
• Haskell tembel dili olduğu için, tembellik her yerde ve sadece Haskell bir zorunluluk dilden bir program dönüştürmek if (@RomanL onun cevabını açıklar gibi), bellek gereksinimi ciddi değiştirebilir.

Ancak Haskell, jeneratör/tüketici modelini gerçekleştirmek için daha gelişmiş araçlar sunar. Şu anda bu soruna odaklanan üç kütüphane var: pipes, conduit and iteratees. Benim favorim conduit, kullanımı kolaydır ve türlerinin karmaşıklığı düşük tutulur.

Onlar özellikle karmaşık boru hatlarını oluşturabilmeleri ve size bir boru hattına izin hangi yan etkileri söylemek olanak sağlayan bir seçilmiş monad, dayandırabilirsiniz, çeşitli avantajları vardır. İşte

import Data.Functor.Identity 
import Data.Conduit 
import qualified Data.Conduit.List as C 

ifactC :: (Num a, Monad m) => Producer m a 
ifactC = loop 1 1 
    where 
    loop r n = let r' = r * n 
       in yield r' >> loop r' (n + 1) 

sumC :: (Num a, Monad m) => Consumer a m a 
sumC = C.fold (+) 0 

main :: IO() 
main = (print . runIdentity) (ifactC $= C.isolate 5 $$ sumC) 
-- alternatively running the pipeline in IO monad directly: 
-- main = (ifactC $= C.isolate 5 $$ sumC) >>= print 

biz süresiz faktöriyel'dir veren bir Producer (hayır girdi tüketir bir kanal) oluşturmak şöyledir: kanal kullanarak

, sizin örnek ifade edilebilir. Daha sonra, isolate ile oluşturuyoruz, bu sayede, belirli bir sayıda değerden daha fazla yayılmamasını sağlıyoruz ve daha sonra değerleri toplayan ve sonucu döndüren Consumer ile oluşturuyoruz.