Saya mulai memahami bagaimana forallkata kunci digunakan dalam apa yang disebut "tipe eksistensial" seperti ini:

data ShowBox = forall s. Show s => SB s

Namun, ini hanya sebagian dari cara forallpenggunaannya dan saya tidak bisa menggunakan pikiran saya dalam hal-hal seperti ini:

runST :: forall a. (forall s. ST s a) -> a

Atau jelaskan mengapa ini berbeda:

foo :: (forall a. a -> a) -> (Char, Bool)
bar :: forall a. ((a -> a) -> (Char, Bool))

Atau semuanya RankNTypes...

Saya cenderung lebih memilih bahasa Inggris yang jelas dan bebas jargon daripada jenis bahasa yang normal di lingkungan akademik. Sebagian besar penjelasan yang saya coba baca tentang ini (yang dapat saya temukan melalui mesin pencari) memiliki masalah berikut:

1. Mereka tidak lengkap. Mereka menjelaskan satu bagian dari penggunaan kata kunci ini (seperti "tipe eksistensial") yang membuat saya merasa senang sampai saya membaca kode yang menggunakannya dengan cara yang sama sekali berbeda (seperti runST, foodan di baratas).
2. Mereka padat dengan asumsi bahwa saya telah membaca yang terbaru di cabang matematika diskrit, teori kategori atau aljabar abstrak apa pun yang populer minggu ini. (Jika saya tidak pernah membaca kata-kata "baca makalah apa pun untuk detail implementasi" lagi, itu akan terlalu cepat.)
3. Mereka ditulis dengan cara-cara yang sering mengubah konsep-konsep sederhana menjadi tata bahasa dan semantik yang terpelintir dan patah.

Begitu...

Aktif ke pertanyaan aktual. Adakah yang bisa sepenuhnya menjelaskan forallkata kunci dalam bahasa Inggris yang jelas dan sederhana (atau, jika ada di suatu tempat, tunjukkan penjelasan yang jelas yang saya lewatkan) yang tidak menganggap saya seorang ahli matematika yang menguasai jargon?

Diedit untuk menambahkan:

Ada dua jawaban menonjol dari yang berkualitas tinggi di bawah ini, tetapi sayangnya saya hanya dapat memilih satu sebagai yang terbaik. Jawaban Norman terperinci dan bermanfaat, menjelaskan berbagai hal dengan cara yang menunjukkan beberapa landasan teoretis foralldan pada saat yang sama menunjukkan kepada saya beberapa implikasi praktisnya. jawaban yairchumencakup area yang tidak disebutkan orang lain (variabel tipe cakupan) dan mengilustrasikan semua konsep dengan kode dan sesi GHCi. Apakah mungkin untuk memilih keduanya sebagai yang terbaik, saya akan melakukannya. Sayangnya saya tidak bisa dan, setelah memeriksa kedua jawaban dengan cermat, saya telah memutuskan bahwa yairchu sedikit keluar dari Norman karena kode ilustratif dan penjelasan terlampir. Ini agak tidak adil, karena saya benar-benar membutuhkan kedua jawaban untuk memahami ini sampai pada titik yang foralltidak meninggalkan saya dengan rasa takut yang samar ketika saya melihatnya dalam jenis tanda tangan.

Mari kita mulai dengan contoh kode:

foob :: forall a b. (b -> b) -> b -> (a -> b) -> Maybe a -> b
foob postProcess onNothin onJust mval =
    postProcess val
    where
        val :: b
        val = maybe onNothin onJust mval

Kode ini tidak dapat dikompilasi (kesalahan sintaks) di Haskell 98. Diperlukan ekstensi untuk mendukung forallkata kunci.

Pada dasarnya, ada 3 yang berbeda penggunaan umum untuk forallkata kunci (atau setidaknya sehingga tampaknya ), dan masing-masing memiliki ekstensi Haskell sendiri: ScopedTypeVariables, RankNTypes/ Rank2Types, ExistentialQuantification.

Kode di atas tidak mendapatkan kesalahan sintaks dengan salah satu yang diaktifkan, tetapi hanya ketik-cek dengan ScopedTypeVariablesdiaktifkan.

Variabel Jenis yang Dicakup:

Variabel tipe cakupan membantu seseorang menentukan tipe untuk kode di dalam whereklausa. Itu membuat bdi val :: bsatu sama seperti bdi foob :: forall a b. (b -> b) -> b -> (a -> b) -> Maybe a -> b.

Suatu titik yang membingungkan : Anda mungkin mendengar bahwa ketika Anda menghilangkan foralldari suatu jenis itu sebenarnya masih ada secara implisit. ( dari jawaban Norman: "biasanya bahasa-bahasa ini menghilangkan forall dari tipe polimorfik" ). Klaim ini benar, tetapi mengacu pada penggunaan lain dari forall, dan bukan pada ScopedTypeVariablespenggunaan.

Peringkat-N-Jenis:

Mari kita mulai dengan yang mayb :: b -> (a -> b) -> Maybe a -> bsetara dengan mayb :: forall a b. b -> (a -> b) -> Maybe a -> b, kecuali ketika ScopedTypeVariablesdiaktifkan.

Ini berarti bahwa ia bekerja untuk setiap adan b.

Katakanlah Anda ingin melakukan sesuatu seperti ini.

ghci> let putInList x = [x]
ghci> liftTup putInList (5, "Blah")
([5], ["Blah"])

Apa yang harus menjadi tipe ini liftTup? Ini liftTup :: (forall x. x -> f x) -> (a, b) -> (f a, f b). Untuk mengetahui alasannya, mari kita coba kode:

ghci> let liftTup liftFunc (a, b) = (liftFunc a, liftFunc b)
ghci> liftTup (\x -> [x]) (5, "Hello")
    No instance for (Num [Char])
    ...
ghci> -- huh?
ghci> :t liftTup
liftTup :: (t -> t1) -> (t, t) -> (t1, t1)

"Hmm .. mengapa GHC menyimpulkan bahwa tuple harus mengandung dua jenis yang sama? Katakan saja mereka tidak harus"

-- test.hs
liftTup :: (x -> f x) -> (a, b) -> (f a, f b)
liftTup liftFunc (t, v) = (liftFunc t, liftFunc v)

ghci> :l test.hs
    Couldnt match expected type 'x' against inferred type 'b'
    ...

Hmm. jadi di sini GHC tidak membiarkan kita menerapkan liftFuncpada vkarena v :: bdan liftFuncmenginginkan x. Kami benar-benar ingin fungsi kami mendapatkan fungsi yang menerima segala kemungkinan x!

{-# LANGUAGE RankNTypes #-}
liftTup :: (forall x. x -> f x) -> (a, b) -> (f a, f b)
liftTup liftFunc (t, v) = (liftFunc t, liftFunc v)

Jadi bukan liftTupitu yang bekerja untuk semua x, itu fungsi yang didapatnya yang berfungsi.

Kuantifikasi Eksistensial:

Mari kita gunakan sebuah contoh:

-- test.hs
{-# LANGUAGE ExistentialQuantification #-}
data EQList = forall a. EQList [a]
eqListLen :: EQList -> Int
eqListLen (EQList x) = length x

ghci> :l test.hs
ghci> eqListLen $ EQList ["Hello", "World"]
2

Apa bedanya dengan Tipe-N-Tipe?

ghci> :set -XRankNTypes
ghci> length (["Hello", "World"] :: forall a. [a])
    Couldnt match expected type 'a' against inferred type '[Char]'
    ...

Dengan Rank-N-Types, forall aberarti ekspresi Anda harus sesuai dengan semua yang mungkin a. Sebagai contoh:

ghci> length ([] :: forall a. [a])
0

Daftar kosong berfungsi sebagai daftar jenis apa pun.

Jadi dengan Existential-Quantification, foralls dalam datadefinisi berarti bahwa, nilai yang terkandung dapat dari jenis apa pun yang cocok, bukan harus dari semua jenis yang sesuai.

Adakah yang bisa sepenuhnya menjelaskan kata kunci forall dalam bahasa Inggris yang jelas dan sederhana?

Tidak. (Yah, mungkin Don Stewart bisa.)

Berikut adalah hambatan untuk penjelasan yang sederhana, jelas atau forall:

• Ini adalah penjumlah. Anda harus memiliki setidaknya sedikit logika (predikat kalkulus) untuk melihat penjumlah universal atau eksistensial. Jika Anda belum pernah melihat kalkulus predikat atau tidak nyaman dengan quantifiers (dan saya telah melihat siswa selama ujian kualifikasi PhD yang tidak nyaman), maka bagi Anda, tidak ada penjelasan yang mudah forall.

• Ini adalah tipe quantifier. Jika Anda belum melihat Sistem F dan berlatih menulis jenis polimorfik, Anda akan merasa forallbingung. Pengalaman dengan Haskell atau ML tidak cukup, karena biasanya bahasa-bahasa ini menghilangkan foralldari tipe polimorfik. (Menurut saya, ini adalah kesalahan desain bahasa.)

• Dalam Haskell khususnya, foralldigunakan dengan cara yang menurut saya membingungkan. (Saya bukan tipe teori, tetapi pekerjaan saya membuat saya berhubungan dengan banyak teori tipe, dan saya cukup nyaman dengan itu.) Bagi saya, sumber utama kebingungan adalah yang foralldigunakan untuk menyandikan tipe yang Saya sendiri lebih suka menulis exists. Itu dibenarkan oleh sedikit isomorfisme tipe rumit yang melibatkan penjumlah dan panah, dan setiap kali saya ingin memahaminya, saya harus mencari hal-hal dan mengerjakan sendiri isomorfisma.

  Jika Anda tidak nyaman dengan ide isomorfisma tipe, atau jika Anda tidak memiliki praktik memikirkan isomorfisma tipe, penggunaan forallini akan menghalangi Anda.

• Sementara konsep umum forallselalu sama (mengikat untuk memperkenalkan variabel tipe), detail penggunaan yang berbeda dapat sangat bervariasi. Bahasa Inggris Informal bukan alat yang sangat baik untuk menjelaskan variasi. Untuk benar-benar memahami apa yang terjadi, Anda perlu matematika. Dalam hal ini, matematika yang relevan dapat ditemukan dalam teks pengantar Benjamin Pierce Jenis dan Bahasa Pemrograman , yang merupakan buku yang sangat bagus.

Adapun contoh khusus Anda,

• runST harus membuat kepala Anda sakit. Jenis peringkat tinggi (terutama di sebelah kiri panah) jarang ditemukan di alam liar. Saya mendorong Anda untuk membaca makalah yang memperkenalkan runST: "Lazy Functional State Threads" . Ini adalah makalah yang sangat bagus, dan itu akan memberi Anda intuisi yang jauh lebih baik untuk tipe runSTtertentu dan untuk tipe peringkat yang lebih tinggi secara umum. Penjelasannya membutuhkan beberapa halaman, ini dilakukan dengan sangat baik, dan saya tidak akan mencoba untuk menyingkatnya di sini.

• Mempertimbangkan

  foo :: (forall a. a -> a) -> (Char,Bool)
  bar :: forall a. ((a -> a) -> (Char, Bool))

  Jika saya menelepon bar, saya bisa memilih jenis apa saja ayang saya suka, dan saya bisa meneruskannya dari jenis ake jenis a. Misalnya, saya bisa melewatkan fungsi (+1)atau fungsi reverse. Anda bisa memikirkanforall sebagai "Saya bisa memilih tipe sekarang". (Kata teknis untuk memilih jenis adalah instantiating .)

  Pembatasan pemanggilan foojauh lebih ketat: argumen untuk foo harus menjadi fungsi polimorfik. Dengan tipe itu, satu-satunya fungsi yang bisa saya lewati fooadalah idatau fungsi yang selalu menyimpang atau salah undefined. Alasannya adalah bahwa dengan foo, yang forallada di sebelah kiri dari panah, sehingga pemanggil foosaya tidak bisa memilih apa ayang-bukan itu adalah implementasi dari fooyang mendapat untuk memilih apa ayang. Karena forallberada di sebelah kiri panah, daripada di atas panah seperti pada bar, instantiasi terjadi di tubuh fungsi daripada di situs panggilan.

Ringkasan: Sebuah lengkap penjelasan tentang forallkata kunci membutuhkan matematika dan dapat dipahami hanya oleh seseorang yang telah mempelajari matematika. Bahkan penjelasan parsial sulit dimengerti tanpa matematika. Tapi mungkin sebagian, penjelasan non-matematika saya sedikit membantu. Bacalah Launchbury dan Peyton Jones di runST!

Tambahan: Jargon "di atas", "di bawah", "di sebelah kiri". Ini tidak ada hubungannya dengan cara tekstual jenis ditulis dan semuanya berkaitan dengan pohon sintaksis abstrak. Dalam sintaksis abstrak, a forallmengambil nama variabel tipe, dan kemudian ada tipe lengkap "di bawah" forall. Panah mengambil dua jenis (tipe argumen dan hasil) dan membentuk tipe baru (tipe fungsi). Jenis argumen adalah "di sebelah kiri" panah; itu adalah anak panah kiri di pohon abstrak-sintaksis.

Contoh:

• Dalam forall a . [a] -> [a], forall berada di atas panah; apa yang ada di sebelah kiri panah itu [a].

• Di

  forall n f e x . (forall e x . n e x -> f -> Fact x f) 
                -> Block n e x -> f -> Fact x f

  jenis dalam tanda kurung akan disebut "forall di sebelah kiri panah". (Saya menggunakan jenis seperti ini di pengoptimal yang sedang saya kerjakan.)

Jawaban asli saya:

Adakah yang bisa sepenuhnya menjelaskan kata kunci forall dalam bahasa Inggris yang jelas dan sederhana

Seperti yang ditunjukkan Norman, sangat sulit untuk memberikan penjelasan bahasa Inggris yang jelas dan jelas tentang istilah teknis dari teori jenis. Kita semua berusaha.

Hanya ada satu hal yang perlu diingat tentang 'forall': ia mengikat tipe ke beberapa cakupan . Setelah Anda memahami itu, semuanya cukup mudah. Ini setara dengan 'lambda' (atau bentuk 'biarkan') pada tingkat tipe - Norman Ramsey menggunakan gagasan "kiri" / "di atas" untuk menyampaikan konsep ruang lingkup yang sama ini dalam jawaban yang sangat bagus .

Sebagian besar penggunaan 'forall' sangat sederhana, dan Anda dapat menemukannya diperkenalkan di GHC Users Manual, S7.8 ., Khususnya S7.8.5 yang luar biasa pada bentuk bersarang 'forall'.

Di Haskell, kami biasanya meninggalkan binder untuk jenis, ketika jenis itu dikuantifikasi secara universal, seperti:

length :: forall a. [a] -> Int

setara dengan:

length :: [a] -> Int

Itu dia.

Karena Anda dapat mengikat variabel tipe sekarang ke beberapa ruang lingkup, Anda dapat memiliki cakupan selain tingkat atas (" dikuantifikasi secara universal "), seperti contoh pertama Anda, di mana variabel tipe hanya terlihat dalam struktur data. Ini memungkinkan untuk tipe tersembunyi (" tipe eksistensial "). Atau kita dapat memiliki nesting binding yang sewenang - wenang ("peringkat tipe N").

Untuk sangat memahami sistem tipe, Anda perlu mempelajari beberapa jargon. Itulah sifat ilmu komputer. Namun, penggunaan sederhana, seperti di atas, harus dapat dipahami secara intuitif, melalui analogi dengan 'let' pada tingkat nilai. Pengantar yang bagus adalah Launchbury dan Peyton Jones .

Mereka padat dengan asumsi bahwa saya telah membaca yang terbaru di cabang matematika diskrit, teori kategori atau aljabar abstrak apa pun yang populer minggu ini. (Jika saya tidak pernah membaca kata-kata "baca makalah apa pun untuk detail implementasi" lagi, itu akan terlalu cepat.)

Eh, dan bagaimana dengan logika first-order sederhana? forallcukup jelas dalam kaitannya dengan kuantifikasi universal , dan dalam konteks itu istilah eksistensial lebih masuk akal juga, meskipun akan kurang canggung jika ada existskata kunci. Apakah kuantifikasi efektif secara universal atau eksistensial tergantung pada penempatan kuantifier relatif terhadap tempat variabel digunakan di sisi mana dari panah fungsi dan itu semua agak membingungkan.

Jadi, jika itu tidak membantu, atau jika Anda tidak suka logika simbolik, dari perspektif pemrograman-ish yang lebih fungsional, Anda dapat menganggap variabel tipe hanya sebagai parameter tipe (implisit) ke fungsi. Fungsi yang mengambil parameter tipe dalam pengertian ini secara tradisional ditulis menggunakan huruf kapital lambda untuk alasan apa pun, yang akan saya tulis di sini sebagai/\ .

Jadi, pertimbangkan idfungsinya:

id :: forall a. a -> a
id x = x

Kita dapat menulis ulang sebagai lambdas, memindahkan "parameter tipe" dari tanda tangan tipe dan menambahkan anotasi tipe inline:

id = /\a -> (\x -> x) :: a -> a

Inilah hal yang sama dilakukan untuk const:

const = /\a b -> (\x y -> x) :: a -> b -> a

Jadi barfungsi Anda mungkin seperti ini:

bar = /\a -> (\f -> ('t', True)) :: (a -> a) -> (Char, Bool)

Perhatikan bahwa tipe fungsi yang diberikan barsebagai argumen tergantung pada barparameter tipe. Pertimbangkan jika Anda memiliki sesuatu seperti ini sebagai gantinya:

bar2 = /\a -> (\f -> (f 't', True)) :: (a -> a) -> (Char, Bool)

Di sini bar2adalah menerapkan fungsi untuk sesuatu tipe Char, jadi memberikan bar2parameter tipe apa pun selainChar akan menyebabkan kesalahan tipe.

Di sisi lain, inilah yang fooakan terlihat:

foo = (\f -> (f Char 't', f Bool True))

Tidak seperti itu bar, foosebenarnya tidak mengambil parameter tipe apa pun! Dibutuhkan fungsi yang sendiri mengambil parameter tipe, lalu menerapkan fungsi itu ke dua berbeda jenis.

Jadi, ketika Anda melihat foralltanda tangan tipe, anggap saja sebagai ekspresi lambda untuk tanda tangan tipe . Sama seperti foralllambda biasa, ruang lingkup meluas sejauh mungkin ke kanan, hingga melampirkan tanda kurung, dan sama seperti variabel terikat dalam lambda biasa, variabel tipe terikat oleh a forallhanya dalam lingkup dalam ekspresi terkuantifikasi.

Post scriptum : Mungkin Anda mungkin bertanya-tanya - sekarang kita sedang berpikir tentang fungsi yang mengambil parameter tipe, mengapa kita tidak bisa melakukan sesuatu yang lebih menarik dengan parameter itu daripada memasukkannya ke dalam tanda tangan tipe? Jawabannya adalah kita bisa!

Fungsi yang menempatkan variabel tipe bersama-sama dengan label dan mengembalikan tipe baru adalah konstruktor tipe , yang Anda bisa menulis sesuatu seperti ini:

Either = /\a b -> ...

Tetapi kita membutuhkan notasi yang sama sekali baru, karena cara penulisan jenis itu, seperti Either a b, sudah menyarankan "menerapkan fungsiEither ke parameter ini".

Di sisi lain, fungsi yang semacam "pola cocok" pada parameter tipe, mengembalikan nilai yang berbeda untuk tipe yang berbeda, adalah metode kelas tipe . Sedikit ekspansi ke /\sintaksis saya di atas menunjukkan sesuatu seperti ini:

fmap = /\ f a b -> case f of
    Maybe -> (\g x -> case x of
        Just y -> Just b g y
        Nothing -> Nothing b) :: (a -> b) -> Maybe a -> Maybe b
    [] -> (\g x -> case x of
        (y:ys) -> g y : fmap [] a b g ys 
        []     -> [] b) :: (a -> b) -> [a] -> [b]

Secara pribadi, saya pikir saya lebih suka sintaksis aktual Haskell ...

Suatu fungsi yang "pola cocok" dengan parameter tipenya dan mengembalikan tipe yang semau dan ada adalah tipe keluarga atau dependensi fungsional - dalam kasus sebelumnya, bahkan sudah sangat mirip dengan definisi fungsi.

Berikut adalah penjelasan cepat dan kotor dalam istilah sederhana yang kemungkinan besar sudah Anda kenal.

Kata forallkunci ini benar-benar hanya digunakan dalam satu cara di Haskell. Itu selalu berarti hal yang sama ketika Anda melihatnya.

Kuantifikasi universal

Sebuah jenis diukur secara universal adalah jenis formulir forall a. f a. Nilai tipe itu dapat dianggap sebagai fungsi yang mengambil tipe a sebagai argumennya dan mengembalikan nilai tipe f a. Kecuali bahwa dalam Haskell argumen tipe ini diteruskan secara implisit oleh sistem tipe. "Fungsi" ini harus memberi Anda nilai yang sama apa pun tipe yang diterimanya, sehingga nilainya polimorfik .

Misalnya, perhatikan tipenya forall a. [a]. Nilai tipe itu mengambil tipe lain adan memberi Anda kembali daftar elemen dari tipe yang samaa . Hanya ada satu kemungkinan implementasi, tentu saja. Itu harus memberi Anda daftar kosong karenaa dapat benar-benar jenis apa pun. Daftar kosong adalah satu-satunya nilai daftar yang polimorfik dalam jenis elemennya (karena tidak memiliki elemen).

Atau tipenya forall a. a -> a. Penelepon dari fungsi semacam itu menyediakan tipe adan nilai tipe a. Implementasi kemudian harus mengembalikan nilai dari jenis yang sama a. Hanya ada satu kemungkinan implementasi lagi. Itu harus mengembalikan nilai yang sama seperti yang diberikan.

Kuantifikasi eksistensial

Sebuah jenis eksistensial dihitung akan memiliki bentuk exists a. f a, jika Haskell didukung notasi itu. Nilai jenis itu dapat dianggap sebagai pasangan (atau "produk") yang terdiri dari suatu jenis adan nilai jenisf a .

Misalnya, jika Anda memiliki nilai tipe exists a. [a], Anda memiliki daftar elemen tipe tertentu. Itu bisa berupa tipe apa saja, tetapi bahkan jika Anda tidak tahu apa itu, ada banyak hal yang dapat Anda lakukan untuk daftar seperti itu. Anda bisa membalikkannya, atau Anda bisa menghitung jumlah elemen, atau melakukan operasi daftar lainnya yang tidak bergantung pada jenis elemen.

OK, jadi tunggu sebentar. Mengapa Haskell menggunakan foralluntuk menunjukkan tipe "eksistensial" seperti berikut?

data ShowBox = forall s. Show s => SB s

Ini bisa membingungkan, tapi itu benar-benar menggambarkan tipe konstruktor data SB :

SB :: forall s. Show s => s -> ShowBox

Setelah dikonstruksi, Anda dapat menganggap nilai tipe ShowBoxterdiri dari dua hal. Ini adalah tipe sbersama dengan nilai tipe s. Dengan kata lain, ini adalah nilai dari tipe yang dikuantifikasi secara eksistensial. ShowBoxdapat benar-benar ditulis sebagai exists s. Show s => s, jika Haskell mendukung notasi itu.

runST dan teman-teman

Mengingat itu, bagaimana perbedaannya?

foo :: (forall a. a -> a) -> (Char,Bool)
bar :: forall a. ((a -> a) -> (Char, Bool))

Mari kita ambil bar. Dibutuhkan jenis adan fungsi tipe a -> a, dan menghasilkan nilai tipe (Char, Bool). Kita bisa memilih Intsebagai adan memberikan fungsi tipe Int -> Intmisalnya. Tetapi fooberbeda. Ini membutuhkan implementasi fooagar dapat melewati semua jenis yang diinginkannya ke fungsi yang kita berikan. Jadi satu-satunya fungsi yang bisa kita berikan adalah id.

Kita sekarang harus dapat menangani arti dari jenis runST:

runST :: forall a. (forall s. ST s a) -> a

Jadi runSTharus dapat menghasilkan nilai tipe a, apa pun tipe yang kita berikan a. Untuk melakukannya, ia menggunakan argumen tipe forall s. ST s ayang pasti harus entah bagaimana menghasilkan a. Terlebih lagi, itu harus dapat menghasilkan nilai jenis atidak peduli apa jenis implementasi runSTmemutuskan untuk memberikans .

Oke, lalu bagaimana? Keuntungannya adalah bahwa hal ini membatasi penelepon runSTkarena jenisnya atidak dapat melibatkan jenis ssama sekali. Anda tidak dapat memberikan nilai tipe ST s [s], misalnya. Apa artinya itu dalam praktik adalah bahwa implementasi runSTbebas untuk melakukan mutasi dengan nilai tipe s. Jenis ini menjamin bahwa mutasi ini bersifat lokal untuk implementasi runST.

Tipe runSTadalah contoh tipe polimorfik peringkat-2 karena tipe argumennya berisi forallkuantifier. Tipe di fooatas juga dari peringkat 2. Tipe polimorfik biasa, seperti yang barada di peringkat, adalah peringkat-1, tetapi menjadi peringkat-2 jika jenis argumen diharuskan bersifat polimorfik, dengan forallpenjumlahannya sendiri . Dan jika suatu fungsi mengambil argumen peringkat-2 maka tipenya adalah peringkat-3, dan seterusnya. Secara umum, jenis yang mengambil argumen polimorfik peringkat nmemiliki peringkat n + 1.

Adakah yang bisa sepenuhnya menjelaskan kata kunci forall dalam bahasa Inggris yang jelas (atau, jika ada di suatu tempat, arahkan ke penjelasan yang jelas yang saya lewatkan) yang tidak menganggap saya ahli matematika yang menguasai jargon?

Saya akan mencoba dan menjelaskan arti dan mungkin penerapan foralldalam konteks Haskell dan sistem tipenya.

Tetapi sebelum Anda memahami bahwa saya ingin mengarahkan Anda ke sebuah pembicaraan yang sangat mudah diakses dan bagus oleh Runar Bjarnason berjudul " Kendala Pembebasan, Pembatasan Liberties ". Pembicaraan penuh dengan contoh dari kasus penggunaan dunia nyata serta contoh di Scala untuk mendukung pernyataan ini, meskipun tidak disebutkan forall. Saya akan mencoba menjelaskan forallperspektif di bawah ini.

                CONSTRAINTS LIBERATE, LIBERTIES CONSTRAIN

Sangat penting untuk mencerna dan meyakini pernyataan ini untuk melanjutkan dengan penjelasan berikut, jadi saya mendorong Anda untuk menonton ceramah (setidaknya sebagian darinya).

Sekarang contoh yang sangat umum, menunjukkan ekspresifitas sistem tipe Haskell adalah tipe signature ini:

foo :: a -> a

Dikatakan bahwa dengan jenis tanda tangan ini, hanya ada satu fungsi yang dapat memuaskan tipe ini dan itu adalah identityfungsi atau apa yang lebih dikenal.id .

Pada tahap awal saya belajar Haskell, saya selalu bertanya-tanya fungsi di bawah ini:

foo 5 = 6

foo True = False

mereka berdua memenuhi tanda tangan tipe di atas, lalu mengapa orang Haskell mengklaim itu id saja yang memenuhi tanda tangan tipe

Itu karena ada implisit foralltersembunyi dalam tipe tanda tangan. Jenis yang sebenarnya adalah:

id :: forall a. a -> a

Jadi, sekarang mari kita kembali ke pernyataan: Batasan membebaskan, kebebasan membatasi

Menerjemahkannya ke sistem tipe, pernyataan ini menjadi:

Batasan pada level type, menjadi kebebasan pada level term

dan

Kebebasan pada level tipe, menjadi kendala pada level term

Mari kita coba buktikan pernyataan pertama:

Batasan pada tingkat tipe ..

Jadi menempatkan batasan pada tanda tangan tipe kami

foo :: (Num a) => a -> a

menjadi kebebasan pada level istilah memberi kita kebebasan atau fleksibilitas untuk menulis semua ini

foo 5 = 6
foo 4 = 2
foo 7 = 9
...

Hal yang sama dapat diamati dengan membatasi adengan typeclass lain dll

Jadi sekarang apa jenis tanda tangan: foo :: (Num a) => a -> aditerjemahkan adalah:

∃a , st a -> a, ∀a ∈ Num

Ini dikenal sebagai kuantifikasi eksistensial, yang diterjemahkan menjadi ada beberapa contoh ayang fungsinya ketika diberi makan sesuatu jenisa mengembalikan sesuatu dari jenis yang sama, dan contoh-contoh itu semua milik himpunan Bilangan.

Karenanya kita dapat melihat menambahkan kendala (yang aseharusnya menjadi bagian dari himpunan Angka), membebaskan tingkat istilah untuk memiliki beberapa implementasi yang mungkin.

Sekarang sampai pada pernyataan kedua dan yang benar-benar membawa penjelasan tentang forall:

Kebebasan pada level tipe, menjadi kendala pada level term

Jadi sekarang mari kita lepaskan fungsi pada level type:

foo :: forall a. a -> a

Sekarang ini diterjemahkan menjadi:

∀a , a -> a

yang berarti bahwa implementasi tanda tangan jenis ini harus sedemikian rupa a -> a untuk semua keadaan.

Jadi sekarang ini mulai membatasi kita pada level term. Kami tidak bisa lagi menulis

foo 5 = 7

karena implementasi ini tidak akan memuaskan jika kita menempatkan asebagai Bool. abisa berupa a Charatau a [Char]atau tipe data khusus. Dalam semua keadaan itu harus mengembalikan sesuatu dari tipe yang sama. Kebebasan pada tingkat tipe ini adalah apa yang dikenal sebagai Kuantifikasi Universal dan satu-satunya fungsi yang dapat memuaskan ini

foo a = a

yang biasa dikenal dengan identityfungsi

Oleh karena itu foralladalah libertypada level tipe, yang tujuan sebenarnya adalah constrainlevel istilah untuk implementasi tertentu.

Alasan mengapa ada berbagai penggunaan kata kunci ini adalah bahwa kata kunci itu sebenarnya digunakan dalam setidaknya dua ekstensi sistem tipe yang berbeda: tipe peringkat lebih tinggi, dan eksistensial.

Mungkin lebih baik membaca dan memahami kedua hal itu secara terpisah, daripada mencoba untuk mendapatkan penjelasan mengapa 'forall' adalah bagian sintaksis yang tepat untuk keduanya sekaligus.

Bagaimana eksistensial eksistensial?

Dengan Existential-Quantification, foralls dalam datadefinisi berarti bahwa, nilai yang terkandung dapat dari jenis apa pun yang sesuai, bukan harus dari semua jenis yang sesuai. - jawaban yachiru

Penjelasan mengapa foralldalam datadefinisi bersifat isomorfik (exists a. a)(pseudo-Haskell) dapat ditemukan di wikibooks "Haskell / Existentially quantized types" .

Berikut ini adalah ringkasan singkat kata demi kata:

data T = forall a. MkT a -- an existential datatype
MkT :: forall a. a -> T -- the type of the existential constructor

Ketika pencocokan pola / mendekonstruksi MkT x, apa jenisnya x?

foo (MkT x) = ... -- -- what is the type of x?

xdapat berupa jenis apa saja (sebagaimana dinyatakan dalam forall), dan jenisnya adalah:

x :: exists a. a -- (pseudo-Haskell)

Oleh karena itu, berikut ini isomorfik:

data T = forall a. MkT a -- an existential datatype
data T = MkT (exists a. a) -- (pseudo-Haskell)

forall berarti forall

Penafsiran saya yang sederhana tentang semua ini, adalah " forallbenar-benar berarti 'untuk semua'". Perbedaan penting untuk dibuat adalah dampak forallpada definisi versus aplikasi fungsi .

A forallberarti definisi nilai atau fungsi harus polimorfik.

Jika hal yang didefinisikan adalah nilai polimorfik , maka itu berarti bahwa nilai tersebut harus valid untuk semua yang sesuaia , yang cukup ketat.

Jika hal yang didefinisikan adalah fungsi polimorfik , maka itu berarti bahwa fungsi tersebut harus valid untuk semua yang sesuai a, yang tidak membatasi karena hanya karena fungsi tersebut polimorfik tidak berarti parameter yang diterapkan harus polimorfik. Artinya, jika fungsi ini berlaku untuk semua a, maka sebaliknya setiap yang cocok adapat diterapkan ke fungsi. Namun, tipe parameter hanya dapat dipilih satu kali dalam definisi fungsi.

Jika a forallberada di dalam tipe parameter fungsi (yaitu, a Rank2Type) maka itu berarti parameter yang diterapkan harus benar - benar polimorfik, agar konsisten dengan gagasan definisiforall cara adalah polimorfik. Dalam hal ini, jenis parameter dapat dipilih lebih dari satu kali dalam definisi fungsi ( "dan dipilih oleh implementasi fungsi", seperti yang ditunjukkan oleh Norman )

Oleh karena itu, alasan mengapa datadefinisi eksistensial memungkinkan ada a adalah karena konstruktor data adalah fungsi polimorfik :

MkT :: forall a. a -> T

jenis MkT :: a -> *

Yang berarti apa pun adapat diterapkan ke fungsi. Berbeda dengan, katakanlah, nilai polimorfik :

valueT :: forall a. [a]

jenis valueT :: a

Yang berarti bahwa definisi valueT haruslah polimorfik. Dalam hal ini, valueTdapat didefinisikan sebagai daftar kosong []semua jenis.

[] :: [t]

Perbedaan

Meskipun makna untuk forallkonsisten ExistentialQuantificationdan RankNType, eksistensial memiliki perbedaan karena datakonstruktor dapat digunakan dalam pencocokan pola. Seperti yang didokumentasikan dalam panduan pengguna ghc :

Saat pencocokan pola, setiap pencocokan pola memperkenalkan tipe baru, berbeda, untuk setiap variabel tipe eksistensial. Tipe-tipe ini tidak dapat disatukan dengan tipe lain, juga tidak bisa lepas dari cakupan pencocokan pola.