Pertanyaan Mengapa Haskell tidak menyediakan lipatan untuk Array satu dimensi?


Data.Array tidak menyediakan lipatan untuk Array mengetik.

Dalam Real World Haskell (bab 12), alasannya dikatakan demikian Arrays dapat dilipat dengan cara yang berbeda berdasarkan kebutuhan pemrogram:

Pertama-tama, ada beberapa jenis lipatan yang masuk akal. Kami mungkin masih ingin melipat lebih dari satu elemen, tetapi sekarang kami memiliki kemungkinan melipat baris atau kolom juga. Di atas ini, untuk elemen-pada-waktu-lipat, tidak ada lagi hanya dua urutan untuk traversal.

Bukankah ini benar Lists? Sangat umum untuk mewakili mis. matriks dengan multidimensional List, tetapi masih ada lipatan yang ditentukan untuk satu dimensi Lists.

Apa kehalusan yang aku rindukan? Apakah itu multidimensional Array cukup berbeda dari Array dari Arrays?

Edit: Hm, bahkan multidimensi array memiliki lipatan yang ditentukan, dalam bentuk contoh Data.Foldable. [0] Jadi bagaimana hal itu sesuai dengan kutipan Haskell Dunia Nyata?

[0] http://hackage.haskell.org/packages/archive/base/4.6.0.0/doc/html/Data-Foldable.html


5
2017-09-09 00:48


asal


Jawaban:


Karena Anda menyebutkan perbedaan antara "multidimensional" Array dan sebuah Array dari Arrays, yang akan mengilustrasikan pokoknya dengan baik, di samping perbandingan dengan daftar.

Lipat (dalam Foldable pengertian kelas) adalah operasi linier inheren, sama seperti daftar adalah struktur linear yang inheren; lipatan yang tepat sepenuhnya mencirikan daftar dengan mencocokkan konstruktornya satu-satu dengan argumennya foldr. Meskipun Anda dapat mendefinisikan fungsi seperti foldl juga, ada pilihan yang jelas dari lipatan kanonis standar.

Array tidak memiliki struktur transparan seperti itu yang dapat dicocokkan satu-untuk-satu dalam lipatan. Ini adalah tipe abstrak, dengan akses ke elemen individual yang disediakan oleh nilai indeks, yang dapat berupa tipe apa pun yang memiliki Ix contoh. Jadi tidak hanya tidak ada pilihan yang jelas untuk menerapkan lipatan, juga tidak ada struktur linier intrinsik. Itu memang terjadi itu Ix memungkinkan Anda menghitung berbagai indeks, tetapi ini lebih merupakan detail implementasi daripada yang lain.

Bagaimana dengan multidimensional Arrays? Mereka tidak benar-benar ada, seperti itu. Ix mendefinisikan contoh untuk tupel jenis yang juga merupakan contoh, dan jika Anda ingin memikirkan tupel seperti itu sebagai jenis indeks untuk "multidimensional" Array, lanjutkan! Tapi mereka masih tupel. Tentunya, Ix menempatkan beberapa tatanan linear pada tupel tersebut, tapi apa itu? Dapatkah Anda menemukan sesuatu di dokumentasi yang memberi tahu Anda?

Jadi, saya pikir kita dapat mengatakan bahwa lipat multidimensional Array menggunakan urutan yang ditentukan oleh Ix tidak bijaksana kecuali Anda tidak benar-benar peduli apa urutan Anda mendapatkan elemen.

Untuk sebuah Array dari ArrayDi sisi lain, hanya ada satu cara yang masuk akal untuk menggabungkannya, seperti daftar bertingkat: lipat setiap bagian dalam Array secara terpisah sesuai dengan urutan elemennya masing-masing, lalu lipat hasilnya masing-masing sesuai dengan bagian luarnya Arrayurutan elemen.


Sekarang, Anda mungkin cukup keberatan karena tidak ada perbedaan jenis antara satu dimensi dan multidimensi Arrays, dan yang pertama dapat diasumsikan memiliki susunan lipatan yang masuk akal berdasarkan pada Ix Misalnya, mengapa tidak menggunakan pemesanan itu secara default? Sudah ada fungsi yang mengembalikan elemen-elemen a Array dalam daftar, setelah semua.

Ternyata, perpustakaan itu sendiri akan setuju dengan Anda, karena itulah persisnya Foldable contohnya.


8
2017-09-09 04:05



Ada satu cara alami untuk melipat daftar, yaitu foldr. Perhatikan jenis konstruktor daftar:

(:) :: a -> [a] -> [a]
[]  :: [a]

Mengganti kejadian [a] dengan b, kami mendapatkan jenis ini:

f :: a -> b -> b
z :: b

Dan sekarang, tentu saja, jenisnya foldr didasarkan pada prinsip ini:

foldr :: (a -> b -> b) -> b -> [a] -> b

Jadi diberi semantik konstruksi / observasi daftar, foldr adalah yang paling alami. Anda dapat membaca jenisnya sebagai "beri tahu saya apa yang harus dilakukan dengan (:) dan apa yang harus dilakukan dengan [], dan saya akan menyingkirkan daftar untuk Anda. "

Array tidak memiliki properti ini; Anda membuat larik dari daftar asosiasi (Ix i => [(i,a)]), dan jenisnya tidak benar-benar mengekspos struktur rekursif: satu array tidak dibangun dari array lain melalui konstruktor rekursif sebagai daftar atau pohon akan.


4
2017-09-09 03:51