Dengan mekanisme apa fungsi fibonacci ini dimoalkan?
fib = (map fib' [0..] !!)
where fib' 1 = 1
fib' 2 = 1
fib' n = fib (n-2) + fib (n-1)
Dan pada catatan terkait, mengapa versi ini tidak?
fib n = (map fib' [0..] !! n)
where fib' 1 = 1
fib' 2 = 1
fib' n = fib (n-2) + fib (n-1)
fib 0
tidak berakhir: Anda mungkin ingin kasus dasarfib'
menjadifib' 0 = 0
danfib' 1 = 1
.fibs = 1:1:zipWith (+) fibs (tail fibs)
danfib = (fibs !!)
.Jawaban:
Mekanisme evaluasi di Haskell adalah dengan kebutuhan : ketika sebuah nilai dibutuhkan, itu dihitung, dan tetap siap jika diminta lagi. Jika kita mendefinisikan beberapa daftar,
xs=[0..]
dan kemudian meminta elemen ke-100,xs!!99
slot ke-100 dalam daftar akan "disempurnakan", menahan nomor tersebut99
sekarang, siap untuk akses berikutnya.Itulah yang dieksploitasi oleh trik itu, "melalui daftar". Dalam definisi Fibonacci rekursi ganda normal
fib n = fib (n-1) + fib (n-2)
, fungsi itu sendiri dipanggil, dua kali dari atas, menyebabkan ledakan eksponensial. Tapi dengan trik itu, kami membuat daftar untuk hasil sementara, dan pergi "melalui daftar":Triknya adalah membuat daftar itu dibuat, dan menyebabkan daftar itu tidak hilang (melalui pengumpulan sampah) di antara panggilan ke
fib
. Cara termudah untuk mencapai ini, adalah dengan menamai daftar itu. "Jika Anda menyebutkannya, itu akan tetap ada."Versi pertama Anda mendefinisikan konstanta monomorfik, dan versi kedua mendefinisikan fungsi polimorfik. Fungsi polimorfik tidak dapat menggunakan daftar internal yang sama untuk jenis berbeda yang mungkin perlu dilayaninya, jadi tidak ada pembagian , yaitu tidak ada memoisasi.
Dengan versi pertama, compiler bermurah hati dengan kami, mengambil subekspresi konstan (
map fib' [0..]
) dan menjadikannya entitas terpisah yang dapat dibagikan, tetapi tidak ada kewajiban untuk melakukannya. dan sebenarnya ada kasus di mana kami tidak ingin melakukannya untuk kami secara otomatis.( sunting :) Pertimbangkan penulisan ulang ini:
Jadi kisah sebenarnya tampaknya tentang definisi lingkup bersarang. Tidak ada lingkup luar dengan definisi pertama, dan definisi ketiga berhati-hati untuk tidak memanggil lingkup luar
fib3
, tetapi tingkat yang samaf
.Setiap pemanggilan baru
fib2
tampaknya membuat definisi bersarangnya lagi karena salah satu dari mereka dapat (secara teori) didefinisikan secara berbeda tergantung pada nilain
(terima kasih kepada Vitus dan Tikhon untuk menunjukkannya). Dengan definisi pertama tidak ada yangn
bisa diandalkan, dan dengan definisi ketiga ada ketergantungan, tetapi setiap panggilan terpisah kefib3
panggilanf
yang berhati-hati untuk hanya memanggil definisi dari lingkup tingkat yang sama, internal ke pemanggilan spesifik inifib3
, sehingga hal yang samaxs
akan terjadi. digunakan kembali (yaitu dibagikan) untuk pemanggilan itufib3
.Tetapi tidak ada yang menghalangi kompilator untuk mengenali bahwa definisi internal dalam salah satu versi di atas sebenarnya tidak bergantung pada
n
pengikatan luar , untuk melakukan pengangkatan lambda bagaimanapun juga, menghasilkan memoisasi penuh (kecuali untuk definisi polimorfik). Sebenarnya itulah yang terjadi dengan ketiga versi ketika dideklarasikan dengan tipe monomorphic dan dikompilasi dengan flag -O2. Dengan deklarasi tipe polimorfik,fib3
menunjukkan berbagi lokal danfib2
tidak berbagi sama sekali.Pada akhirnya, bergantung pada kompilator, dan pengoptimalan kompilator yang digunakan, dan bagaimana Anda mengujinya (memuat file di GHCI, dikompilasi atau tidak, dengan -O2 atau tidak, atau mandiri), dan apakah ia mendapat jenis monomorfik atau polimorfik, perilaku mungkin berubah sepenuhnya - apakah itu menunjukkan berbagi lokal (per panggilan) (yaitu waktu linier pada setiap panggilan), memoisasi (yaitu waktu linier pada panggilan pertama, dan 0 waktu pada panggilan berikutnya dengan argumen yang sama atau lebih kecil), atau tidak berbagi sama sekali ( waktu eksponensial).
Jawaban singkatnya adalah, ini adalah kompiler. :)
sumber
fib'
didefinisikan ulang untuk setiapn
dan dengan demikianfib'
difib 1
≠fib'
difib 2
, yang juga berarti daftar yang berbeda. Bahkan jika Anda memperbaiki tipe menjadi monomorfik, itu masih menunjukkan perilaku ini.where
klausa memperkenalkan berbagi sepertilet
ekspresi, tetapi mereka cenderung menyembunyikan masalah seperti ini. Menulis ulang sedikit lebih eksplisit, Anda mendapatkan ini: hpaste.org/71406Int -> Integer
), kemudianfib2
berjalan dalam waktu eksponensial,fib1
danfib3
keduanya berjalan dalam waktu linier tetapifib1
juga dimoisasi - sekali lagi karena untukfib3
definisi lokal didefinisikan ulang untuk setiapn
.pwr (x:xs) = pwr xs ++ map (x:) pwr xs ; pwr [] = [[]]
kami inginpwr xs
dihitung secara mandiri, dua kali, sehingga sampah tersebut dapat dikumpulkan dengan cepat saat diproduksi dan dikonsumsi.Saya tidak sepenuhnya yakin, tapi inilah tebakan yang masuk akal:
Compiler berasumsi bahwa ini
fib n
bisa berbeda di tempat yang berbedan
dan oleh karena itu perlu menghitung ulang daftar tersebut setiap saat. Bit-bit di dalamwhere
pernyataan itu bisa bergantungn
. Artinya, dalam hal ini, seluruh daftar angka pada dasarnya adalah fungsi darin
.Versi tanpa
n
dapat membuat daftar sekali dan membungkusnya dalam sebuah fungsi. Daftar tidak dapat bergantung pada nilai yangn
diteruskan dan ini mudah diverifikasi. Daftar ini adalah konstanta yang kemudian diindeks menjadi. Ini, tentu saja, adalah konstanta yang dievaluasi secara malas, jadi program Anda tidak mencoba untuk segera mendapatkan seluruh daftar (tak terbatas). Karena ini adalah konstanta, ini dapat dibagikan ke seluruh pemanggilan fungsi.Ini dikosongkan sama sekali karena panggilan rekursif hanya perlu mencari nilai dalam daftar. Sejak
fib
versi membuat daftar sekali malas, itu hanya menghitung cukup untuk mendapatkan jawaban tanpa melakukan perhitungan yang berlebihan. Di sini, "malas" berarti bahwa setiap entri dalam daftar adalah thunk (ekspresi yang tidak dievaluasi). Ketika Anda melakukan evaluasi dunk, menjadi nilai, sehingga mengakses waktu berikutnya tidak ada mengulang perhitungan. Karena daftar dapat dibagi di antara panggilan, semua entri sebelumnya sudah dihitung pada saat Anda membutuhkan yang berikutnya.Ini pada dasarnya adalah bentuk pemrograman dinamis yang cerdas dan murah berdasarkan semantik malas GHC. Saya pikir standar hanya menentukan bahwa itu harus tidak ketat , jadi kompiler yang patuh berpotensi mengkompilasi kode ini untuk tidak memo. Namun, dalam praktiknya, setiap kompilator yang masuk akal akan menjadi malas.
Untuk informasi lebih lanjut tentang mengapa kasus kedua berfungsi, baca Memahami daftar yang didefinisikan secara rekursif (fib dalam istilah zipWith) .
sumber
fib' n
mungkin " bisa berbeda di lainn
"?fib
, termasukfib'
, dapat berbeda pada setiap perbedaann
. Menurut saya contoh aslinya agak sedikit membingungkan karenafib'
juga tergantungn
bayangannya sendiri yang mana yang lainn
.Pertama, dengan ghc-7.4.2, dikompilasi dengan
-O2
, versi non-memoised tidak terlalu buruk, daftar internal nomor Fibonacci masih dikompilasi untuk setiap panggilan tingkat atas ke fungsi tersebut. Tetapi ini tidak, dan tidak dapat secara masuk akal, dicatat di berbagai panggilan tingkat atas. Namun, untuk versi lainnya, daftar tersebut dibagikan ke semua panggilan.Itu karena pembatasan monomorfisme.
Yang pertama terikat oleh pengikatan pola sederhana (hanya nama, tidak ada argumen), oleh karena itu dengan pembatasan monomorfisme ia harus mendapatkan tipe monomorfik. Jenis yang disimpulkan adalah
dan batasan seperti itu menjadi default (jika tidak ada deklarasi default yang mengatakan sebaliknya) ke
Integer
, memperbaiki tipe sebagaiJadi, hanya ada satu daftar (jenis
[Integer]
) yang perlu diingat.Yang kedua didefinisikan dengan argumen fungsi, sehingga tetap polimorfik, dan jika daftar internal telah dimoisasi di seluruh panggilan, satu daftar harus dimoisasi untuk setiap tipe dalam
Num
. Itu tidak praktis.Kompilasi kedua versi dengan pembatasan monomorfisme dinonaktifkan, atau dengan jenis tanda tangan yang identik, dan keduanya menunjukkan perilaku yang persis sama. (Itu tidak benar untuk versi kompilator yang lebih lama, saya tidak tahu versi mana yang pertama kali melakukannya.)
sumber
fib 1000000
banyak tipe, itu memakan banyak memori. Untuk menghindarinya, seseorang akan membutuhkan heuristik yang mendaftar untuk membuang cache ketika itu tumbuh terlalu besar. Dan strategi memoisation seperti itu juga akan berlaku untuk fungsi atau nilai lain, mungkin, jadi kompilator harus berurusan dengan sejumlah besar hal yang berpotensi untuk dimoise untuk banyak tipe yang berpotensi. Saya pikir akan mungkin untuk mengimplementasikan memoisation (parsial) polimorfik dengan heuristik yang cukup baik, tapi saya ragu itu akan bermanfaat.Anda tidak perlu fungsi memoize untuk Haskell. Hanya bahasa pemrograman empiratif yang membutuhkan fungsi itu. Namun, Haskel adalah bahasa fungsional dan ...
Jadi, ini contoh algoritma Fibonacci yang sangat cepat:
zipWith adalah fungsi dari Prelude standar:
Uji:
Keluaran:
Waktu berlalu: 0,00018s
sumber