Czy ktoś może całkowicie wyjaśnić słowo kluczowe forall w jasnym, prostym języku angielskim?

Nie.Może Don Stewart może.)

Oto bariery dla prostego, jasnego wyjaśnienia lub forall:

• To kwantyfikator. Musisz mieć przynajmniej trochę logiki (rachunek predykatów), aby zobaczyć kwantyfikator uniwersalny lub egzystencjalny. Jeśli nigdy nie widziałeś rachunku predykatów lub nie czujesz się komfortowo z kwantyfikatorami (I widziałem studentów podczas egzaminów doktoranckich, którzy nie są wygodne), to dla Ciebie nie ma łatwego wyjaśnienia forall.

• Jest to Typ kwantyfikator. Jeśli nie widziałeś systemu F i nauczyłeś się pisać typy polimorficzne, znajdziesz forall mylące. Doświadczenie z Haskell lub ML nie wystarcza, ponieważ normalnie języki te pomijają forall z typów polimorficznych. (Moim zdaniem jest to projekt językowy błąd.)

• W Haskell w szczególności, forall jest używany w sposób, który uważam za mylący. (Nie jestem teoretykiem typu, ale moja praca przynosi mi kontakt z partii teorii typu, i czuję się z tym całkiem komfortowo.) Dla mnie głównym źródłem zamieszania jest to, że forall jest używany do kodowania typu, który sam wolałbym napisać z exists. Uzasadnia to skomplikowany izomorfizm typu obejmujący kwantyfikatory i strzałki. za każdym razem, gdy chcę go zrozumieć, mam aby sprawdzić rzeczy i wypracować izomorfizm siebie.

  Jeśli nie czujesz się komfortowo z ideą izomorfizmu typu, lub jeśli nie masz żadnej praktyki myślenia o izomorfizmach typu, to użycie forall będzie cię zniechęcić.

• Chociaż ogólne pojęcie forall jest zawsze takie samo( wiąże się z wprowadzeniem zmiennej typu), szczegóły różnych zastosowań mogą się znacznie różnić. Nieformalny angielski nie jest zbyt dobrym narzędziem do wyjaśnienia różnic. Do naprawdę zrozum o co chodzi, potrzebujesz trochę matematyki. W tym przypadku odpowiednią matematykę można znaleźć w tekście wprowadzającym Benjamina Pierce ' a typy i języki programowania , który jest bardzo dobrą książką.

Jeśli chodzi o twoje konkretne przykłady,

• runST powinno cię boleć głowa. Typy wyższej rangi (forall na lewo od strzałki) są rzadko spotykane na wolności. Zachęcam do zapoznania się z artykułem, który wprowadził runST: "Lazy Functional State Threads". Jest to naprawdę dobry artykuł, który da ci znacznie lepszą intuicję dla typu runST w szczególności i dla typów wyższych rang w ogóle. Wyjaśnienie zajmuje kilka stron, jest bardzo dobrze zrobione, i nie będę próbował skondensować go tutaj.

• Rozważ

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

  Jeśli wywołam bar, mogę po prostu wybrać dowolny typ a, który mi się podoba, i mogę przekazać mu funkcję z type a do type a. Na przykład może przekazać funkcję (+1) lub funkcję reverse. Możesz myśleć o forall jako o powiedzeniu "teraz mogę wybrać typ". (Techniczne słowo określające typ to instantiating .)

  Ograniczenia wywołania foo są znacznie bardziej rygorystyczne: argument do foo musi być funkcją polimorficzną. W przypadku tego typu, jedynymi funkcjami, które mogę przekazać foo są id lub funkcja, która zawsze się rozchodzi lub błędy, jak undefined. Powodem jest to, że z foo, forall jest na lewo od strzałki, więc jako rozmówca foo nie mogę wybrać tego, czym jest a-raczej to implementacja {42]} z foo, która wybiera to, czym jest a. Ponieważ forall znajduje się na lewo od strzałki, A nie nad strzałką, jak w bar, instancjacja odbywa się w ciele funkcji, a nie w miejscu wywołania.

Podsumowanie: a pełne Wyjaśnienie słowa kluczowego forall wymaga matematyki i może być zrozumiałe tylko przez kogoś, kto studiował matematykę. Nawet częściowe wyjaśnienia są trudne do zrozumienia bez matematyki. Ale może moje częściowe, nie matematyczne wyjaśnienia trochę pomogą. Idź poczytać Launchbury i Peyton Jones na runST!

Dodatek: żargon "powyżej"," poniżej","na lewo od". Nie mają one nic wspólnego ze sposobami pisania typów tekstowych i wszystko, co ma związek z drzewami abstrakcyjno-składni. W składni abstrakcyjnej forall przyjmuje nazwę zmiennej typu, A następnie jest pełny Typ" poniżej " forall. Strzałka przyjmuje dwa typy (argument i typ wyniku) i tworzy nowy typ (typ funkcji). Typ argumentu jest" na lewo od " strzałki; jest lewym potomkiem strzałki w drzewie abstrakcyjnej składni.

Przykłady:

• W forall a . [a] -> [a], forall znajduje się nad strzałką; to, co znajduje się po lewej stronie strzałki, to [a].

• W

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

  Typ w nawiasach będzie nazywany " a forall po lewej stronie arrow". (Używam takich typów w optymalizatorze, nad którym pracuję.)

Moja oryginalna odpowiedź:

Czy ktoś może całkowicie wyjaśnić słowo kluczowe forall w jasnym, prostym języku angielskim

Jak wskazuje Norman, bardzo trudno jest dać jasne, proste angielskie Wyjaśnienie termin techniczny z teorii typów. Wszyscy się staramy.

Jest tylko jedna rzecz do zapamiętania o 'forall': wiąże typy z niektóre zakres . Kiedy to zrozumiesz, wszystko jest dość łatwe. Jest to odpowiednik 'lambda' (lub forma 'let') na poziomie typu-Norman Ramsey używa pojęcia"Left"/ "above", aby przekazać to samo pojęcie zakresu w jego doskonała odpowiedź .

Większość zastosowań 'forall' jest bardzo prosta i można je znaleźć w the GHC Users Manual, S7. 8., szczególnie doskonały S7.8. 5 na zagnieżdżonym formy "forall".

W Haskell zwykle zostawiamy spoiwo dla typów, gdy typ jest ogólnie rzecz biorąc, tak:

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

Jest równoważne do:

length :: [a] -> Int

Ponieważ możesz teraz powiązać zmienne typu z pewnym zakresem, możesz mieć zakresy inne niż najwyższy poziom (" "), jak w pierwszym przykładzie, gdzie zmienna typu jest widoczna tylko w strukturze danych. Pozwala to na dla typów ukrytych ("typy egzystencjalne"). Albo możemy mieć dowolne zagnieżdżanie wiązań ("rangi N typów").

Aby dogłębnie zrozumieć systemy typów, musisz nauczyć się żargonu. To natura informatyki. Jednak proste zastosowania, jak wyżej, powinny być możliwe do uchwycenia intuicyjnie, poprzez analogię z "let" na poziomie wartości. A wielkie Wprowadzenie To Launchbury i Peyton Jones.

Są gęsto wypełnione założeniami, które przeczytałem w najnowszych dziedzinach matematyki dyskretnej, teorii kategorii czy algebry abstrakcyjnej, które są popularne w tym tygodniu. (JeĹ "li Juĺľ nigdy nie przeczytam sĹ 'Ăłw" skonsultuj siÄ ™ z papierem po szczegóŠ'y realizacji", bÄ ™ dzie to za szybko.)

Więc, jeśli to nie pomaga, lub jeśli po prostu nie lubisz logiki symbolicznej, z bardziej funkcjonalnego punktu widzenia programowania można myśleć o zmiennych typu jako o byciu (implicit) wpisz parametry do funkcji. Funkcje przyjmujące parametry typu w tym sensie są tradycyjnie zapisywane za pomocą wielkiej lambda z jakiegokolwiek powodu, co napiszę tutaj jako /\.

Rozważmy więc id funkcję:

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

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

To samo zrobiono const:

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

Więc twoja bar funkcja może być coś takiego:

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

Zauważ, że typ funkcji podanej bar jako argument zależy od parametru typu bar. Zastanów się, czy zamiast tego masz coś takiego: {]}

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

Tutaj bar2 jest zastosowanie funkcji do czegoś typu Char, więc podanie bar2 dowolnego parametru typu innego niż Char spowoduje błąd typu.

Z drugiej strony, oto jak foo może wyglądać:

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

bar, foo Nie przyjmuje żadnego rodzaju parametry w ogóle! Przyjmuje funkcję, która sama pobiera parametr typu, a następnie stosuje tę funkcję do dwóch różnych typów.

Więc kiedy widzisz forall w podpisie typu, pomyśl o tym jako o wyrażeniu lambda dla podpisów typu. Podobnie jak zwykłe lambda, zakres forall rozciąga się tak daleko w prawo, jak to możliwe, aż do zamkniętego nawiasu, i tak jak zmienne związane w regularnej lambda, zmienne typu związane przez forall są tylko w zakres w wyrażeniu kwantyfikowanym.

Post scriptum: być może zastanawiasz się-teraz, gdy myślimy o funkcjach pobierających parametry typu, Dlaczego nie możemy zrobić czegoś bardziej interesującego z tymi parametrami niż umieścić je w podpisie typu? Odpowiedź jest taka, że możemy!

Funkcja, która umieszcza zmienne typu razem z etykietą i zwraca nowy typ, to Konstruktor typu , który można napisać coś w stylu to:

Either = /\a b -> ...

Ale potrzebujemy zupełnie nowej notacji, ponieważ sposób zapisu takiego typu, jak Either a b, sugeruje już "zastosuj funkcję Either do tych parametrów".

Z drugiej strony, funkcja, która rodzaj "wzorca dopasowuje" do swoich parametrów typu, zwracając różne wartości dla różnych typów, jest metodą klasy typu. Małe rozszerzenie mojej składni /\ powyżej sugeruje coś takiego:

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]

Osobiście myślę, że preferuj rzeczywistą składnię Haskella...

Funkcja, która "pattern dopasowuje" swoje parametry typu i zwraca dowolny, istniejący typ jest rodziną typów lub zależnością funkcyjną - w pierwszym przypadku nawet wygląda bardzo podobnie do definicji funkcji.

Oto szybkie i brudne wyjaśnienie w prostych słowach, które prawdopodobnie już znasz.

Słowo kluczowe forall jest tak naprawdę używane tylko w jeden sposób w Haskell. To zawsze oznacza to samo, kiedy to widzisz.

Kwantyfikacja uniwersalna

A typ Uniwersalny jest typem postaci forall a. f a. Wartość tego typu może być traktowana jako funkcja {[67] } przyjmująca Typ a jako argument i zwraca wartość typu f a. Z tym wyjątkiem, że w Haskell te argumenty typu są przekazywane domyślnie przez system typu. Ta "funkcja" musi dawać tę samą wartość bez względu na typ, który otrzymuje, więc wartość jest polimorficzna .

Na przykład, rozważmy typ forall a. [a]. Wartość tego typu pobiera inny typ a i zwraca listę elementów tego samego typu a. Jest oczywiście tylko jedna możliwa realizacja. To musiałoby dać ci pustą listę ponieważ a może być absolutnie każdy typ. Pusta lista jest jedyną wartością listy, która jest polimorficzna w swoim typie elementu (ponieważ nie ma elementów).

Lub typu forall a. a -> a. Wywołanie takiej funkcji zapewnia zarówno typ a, jak i wartość typu a. Implementacja musi zwrócić wartość tego samego typu a. Jest tylko jedna możliwa realizacja. Musiałby zwrócić tę samą wartość, którą otrzymał.

Egzystencjalny kwantyfikacja

Typkwantyfikowany egzystencjalnie miałby postać exists a. f a, gdyby Haskell wspierał tę notację. Wartość tego typu może być traktowana jako para (lub "produkt") składająca się z typu a i wartości typu f a.

Na przykład, jeśli masz wartość typu exists a. [a], masz listę elementów pewnego typu. Może to być dowolny typ, ale nawet jeśli nie wiesz, co to jest, Możesz wiele zrobić z taką listą. Mógłbyś odwróć go, możesz policzyć liczbę elementów lub wykonać dowolną inną operację na liście, która nie zależy od typu elementów.

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

To może być mylące, ale tak naprawdę opisuje typ konstruktora danych SB:

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

Po zbudowaniu można myśleć o wartości typu ShowBox jako składającej się z dwóch rzeczy. To typ s wraz z wartością typu s. Innymi słowy, jest to wartość typu kwantyfikowanego egzystencjalnie. ShowBox może być naprawdę zapisany jako exists s. Show s => s, jeśli Haskell poparł tę notację.

runST i przyjaciele

Biorąc pod uwagę to, czym się różnią?

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

Weźmy najpierw bar. Przyjmuje typ a i funkcję typu a -> a i tworzy wartość typu (Char, Bool). Możemy wybrać Int jako a i nadać mu funkcję typu Int -> Int dla przykład. Ale to co innego. Wymaga to, aby implementacja foo była w stanie przekazać dowolny typ, jaki chce do danej funkcji. Więc jedyną funkcją, którą możemy rozsądnie mu dać, jest id.

Powinniśmy teraz być w stanie zmierzyć się ze znaczeniem typu runST:

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

Więc runST musi być w stanie wytworzyć wartość typu a, bez względu na to, jaki typ podamy jako a. Aby to zrobić, potrzebuje argumentu typu forall s. ST s a, który pod maską jest tylko funkcją typu forall s. s -> (a, s). Funkcja ta musi być w stanie wytworzyć wartość typu (a, s) bez względu na to, jakiego typu implementacja runST zdecyduje się podać jako s.

Typ runST jest przykładem typu polimorficznego rank-2 , ponieważ Typ jego argumentu zawiera forall kwantyfikator. Typ foo powyżej również ma rangę 2. Zwykły Typ polimorficzny, podobnie jak bar, jest rangą-1, ale staje się rangą - 2, jeśli typy argumentów są wymagane, aby były polimorficzne, z własnym kwantyfikatorem forall. A jeśli funkcja przyjmuje argumenty rank-2, to jej Typ to ranga-3 i tak dalej. Ogólnie rzecz biorąc, typ, który przyjmuje argumenty polimorficzne rangi n ma rangę n + 1.

Powodem, dla którego istnieją różne zastosowania tego słowa kluczowego, jest to, że jest ono używane w co najmniej dwóch różnych rozszerzeniach systemu typów: typy wyższej rangi i existentials.

Najlepiej jest po prostu poczytać i zrozumieć te dwie rzeczy osobno, zamiast próbować uzyskać wyjaśnienie, dlaczego 'forall' jest odpowiednim fragmentem składni w obu naraz.

Czy ktoś może całkowicie wyjaśnić słowo kluczowe forall w jasnym, prostym języku angielskim (lub, jeśli gdzieś istnieje, wskazać tak jasne wyjaśnienie, które przeoczyłem), że nie zakłada, że jestem matematykiem przesiąkniętym żargonem?

Postaram się wyjaśnić tylko znaczenie i być może zastosowanie forall w kontekście Haskell i jego systemów typu.

Ale zanim zrozumiesz, że chciałbym skierować Cię na bardzo przystępną i miłą rozmowę przez Runar Bjarnason zatytułował " ograniczenia wyzwalają, wolności ograniczają ". Dyskusja jest pełna przykładów z rzeczywistych przypadków użycia, jak również przykładów w Scali na poparcie tego stwierdzenia, chociaż nie wspomina forall. Postaram się wyjaśnić perspektywę forall poniżej.

                CONSTRAINTS LIBERATE, LIBERTIES CONSTRAIN

Bardzo ważne jest, aby przetrawić i uwierzyć w to stwierdzenie, aby przejść do następującego wyjaśnienia, więc zachęcam do obejrzenia rozmowy(przynajmniej jej części).

Teraz bardzo powszechny przykład, w systemie Haskell ' a jest to typ sygnatury:

foo :: a -> a

Mówi się, że biorąc pod uwagę ten typ, istnieje tylko jedna funkcja, która może zaspokoić ten typ i jest to identity funkcja lub co jest bardziej znane id.

foo 5 = 6

foo True = False

Oba spełniają powyższą sygnaturę typu, to dlaczego ludzie Haskell twierdzą, że jest id sam, który spełnia podpis typu?

To dlatego, że w sygnaturze typu jest ukryty forall. Rzeczywisty typ to:

id :: forall a. a -> a

Tłumacząc to na system typów, to stwierdzenie staje się:

I

Wolność na poziomie typu, staje się ograniczenie na poziomie terminowym

ograniczenie na poziomie typu..

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

staje się wolnością na poziomie terminowym daje nam swobodę lub elastyczność, aby napisać wszystkie te [36]}

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

To samo można zaobserwować ograniczając a z innymi typeklasami itp

Więc teraz, co ten podpis typu: foo :: (Num a) => a -> a tłumaczy się na jest:

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

Jest to znane jako kwantyfikacja egzystencjalna, co tłumaczy się na istnieją niektóre instancje a, dla których funkcja, gdy karmiona czymś typu a zwraca coś tego samego typu, a wszystkie te instancje należą do zbioru liczb.

Stąd widzimy dodanie ograniczenia (które a powinno należeć do zbioru liczb), uwalnia termin poziom, aby miał wiele możliwych implementacji.

Teraz nadchodzi druga twierdzenie i to, które faktycznie zawiera wyjaśnienie forall:

w zależności od tego, która z tych wartości jest większa, można ją zmienić na inną.]}

Więc teraz uwolnijmy funkcję na poziomie typu:

foo :: forall a. a -> a

∀a , a -> a

foo 5 = 7

foo a = a

Jak egzystencjalny jest egzystencjalny?

Z Kwantyfikacją egzystencjalną, foralls W data definicje oznaczają że wartość zawarta może być dowolnego odpowiedniego typu, nie że tomusi być zwszystkich odpowiednich typów. -- odpowiedź yachiru

Poniżej znajduje się krótkie, dosłowne podsumowanie:

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

Kiedy dopasowujemy / dekonstruujemy MkT x, jaki jest typ x?

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

x może być dowolnym typem (jak podano w forall), a więc jest to typ:

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

Zatem następujące są izomorficzne:

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

Forall oznacza forall

A forall oznacza definicja wartości lub funkcji musi być polimorficzna.

Jeśli zdefiniowana rzecz jest polimorficzną wartością , to oznacza, że wartość musi być ważna dla wszystkich odpowiednich a, co jest dość restrykcyjne.

Jeśli zdefiniowana rzecz jest funkcją polimorficzną , to oznacza, że funkcja musi być ważna dla wszystkich odpowiednich a, co nie jest tak restrykcyjne, ponieważ tylko dlatego, że funkcja jest polimorficzna, nie oznacza, że parametr zastosowany musi być polimorficzny. Oznacza to, że jeśli funkcja jest ważna dla wszystkich a, to odwrotnie Dowolna odpowiednia a może być zastosowana do funkcji. Jednak typ parametru może być wybrany tylko raz w definicji funkcji.

Jeśli a forall znajduje się wewnątrz typu parametru funkcji (tj. a Rank2Type), to oznacza zastosowany parametr musi być prawdziwie polimorficzny, aby był zgodny z ideą forall oznacza, że definicja jest polimorficzna. W tym przypadku typ parametru może być wybrany więcej niż jeden raz w definicji funkcji ( "i jest wybierany przez implementację funkcji", jak wskazał Norman )

Dlatego powód, dla którego egzystencjalne data definicje pozwalają dowolne a jest, ponieważ konstruktor danych jest polimorficznym funkcja :

MkT :: forall a. a -> T

Rodzaj MkT :: a -> *

Co oznacza, że dowolna a może być zastosowana do funkcji. W przeciwieństwie do, powiedzmy, polimorficznej wartości :

valueT :: forall a. [a]

Rodzaj wartości :: a

Co oznacza, że definicja valueT musi być polimorficzna. W tym przypadku {[31] } można zdefiniować jako pustą listę [] wszystkich typów.

[] :: [t]

Różnice

Mimo że znaczenie dla forall jest spójne w ExistentialQuantification i RankNType, existentials ma różnicę, ponieważ konstruktor data może być używany w dopasowywaniu wzorców. Jak udokumentowano w ghc user guide:

Gdy dopasowanie wzorca, każde dopasowanie wzorca wprowadza nowy, odrębny typ dla każdej zmiennej typu egzystencjalnego. Typy te nie mogą być unifikowane z żadnym innym typem, ani nie mogą uciec od zakresu dopasowania wzorca.