Soru Haskell / GHC'deki forall sözcüğü ne yapar?


Nasıl anlamaya başladım forall anahtar kelime, "varoluşsal türler" olarak adlandırılır:

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

Ancak bu sadece bir alt kümedir. forall kullanılır ve aklımı bu gibi şeylerde kullanmam mümkün olmaz:

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

Veya bunların neden farklı olduğunu açıklayan:

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

Ya da bütün RankNTypes şey...

Akademik ortamlarda normal olan dil türlerinden ziyade, açık ve jargon içermeyen İngilizce'yi tercih etme eğilimindeyim. Bu konuda okumaya çalıştığım açıklamaların çoğunda (arama motorlarında bulabildiğim) bu problemler var:

  1. Tamamlanmamışlar. Bu anahtar sözcüğün (“varoluşsal tipler” gibi) kullanımının bir bölümünü açıklıyorlar. Bu, beni tamamen farklı bir şekilde kullanan kodları okuyana kadar beni mutlu ediyor. runST, foo ve bar ile elde edilmiş).
  2. Her biri farklı matematik dalının son dalını okuduğum varsayımlar, kategori teorisi veya soyut cebir bu hafta popülerdir. (Eğer kelimeleri hiç okumamış olsaydım "gazeteye danış her neyse Uygulama detayları için "tekrar, çok yakında olacak."
  3. Sık sık basit kavramları bile aşırı derecede bükülmüş ve parçalanmış dilbilgisi ve anlambilimine çeviren şekillerde yazılırlar.

Yani...

Asıl soruya. Herkes tamamen açıklayabilir mi forall açık, sade İngilizce (veya bir yerde var ise, özlediğim böyle net bir açıklamaya işaret eden) anahtar kelime, jargonun içine dizilmiş bir matematikçiyim.


Eklemek için düzenlenmiş:

Aşağıda daha yüksek kaliteli olanlardan iki ayrı cevap vardı, ancak maalesef yalnızca birini seçebiliyorum. Norman'ın cevabı bazı şeylerin teorik temellerini gösteren bir şekilde açıklamak, detaylı ve yararlı oldu forall ve aynı zamanda bana bunun bazı pratik etkilerini gösteriyor. yairchu'nun cevabı kimsenin bahsetmediği bir alanı kapsadı (kapsamlı değişkenler) ve kod ve GHCi oturumuyla tüm kavramları resmeder. Her ikisini de en iyi olarak seçmek mümkün olurdu. Maalesef yapamıyorum ve her iki cevabı da yakından inceledikten sonra yairchu'nun açıklayıcı kod ve ek açıklamadan dolayı Norman'ın dışına çıkmasına karar verdim. Ancak bu biraz haksızlık, çünkü bunu anlamak için her iki cevaba da ihtiyacım vardı. forall ben bir tip imzasıyla gördüğümde hafif bir korku duygusuyla beni bırakmaz.


251
2018-06-18 15:50


Menşei


Haskell wiki Bu konuda oldukça yeni başlayanlar gibi görünüyor. - jhegedus


Cevaplar:


Bir kod örneği ile başlayalım:

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

Bu kod düz Haskell 98'de derleme (söz dizimi hatası) derlemiyor. forall Anahtar kelime.

Temelde 3 tane var farklı yaygın kullanımları forall anahtar kelime (veya en azından bu yüzden görünüyor) ve her birinin kendi Haskell uzantısı vardır: ScopedTypeVariables, RankNTypes/Rank2Types, ExistentialQuantification.

Yukarıdaki kod, etkin olanlardan biriyle birlikte bir sözdizimi hatası almıyor, ancak yalnızca bunlarla yazıyor ScopedTypeVariablessağladı.

Kapsamlı Tip Değişkenler:

Kapsamlı tip değişkenler, içteki kod için türlerin belirtilmesine yardımcı olur where maddeleri. Yapar b içinde val :: b aynı olan b içinde foob :: forall a b. (b -> b) -> b -> (a -> b) -> Maybe a -> b.

Kafa karıştırıcı bir nokta: Bunu duyduğunuzda forall bir türden aslında orada hala örtülüdür. (Norman'ın yanıtından: "normal olarak bu diller, polimorfik türlerden forallları çıkarır"). Bu iddia doğru fakat diğer kullanımlarına atıfta bulunur forallve değil ScopedTypeVariables kullanın.

Rank-N-Tipleri:

Bununla başlayalım mayb :: b -> (a -> b) -> Maybe a -> b eşdeğerdir mayb :: forall a b. b -> (a -> b) -> Maybe a -> b, dışında ne zaman için ScopedTypeVariables etkin.

Bu, her şey için çalıştığı anlamına gelir a ve b.

Bunun gibi bir şey yapmak istediğini varsayalım.

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

Bunun türü ne olmalı liftTup? Onun liftTup :: (forall x. x -> f x) -> (a, b) -> (f a, f b). Nedenini görmek için şunu kodlamaya çalışalım:

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 .. neden GHC, tuple'ın aynı türden iki tane içermesi gerektiğini ortaya koyuyor?

-- 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. işte burada ghc başvurmamıza izin vermiyor liftFunc üzerinde v Çünkü v :: b ve liftFunc bir ister x. Fonksiyonumuzu mümkün olan herşeyi kabul eden bir fonksiyon almak istiyoruz. x!

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

Yani değil liftTup hepsi işe yarıyor xBu, onu aldığı işlevdir.

Varoluşsal Nicelik:

Bir örnek kullanalım:

-- 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

Bu Rank-N-Tiplerinden nasıl farklı?

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

Rank-N-Türleri ile forall a ifadenizin tüm olası uygun olması gerektiği anlamına gelir as. Örneğin:

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

Boş bir liste, herhangi bir türün bir listesi olarak çalışır.

Varoluşsal Nicelik ile, forallgünah data Tanımlar, içerdiği değer anlamına gelir kutu olmak herhangi uygun tip değil, o değil şart olmak herşey uygun tipler.


223
2018-06-18 17:44



Ve şimdi kod ile bir açıklama. Teşekkürler! Burada 2AM var, bu yüzden yarın bunu daha kapsamlı bir şekilde okumalıyım. Tartıldığın için teşekkürler. - JUST MY correct OPINION
Aslında sen ScopedTypeVariables olduğundan daha kötü görünüyor. Yazıyorsanız b -> (a -> b) -> Maybe a -> b Bu uzatma ile hala tam olarak eşdeğer olacaktır forall a b. b -> (a -> b) -> Maybe a -> b. Ancak, başvurmak isterseniz aynısı  b (ve dolaylı olarak nicelendirilmemiş) sonra Açıkça belirtilmiş sürümü yazmanız gerekiyor. Aksi takdirde, STV son derece müdahaleci bir uzantı olurdu. - nominolo
@nominolo: Ben demeden demek istemedim ScopedTypeVariablesve bunun kötü olduğunu düşünmüyorum. imho, programlama süreci için ve özellikle de Haskell yeni başlayanlar için çok yararlı bir araçtır ve bunun için minnettarım. - yairchu
Bu oldukça eski bir soru (ve cevap), ama varoluşsal türlerin GADT'leri kullanarak ifade edilebileceği gerçeğini yansıtmak için değere sahip olabilir. - dfeuer
Ben şahsen, varoluşsal notasyonu kendi deyimiyle GADT formuna çevirme anlamında açıklamak / anlamak daha kolay olduğunu düşünüyorum, ama aksi halde düşünmek kesinlikle özgürdür. - dfeuer


Herhangi biri olabilir tamamen Forall anahtar kelimesini açık, sade İngilizce olarak açıklar mısınız?

Yok hayır. (Belki de Don Stewart yapabilir.)

İşte basit, açık bir açıklamanın önündeki engeller veya forall:

  • Bu bir niceleyici. Evrensel ya da varoluşsal bir niceleyici görmüş olmak için en azından küçük bir mantığa sahip olmalısınız. Daha önce herhangi bir hesaplama hesabı görmediyseniz ya da niceleyicilerle rahat etmediyseniz (ve rahat olmayan doktora yeterlilik sınavları sırasında öğrencileri gördüm), o zaman sizin için kolay bir açıklama yoktur. forall.

  • Bu bir tip miktar belirleyici. Görmediyseniz Sistem F Polymorphic tiplerini yazarken bazı alıştırmalar buldunuz. forall kafa karıştırıcı. Haskell veya ML ile deneyim yeterli değildir, çünkü bu diller normal olarak forall Polimorfik tiplerden (Benim aklımda, bu bir dil tasarım hatasıdır.)

  • Özellikle Haskell'de forall kafa karıştırıcı bulduğum şekilde kullanılır. (Ben bir tip teorisyen değilim, ama işim bana bir çok tip teorisi ve bununla oldukça rahatım.) Benim için ana kafa karışıklığı kaynağı forallkendimle yazmayı tercih ettiğim bir türü kodlamak için kullanılır exists. Bu, niceleyici ve okları içeren zorlu tipte bir izomorfizm tarafından haklı çıkarılır ve bunu anlamak istediğimde herşeyi izleyip, izomorfizmi kendim halletmem gerekir.

    Eğer isomorphism türü konusunda rahat değilseniz ya da tip izomorfizmleri hakkında herhangi bir alıştırma yapmıyorsanız, bu kullanımı forall seni stymie edecek.

  • Genel kavram ise forall her zaman aynıdır (bir tip değişkeni tanıtmak için bağlayıcı), farklı kullanımların detayları önemli ölçüde değişebilir. Resmi olmayan İngilizce, varyasyonları açıklamak için çok iyi bir araç değildir. Neler olup bittiğini anlamak için biraz matematiğe ihtiyacınız var. Bu durumda ilgili matematik Benjamin Pierce'ın giriş metninde bulunabilir. Türler ve Programlama Dilleri, bu çok iyi bir kitap.

Özel örneklerine gelince,

  • runST  meli Başını incitmek. Daha yüksek dereceli tipler (bir okun solundaki forall), vahşi ortamda nadiren bulunur. Sunulan makaleyi okumanı tavsiye ederim runST: "Tembel Fonksiyonel Durum Konuları". Bu gerçekten iyi bir kâğıttır ve bu tür için çok daha iyi bir sezgi sağlayacaktır. runST özellikle ve daha yüksek dereceli türleri için genel olarak. Açıklama birkaç sayfa alıyor, çok iyi yapılmış ve burada yoğunlaşmaya çalışmıyorum.

  • Düşünmek

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

    Eğer ararsam bar, Herhangi bir türü seçebilirim a hoşuma gidiyor ve onu bir işlevden geçirebilirim a yazmak a. Örneğin, işlevi geçebilirim (+1) veya işlevi reverse. Düşünebilirsin forall "şimdi türünü seçiyorum" demişti. (Türü seçmek için teknik kelime başlatmasını.)

    Çağrıya getirilen kısıtlamalar foo çok daha katı: argüman foo  şart polimorfik bir işlev olmak. Bu tiple, geçebileceğim tek fonksiyon foo Hangi id veya her zaman ıraksayan veya hata yapan bir işlev undefined. Nedeni şu ki foo, forall arayanın solunda olduğu gibi okun solunda foo Ne almam a - daha doğrusu uygulama arasında foo ne almak için alır a olduğunu. Çünkü forall okun solunda değil, okun solunda barörnekleme, çağrı yerine, işlev gövdesinde gerçekleşir.

Özet: bir tamamlayınız açıklaması forall anahtar kelime matematiği gerektirir ve sadece matematiği okuyan biri tarafından anlaşılabilir. Kısmi açıklamaların bile matematik olmadan anlaşılması zor. Ama belki kısmi, matematiksel olmayan açıklamalarım biraz yardımcı olur. Git, Startbury ve Peyton Jones'u oku. runST!


Zeyilname: Jargon "yukarıda", "aşağıda", "solunda". Bunlarla hiçbir ilgisi yok metinseltürlerin yazımı ve soyut sözdizimi ağaçları ile ilgili her şey. Özet sözdiziminde, forall bir tür değişkeninin adını alır ve daha sonra forall'ın tam altında "aşağıda" bulunur. Bir ok iki tür alır (argüman ve sonuç türü) ve yeni bir tip oluşturur (fonksiyon tipi). Argüman türü, okun solundadır; Soyut sintaks ağacındaki okun sol çocuğudur.

Örnekler:

  • İçinde forall a . [a] -> [a], forall okun üstünde; okun solunda ne var [a].

  • İçinde

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

    Parantez içindeki türler "bir okun solunda bir forall" olarak adlandırılır. (Şu an üzerinde çalıştığım bir optimizatörde bunun türlerini kullanıyorum.)


104
2018-06-18 16:19



Aslında düşünmek zorunda kalmadan yukarıda / aşağıda / solda var. Ben bir dullardım, evet ama eski Daha önce bu şeyle güreşmek zorunda kalan dullard. (ASN.1 derleyicisini diğerleri arasında yazarak .;) Ancak, ek için teşekkürler. - JUST MY correct OPINION
@JUST teşekkürler ama ben kuşak için yazıyorum. Bunu düşünen birden fazla programcıya girdim forall a . [a] -> [a], forall okun solunda. - Norman Ramsey
Tamam, cevabınızı ayrıntılı olarak gözden geçiriyorum, şimdi, size, Norman'ın kalbimin altından teşekkür etmeliyim. Yüksek sesle bir tıklama ile pek çok şey gerçekleşti ve hala anlamadığım şeyler en azından benim olmadığımı fark ettim demek anlamak ve sadece geçecek forall Bu şartlarda, etkili bir şekilde, hat gürültüsü. Bağladığınız kağıda bakacağım (link için de teşekkürler!) Ve anlayabildiğim alan içinde olup olmadığına bakacağım. Kudos. - JUST MY correct OPINION
Sola baktım ve tam anlamıyla baktım. Bu yüzden "ayrıştırma ağacı" dedene kadar bana çok net değildi. - Paul Nathan
Pierce'in kitabının işaretçisine teşekkürler. Sistem F'nin çok net bir açıklaması var. Nedenini açıklıyor. exists hiç uygulanmadı. (Sistem F'nin bir parçası değil!) Haskell'de, Sistem F'nin bir kısmı örtülü olarak yapıldı, ancak forall Tamamen halı altında süpürülebilen şeylerden biri. Hindley-Milner ile başlamışlardı. forall örtük hale getirilmeli ve daha güçlü bir sisteme geçilmeli, FOL'un 'forall' ve 'varoluşları' üzerinde çalışmış ve orada durdu. - T_S_


Orijinal cevabım:

Forall anahtar sözcüğünü açık, sade İngilizcede tamamen açıklayan herkes olabilir mi?

Norman'ın belirttiği gibi, açık ve sade bir İngilizce açıklaması vermek çok zor. Tip teorisinden teknik terim. Hepimiz deniyoruz.

'Forall' hakkında hatırlamak için sadece bir şey var: türlerini bağlar bazı kapsam. Bunu anladıktan sonra, her şey oldukça kolaydır. O tip seviyesinde 'lambda' (veya 'let' formunun bir karşılığı) - Norman Ramsey aynı kapsamdaki kavramını aktarmak için "sol" / "yukarıdaki" kavramını kullanır. onun mükemmel cevap.

'Forall' ın çoğu kullanımı çok basittir ve bunları tanıtımı yapabilirsiniz. GHC Kullanıcı Kılavuzu, S7.8., özellikle mükemmel S7.8.5 iç içe 'forall' biçimleri.

Haskell'de, genellikle türler için bağlayıcı türünü bırakırız evrensel olarak quanitified, öyle ki:

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

eşdeğerdir:

length :: [a] -> Int

Bu kadar.

Artık tür değişkenlerini bazı kapsamlara bağlayabildiğinizden, diğer kapsamlara sahip olabilirsiniz. en üst seviyeden ("evrensel olarak ölçülmüş"), ilk örneğiniz gibi tip değişkeni sadece veri yapısı içinde görülebilir. Bu izin verir gizli tipler için ("varoluşsal türler") Veya sahip olabiliriz keyfi yuvalama bağlamaların ("sıra N türleri").

Tip sistemlerini derinlemesine anlamak için, bazı jargonları öğrenmeniz gerekecektir. budur bilgisayar bilimlerinin doğası. Ancak, yukarıdaki gibi basit kullanımlar Sezgisel olarak kavranabilir, değer seviyesinde 'izin' ile analoji yoluyla. bir harika tanıtım Launchbury ve Peyton Jones.


44
2018-06-18 18:02



teknik olarak, length :: forall a. [a] -> Int eşdeğer değildir length :: [a] -> Int ne zaman ScopedTypeVariables etkin. Ne zaman forall a. orada, etkiliyor length'ler where yan tümce (varsa) ve tür değişkenlerinin anlamını değiştirir a içinde. - yairchu
Aslında. ScopedTypeVariables, hikayeyi biraz karmaşıklaştırır. - Don Stewart
@DonStewart, "bazı kapsamlara türleri bağlar" şeklinde daha iyi ifade edilen "bazı değişkenlere tür değişkenlerini bağlar" şeklinde açıklayabilir misiniz? - Romildo


Her biri farklı matematik dalının son dalını okuduğum varsayımlar, kategori teorisi veya soyut cebir bu hafta popülerdir. ("Uygulama detayları için ne olursa olsun, gazeteye danış" kelimesini hiç okumadım, çok yakında olacak.)

Er ve basit birinci dereceden mantık ne olacak? forall oldukça açık bir şekilde evrensel nicelikve bu bağlamda terim varoluşsal Daha fazla mantıklıdır, ancak eğer bir exists Anahtar kelime. Kantifikasyonun etkili bir şekilde evrensel mi yoksa varoluşsal mı olduğu, nicelleştiricinin, değişkenlerin bir fonksiyon okunun hangi tarafında kullanıldığına ve biraz kafa karıştırıcıya göre yerleştirilmesine bağlıdır.

Yani, eğer bu yardımcı olmazsa, ya da sembolik mantığı sevmiyorsanız, daha işlevsel bir programlama-perspektifinden, tür değişkenlerini sadece varlık olarak düşünebilirsiniz (örtük) tip fonksiyona parametreler. Bu anlamda tip parametrelerini alan fonksiyonlar, her ne sebeple olursa olsun, burada yazacağım sermaye lambda kullanılarak geleneksel olarak yazılır. /\.

Yani, düşünün id fonksiyon:

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

Bunu, lambda olarak yeniden yazabiliriz, "type parametresini" tip imzanın dışına taşıyarak satır içi tip ek açıklamaları ekleyebiliriz:

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

İşte aynı şey için yapıldı const:

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

Yani senin bar işlev böyle bir şey olabilir:

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

Verilen işlevin türüne dikkat edin. bar bir argüman olarak bağlıdır bartür parametresi. Bunun gibi bir şeyiniz varsa düşünün:

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

İşte bar2 işlevi türden bir şeye uygular Char, o zaman bar2 dışında herhangi bir tip parametresi Char bir tür hataya neden olur.

Öte yandan, işte ne foo benzeyebilir:

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

aksine bar, foo aslında herhangi bir tip parametresi almaz! Bu bir işlevi alır kendisi bir tür parametresi alır, sonra bu işlevi ikiye uygular farklı türleri.

Yani bir gördüğün zaman forall bir tür imza olarak, sadece bir tip imzalar için lambda ifadesi. Sadece normal lambdalar gibi forall mümkün olduğu kadar sağa kadar, parantezin içine kadar uzanır ve normal lambdaya bağlı değişkenler gibi, forall sadece nicelenmiş ifade içinde kapsamı vardır.


Post senaryosu: Belki de merak edebilirsiniz - şimdi, tip parametrelerini alan fonksiyonlar hakkında düşünüyoruz, niçin bu parametrelerle daha ilginç bir şey yapamıyoruz, onları bir tip imzanın içine koymuyoruz? Cevap, yapabileceğimiz!

Tip değişkenleri bir etiketle birlikte koyan ve yeni bir tür döndüren bir işlev tip kurucuBöyle bir şey yazabilirsiniz:

Either = /\a b -> ...

Ama tamamen yeni bir gösterime ihtiyacımız var, çünkü böyle bir tip yazılır, Either a b, zaten "işlevi uygulamak Either bu parametrelere ".

Öte yandan, farklı tipler için farklı değerler döndürerek, tür parametrelerine göre "örüntü eşleşmesi" türünde bir işlev, tip sınıfı metodu. Benim için biraz genişleme /\ Yukarıdaki sözdizimi böyle bir şey önerir:

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]

Şahsen, sanırım Haskell'in gerçek sözdizimini tercih ediyorum ...

"Desen" tür parametrelerini eşleştiren ve rastgele döndüren bir işlev, varolan bir türdür. aile tipi veya işlevsel bağımlılık- eski durumda, zaten bir işlev tanımı gibi büyük bir şey görünüyor.


25
2018-06-18 16:56



Burada ilginç bir şey. Bu bana, uzun vadede verimli olduğunu kanıtlayabilen sorunlara bir başka saldırı açısı veriyor. Teşekkürler. - JUST MY correct OPINION
@KennyTM: Veya λ Bu konuda, ancak GHC'nin unicode sözdizimi uzantısı bunu desteklemiyor çünkü λ bir harfvarsayımsal olarak varsayımsal büyük lambda soyutlamalarına da hipotetik olarak uygulanacak olan talihsiz bir gerçektir. bundan dolayı /\  analoji ile \ . Sanırım yeni kullanmış olabilirim. ∀ ama hesaplamaktan kaçınmaya çalışıyordum ... - C. A. McCann


Burada, zaten aşina olduğunuz muhtemel, hızlı ve kirli bir açıklama.

forall anahtar kelime gerçekten sadece Haskell'de bir şekilde kullanılır. Gördüğünüz zaman her zaman aynı şey anlamına gelir.

Evrensel kantifikasyon

bir evrensel olarak ölçülmüş tip formun bir türüdür forall a. f a. Bu tür bir değer olarak düşünülebilir bir işlev bu bir alır tip  a argüman olarak ve bir değer türü f a. Haskell dışında bu tür argümanlar, tip sistem tarafından dolaylı olarak aktarılır. Bu "işlev", hangi türden olursa olsun size aynı değeri vermek zorundadır, bu yüzden değer polimorfik.

Örneğin, türü düşünün forall a. [a]. Bu tür bir değer başka türde alır a ve aynı türde öğelerin listesini verir a. Elbette sadece tek bir uygulama var. Sana boş listeyi vermek zorunda kalacaktı çünkü a kesinlikle herhangi bir tip olabilir. Boş liste, eleman türünde polimorfik olan tek liste değeridir (öğe içermediği için).

Veya türü forall a. a -> a. Böyle bir işlevin arayıcısı hem bir tür sağlar a ve bir değer türü a. Uygulama daha sonra aynı türde bir değer döndürmek zorundadır. a. Yine tek bir uygulama var. Verildiği değere dönmek zorunda kalacaktı.

Varoluşsal nicelendirme

bir varoluşsal olarak nicelenmiş tip formu olurdu exists a. f aeğer Haskell bu notasyonu destekliyorsa. Bu tür bir değer olarak düşünülebilir bir çift (veya bir "ürün") bir türden oluşur a ve bir değer türü f a.

Örneğin, bir tür değeriniz varsa exists a. [a], bazı tür öğelerin bir listesi var. Herhangi bir tip olabilir, ama ne olduğunu bilmiyor olsanız bile, böyle bir listeye yapabileceğiniz çok şey var. Bunu tersine çevirebilir veya elemanların sayısını sayabilir veya öğelerin türüne bağlı olmayan başka bir liste işlemi gerçekleştirebilirsiniz.

Tamam, bir dakika bekle. Haskell neden kullanıyor? forall Aşağıdaki gibi bir "varoluşsal" türü belirtmek için?

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

Kafa karıştırıcı olabilir, ama gerçekten veri kurucusunun türü  SB:

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

Yapıldıktan sonra, bir tür değeri düşünebilirsiniz ShowBox iki şeyden oluşuyordu. Bu bir tip s tip değeri ile birlikte s. Başka bir deyişle, varoluşsal olarak nicelenmiş bir türün değeridir. ShowBox gerçekten yazılabilir exists s. Show s => seğer Haskell bu notasyonu destekliyorsa.

runST ve arkadaşlar

Verilenler, bunlar nasıl farklı?

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

İlk alalım bar. Bir tür alır a ve bir işlev türü a -> ave tür bir değer üretir (Char, Bool). Biz seçebiliriz Int olarak a ve ona bir işlev ver Int -> Int Örneğin. Fakat foo farklı. Uygulanması gerektirir foo Verdiğimiz işleve istediği herhangi bir türden geçebilir. Yani makul bir şekilde verebileceğimiz tek fonksiyon id.

Şimdi türünün anlamını çözebilmeliyiz. runST:

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

Yani runST bir tür değer üretebilmelidir ane tür verdiğimiz önemli değil a. Bunu yapmak için, bir tür argümanına ihtiyaç duyar forall s. ST s a kaputun altında sadece tip bir işlevi forall s. s -> (a, s). Bu işlev, daha sonra bir tür değeri üretebilmelidir (a, s) ne tür bir uygulama olursa olsun runST olarak vermeye karar verir s.

Tamam, peki? Yararı, bu arayan arayan için bir kısıtlama koyar runST bu tipte a türü içeremez s hiç Bunu bir değerden geçiremezsin ST s [s], Örneğin. Pratikte bunun anlamı, uygulamanın runST tip değeri ile mutasyon yapmakta serbesttir s. Tip sistem, bu mutasyonun uygulanmasının yerel olduğunu garanti eder. runST.

Türü runST bir örneğidir rank-2 polimorfik tip çünkü argümanının türü bir forall miktar belirleyici. Türü foo yukarıda da 2. sıradadır. Sıradan bir polimorfik tip, bar, rank-1'dir, ancak argüman türlerinin polimorfik olması gerekiyorsa, sırayla-2 olur. forall miktar belirleyici. Ve eğer bir fonksiyon rütbe-2 argümanları alırsa, o zaman onun tipi sıra-3'tür, vb. Genelde, sıralamanın polimorfik argümanlarını alan bir tür n sırada n + 1.


20
2018-03-16 18:12





Bu anahtar kelimenin farklı kullanımlarının nedeni, aslında en az iki farklı türde sistem uzantısında kullanılması: yüksek sıralı türler ve varoluşçular.

Muhtemelen bu iki şeyi ayrı ayrı okumak ve anlamak için en iyisi, 'forall' 'ın neden aynı anda hem sözdizimsel bir sözdizimi olduğu konusunda bir açıklama yapmaya çalışmaktır.


8
2018-06-18 17:26





Forall anahtar sözcüğünü açık, sade bir İngilizcede (veya bir yerde varsa, özlediğim açık bir açıklamaya işaret eder) herkes jargonun içine dizilmiş bir matematikçi olduğumu varsaymaz mı?

Sadece anlamını ve belki de uygulamasını açıklamaya çalışacağım forall Haskell ve tip sistemleri bağlamında.

Ama anladığınızdan önce, sizi Runar Bjarnason'un çok erişilebilir ve güzel bir konuşmasına yönlendirmek istediğimi anlatan "Kısıtlamalar Liberate, Özgürlükler Kısıtlama". Konuşma, gerçek dünyadaki kullanım örneklerinden örnekler ve Scala'da bu ifadeyi desteklemek için örneklerle dolu. forall. Açıklamaya çalışacağım forall perspektif aşağıda.

                CONSTRAINTS LIBERATE, LIBERTIES CONSTRAIN

Bu açıklamayı sindirmek ve bu açıklamaya aşağıdaki açıklamalarla devam etmek için inanması çok önemlidir, bu yüzden konuşmayı izlemenizi tavsiye ederim (en azından bir kısmı).

Şimdi, Haskell tipi sistemin ifadesini gösteren çok yaygın bir örnek, bu tür imzadır:

foo :: a -> a

Bu tip imza verildiğinde, bu tipte tatmin edebilecek tek bir fonksiyon olduğu söylenir. identity fonksiyon veya daha popüler bilinen nedir id.

Haskell'i öğrenmenin başlangıç ​​aşamalarında, her zaman aşağıdaki işlevleri merak ettim:

foo 5 = 6

foo True = False

Her ikisi de yukarıdaki tip imzayı yerine getiriyorlar, o zaman neden Haskell millet bunun olduğunu iddia ediyor idtek başına tip imzayı tatmin eder?

Çünkü bir örtülü var forall tip imzasında saklı. Gerçek tip:

id :: forall a. a -> a

Şimdi, şimdi açıklamaya geri dönelim: Kısıtlamalar özgürleşir, özgürlükler sınırlanır

Bunu tür sistemine tercüme ederek, bu ifade şöyle olur:

Tip seviyesinde bir kısıtlama, dönem seviyesinde bir özgürlük haline gelir

ve

Tür düzeyinde bir özgürlük, terim düzeyinde bir kısıtlama haline gelir


İlk ifadeyi kanıtlamaya çalışalım:

Tip seviyesinde bir kısıtlama ..

Bu nedenle, tür imzamıza bir kısıtlama koymak

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

dönem düzeyinde bir özgürlük haline gelir Bütün bunları yazabilmemiz için özgürlük ya da esneklik verir.

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

Aynı kısıtlama ile gözlemlenebilir a başka bir typeclass vb ile

Şimdi bu tip imza ne: foo :: (Num a) => a -> a çevirir:

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

Bu, varoluşsal nicelik olarak bilinir, var var bazı örnekleri a tür bir şey beslendiğinde bir işlev için a aynı türden bir şey döndürür ve bu örneklerin hepsi Sayılar kümesine aittir.

Dolayısıyla bir kısıtlama ekleyebiliriz ( a Sayı kümesine ait olmalıdır), mümkün olan çoklu uygulamalara sahip olmak için terim seviyesini serbest bırakır.


Şimdi ikinci ifadeye geliyor ve aslında forall:

Tür düzeyinde bir özgürlük, terim düzeyinde bir kısıtlama haline gelir

Şimdi şimdi işlevi tür düzeyinde serbest bırakalım:

foo :: forall a. a -> a

Şimdi bu çevirir:

∀a , a -> a

Bu, bu tip imzanın uygulanmasının öyle olması gerektiği anlamına gelir. a -> a tüm durumlar için.

Yani şimdi bu bizi dönem düzeyinde kısıtlamaya başlıyor. Artık yazamayız

foo 5 = 7

çünkü bu uygulama koyarsak tatmin olmaz a olarak Bool. a Olabilir Char ya da [Char] veya özel bir veri türü. Her koşulda benzer türde bir şey döndürmelidir. Tip seviyesindeki bu özgürlük, Evrensel Niceleme olarak bilinen şeydir ve bunu tatmin edebilen tek işlevdir.

foo a = a

yaygın olarak bilinen identity fonksiyon


bundan dolayı forall bir liberty asıl amacı olan tip seviyesinde constrain Belirli bir uygulama için seviye terim.


3
2017-10-19 00:35





Varoluşsal varoluşsal nasıldır?

Varoluşsal Nicelik ile, forallgünah data tanımlar   bu, içerdiği değer kutu olmak herhangi uygun tip değil   bu o şart olmak herşey uygun tipler.   - yachiru'nun cevabı

Neden bir açıklama forall içinde data tanımları izomorf (exists a. a) (sözde Haskell) bulunabilir wikibooks'un "Haskell / Existentially quantified types".

Aşağıdaki kısa bir özet özetidir:

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

Kalıp eşleşmesi / deconstructing MkT x, ne türü x?

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

x herhangi bir tip olabilir ( forall), ve bu yüzden türü:

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

Bu nedenle, aşağıdaki izomorfiktir:

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

Forall anlamına gelir

Bütün bunları basit bir şekilde yorumladım "forallgerçekten 'herkes için' anlamına gelir. Yapılması önemli bir ayrımın etkisi forall üzerinde tanım karşı işlev uygulama.

bir forall anlamına gelir tanım Değer veya fonksiyonun polimorf olması gerekir.

Tanımlanan şey bir polimorfik ise değero zaman bu değer uygun olan her şey için geçerli olması gerektiği anlamına gelir aoldukça kısıtlayıcı.

Tanımlanan şey bir polimorfik ise fonksiyonDaha sonra, fonksiyonun tüm uygun olanlar için geçerli olması gerektiği anlamına gelir aBu kısıtlayıcı değil çünkü sadece fonksiyon polimorfik olduğu için parametrenin uygulamalı polimorfik olmak zorunda. Yani, işlev herkes için geçerliyse asonra tersi herhangi uygun a olabilir uygulamalı işlevine. Bununla birlikte, parametrenin tipi sadece işlev tanımında bir kez seçilebilir.

Eğer bir forall fonksiyon parametresinin tipindedir (örn. Rank2Type) o zaman demektir uygulamalı parametre olmalıdır gerçekten polimorfik, fikir ile tutarlı olmak forall anlamına geliyor tanım polimorfiktir. Bu durumda, parametrenin tipi fonksiyon tanımında bir defadan fazla seçilebilir (Norman tarafından işaret edildiği gibi "ve işlevin uygulanmasıyla seçilir")

Dolayısıyla, neden var olmanın nedeni data tanımlar sağlar herhangi  a çünkü veri yapıcı bir polimorfiktir fonksiyon:

MkT :: forall a. a -> T

tür MkT :: a -> *

Demek istediğin a fonksiyona uygulanabilir. Aksine, bir polimorfik değer:

valueT :: forall a. [a]

tür bir değer :: a

Bu demektir ki tanım ValueT polimorfik olmalıdır. Bu durumda, valueT boş liste olarak tanımlanabilir [] her türlü

[] :: [t]

farklılıklar

Anlamı olsa bile forall tutarlı ExistentialQuantification ve RankNTypevaroluşçulardan beri data kurucu desen eşlemede kullanılabilir. Belgelendiği gibi ghc kullanıcı kılavuzu:

Kalıp eşleştirmesi yapıldığında, her bir desen eşleşmesi, her varoluşsal tür değişkeni için yeni, farklı bir tür sunar. Bu tipler başka türlerle birleştirilemez, model eşleşmesinin kapsamından kaçamazlar.


2
2018-02-06 18:49