Mengapa Haskell tidak dapat menghindari evaluasi berulang tanpa pembatasan monomorfisme?

14

Saya baru saja selesai mempelajari Anda , mengatakan pada suatu hari, dan saya berusaha memahami Pembatasan Monomorphism, seperti yang dijelaskan oleh Haskell Wiki . Saya pikir saya mengerti bagaimana MR dapat mencegah evaluasi berulang, tetapi saya gagal melihat mengapa evaluasi berulang itu tidak dapat dihindari dengan cara yang jauh lebih mudah.

Contoh spesifik yang ada dalam pikiran saya adalah yang digunakan oleh wiki:

f xs = (len,len)
  where
    len = genericLength xs

dimana genericLengthtipe Num a => [b] -> a.

Jelas, genericLength xshanya perlu dihitung sekali untuk mengevaluasi (len,len), karena fungsinya sama dengan argumen yang sama. Dan kita tidak perlu melihat doa funtuk mengetahui hal itu. Jadi mengapa Haskell tidak dapat melakukan optimasi ini tanpa memperkenalkan aturan seperti MR?

Diskusi pada halaman wiki mengatakan kepada saya itu ada hubungannya dengan fakta bahwa itu Numadalah typeclass daripada jenis beton, tetapi meskipun demikian, seharusnya tidak jelas pada saat kompilasi bahwa fungsi murni akan mengembalikan nilai yang sama- -dan dengan demikian jenis konkrit yang sama dari Bil - ketika diberi argumen yang sama dua kali?

optimization haskell type-systems Ixrec
sumber

Jawaban:

11

Itu nama fungsi yang sama, dengan argumen yang sama, tetapi berpotensi menghasilkan tipe dan implementasi yang berbeda, karena itu polimorfik. Itu berarti jika dipanggil dalam konteks mengharapkan (Int, MyWeirdCustomNumType)tipe pengembalian, ia harus mengevaluasinya dua kali, karena implementasi (+)in Intbenar-benar berbeda dari implementasi (+)in MyWeirdCustomNumType. Anda perlu menjalankan kode yang berbeda secara fisik di beberapa titik.

Itu sebabnya yang penting Numadalah kelas tipe. Ini berarti Anda memiliki implementasi yang berbeda untuk tipe yang berbeda. Ini juga berarti jika fada di perpustakaan, ia tidak tahu pada waktu kompilasi tentang semua kombinasi jenis yang mungkin perlu dikembalikan.

Jadi, ya, Anda perlu melihat permintaan funtuk mengetahui jenis pengembalian yang digunakan. Sebagian besar waktu, Anda akan mengharapkan mereka untuk menjadi sama, itulah sebabnya mereka menempatkan pembatasan monomorfisme secara default. Itu dapat dimatikan untuk kesempatan-kesempatan langka ketika Anda tidak melakukannya. Dalam praktiknya, programmer tidak cenderung membiarkan situasi seperti ini untuk mengetik inferensi.

Karl Bielefeldt
sumber
Saya belum mempertimbangkan kemungkinan f [] :: (Int, Float). Sekarang masuk akal. Terima kasih.
Ixrec
1
It's the same function name, with the same arguments, but potentially different return types and implementations, because it's polymorphic.Saya pikir cara yang lebih baik untuk melihatnya adalah bahwa instance typeclass efektif argumen tambahan genericLengthdan kompiler tidak yakin itu argumen yang sama di kedua panggilan.
Doval
Pertanyaan sampingan yang cepat. Jika MonomorphismRestriction dimatikan, tetapi kemudian Anda melakukan sesuatu seperti a = uncurry (==) $ f [1, 2, 3]Apakah itu dapat mengoptimalkan situs panggilan itu untuk hanya memeriksa panjang [1, 2, 3]sekali? Jika demikian maka saya benar-benar bingung mengenai apa sebenarnya pembatasan monomorfisme yang membeli Anda, jika tidak maka mengapa tidak?
titik koma