SORU
10 HAZİRAN 2012, Pazar


Haskell sonsuz bir liste açısından tembel değerlendirme

Sanki sonsuz bir liste çalışma performansını merak ediyorum aşağıda:

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

Bu fibonacci dizisi sonsuz bir liste oluşturur.

Benim sorum ise şu bunu yaparsam

takeWhile (<5) fibs

kaç kez fibs listedeki her terim değerlendiriyor? Görünüyor takeWhile Her bir kalem için yüklem işlevi denetler beri listesi, fibs liste her dönem birden çok kez değerlendirecektir. Bu ilk 2 dönem ücretsiz olarak verilir. takeWhile değerlendirmek istiyor 3 öğe (<5), elde ederiz:

1 : 1 : zipWith ( ) [(1, 1), (1)] => 1 : 1 : 3

takeWhile 4 öğe (<5) değerlendirmek istiyor sonra: fibs özyinelemeli doğası listesi gibi yeniden inşa edecek aşağıdaki:

1 : 1 : zipWith ( ) [(1, 2), (2, 3)] => 1 : 1 : 3 : 5

3 öğe biz ne zaman yeniden hesaplanması gerekiyor gibi görünüyor 4 öğenin değerini değerlendirmek istiyorum. Bu, ayrıca, takeWhile büyük yüklem, işlev işaret eder her önceki değerlendirme olduğundan gereken daha çok iş yapıyor listede bir öğe birden çok kez. Analizim burada doğru ya. Çoklu değerlendirmeler burada önlemek için bazı önbellekleme yapıyor Haskell?

CEVAP
10 HAZİRAN 2012, Pazar


Bu "daha sonra" yapısının bölümden önceki bölümleri için bakın ne? nereye başvuru benlik, tembel bir veri yapısıdır,

Başlangıçta, yapı unevaluated işaretçiler kendisi ile sadece bir hesaplama. Katlanmamış olduğu gibi, değerler yapısı oluşturulur. Zaten hesaplanan başvurular daha sonra yapı parçaları değer zaten orada onları bekleyen bulmak mümkün. Hayır yeniden değerlendirmek için parçaları ve ekstra bir işe ihtiyacım var!

Bellek yapısı sadece unevaluated bir işaretçi olarak başlar. İlk değer baktığımız zamanlar, bu gibi görünüyor:

> take 2 fibs

enter image description here

(bir işaretçi eksileri hücre, işaret '1', ve bir kuyruk tutarak ikinci '1', ve bir işaretçi işlevi (bu arada bu başvuruları geri yalan ve kuyruklu yalan.

Bir adım daha değerlendirme yapısını genişletir ve referanslar slaytlar boyunca:

enter image description here

Ve yapısını gözler önüne serilen o zaman biz gidelim, her zaman bir kapatma yeni unevaluated bir kuyruk oluşturan geri başvurular son adım olan 1. ve 2. öğeleri tutarak. Bu işlem sonsuz :) devam edebilirsiniz

Ve Adı önceki değerlere atıfta olduğumuz için, DZD her öğe yalnızca bir kez değerlendirilir mutlu bize hafıza onları korur.

Bunu Paylaş:
  • Google+
  • E-Posta
Etiketler:

YORUMLAR

SPONSOR VİDEO

Rastgele Yazarlar

  • Fraser Raft

    Fraser Raft

    9 Mart 2010
  • Joanna Okrajni

    Joanna Okraj

    4 EYLÜL 2010
  • mahalodotcom

    mahalodotcom

    8 HAZİRAN 2007