O que a palavra-chave `forall` no Haskell / GHC faz?

312

Estou começando a entender como a forallpalavra-chave é usada nos chamados "tipos existenciais" como este:

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

Este é apenas um subconjunto, no entanto, de como forallé usado e eu simplesmente não consigo entender meu uso em coisas como esta:

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

Ou explicando por que são diferentes:

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

Ou o RankNTypesmaterial todo ...

Eu tendem a preferir um inglês claro e sem jargões, em vez dos tipos de idioma normais em ambientes acadêmicos. A maioria das explicações que tento ler sobre isso (as que posso encontrar nos mecanismos de pesquisa) tem esses problemas:

  1. Eles estão incompletos. Eles explicam uma parte do uso desta palavra-chave (como "tipos existenciais") que me faz sentir feliz até que eu ler o código que usa-lo em uma maneira completamente diferente (como runST, fooe baracima).
  2. Eles estão densamente repletos de suposições que eu li sobre o que há de mais recente em qualquer ramo da matemática discreta, teoria das categorias ou álgebra abstrata que é popular nesta semana. (Se eu nunca mais ler as palavras "consulte o documento, para maiores detalhes sobre a implementação", será muito cedo.)
  3. Eles são escritos de maneiras que frequentemente transformam conceitos simples em gramática e semântica tortuosamente distorcidas e fraturadas.

Assim...

Para a questão real. Alguém pode explicar completamente a forallpalavra - chave em inglês claro e claro (ou, se existir em algum lugar, apontar para uma explicação tão clara que eu perdi) que não presuma que eu sou um matemático mergulhado no jargão?


Editado para adicionar:

Havia duas respostas destacadas das de alta qualidade abaixo, mas infelizmente só posso escolher uma como a melhor. A resposta de Norman foi detalhada e útil, explicando as coisas de uma maneira que mostrava algumas das bases teóricas foralle, ao mesmo tempo, mostrando-me algumas das implicações práticas dela. resposta de yairchucobriu uma área que ninguém mais mencionou (variáveis ​​de tipo com escopo definido) e ilustrou todos os conceitos com código e uma sessão do GHCi. Se fosse possível selecionar os dois da melhor maneira, eu selecionaria. Infelizmente, não posso e, depois de examinar atentamente as duas respostas, decidi que o yairchu fica um pouco mais afastado do Norman por causa do código ilustrativo e da explicação anexa. Isso é um pouco injusto, no entanto, porque realmente eu precisava das duas respostas para entender isso a tal ponto que forallnão me deixa com um leve senso de pavor quando a vejo em uma assinatura de tipo.

APENAS MINHA OPINIÃO correta
fonte
7
O wiki de Haskell parece ser bastante amigável para iniciantes neste tópico.
jhegedus

Respostas:

263

Vamos começar com um exemplo de código:

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

Esse código não é compilado (erro de sintaxe) no Haskell 98 simples. Requer uma extensão para suportar a forallpalavra - chave.

Basicamente, existem 3 diferentes usos comuns para a forallpalavra-chave (ou pelo menos assim parece ), e cada um tem sua própria extensão Haskell: ScopedTypeVariables, RankNTypes/ Rank2Types, ExistentialQuantification.

O código acima não recebe um erro de sintaxe com nenhum dos habilitados, mas apenas verifica o tipo com ScopedTypeVariablesativado.

Variáveis ​​do tipo de escopo:

Variáveis ​​de tipo com escopo definido ajudam a especificar tipos de código dentro de wherecláusulas. Faz o bno val :: bmesmo que o bin foob :: forall a b. (b -> b) -> b -> (a -> b) -> Maybe a -> b.

Um ponto confuso : você pode ouvir que, quando omite o forallde um tipo, ele ainda está implicitamente presente. ( da resposta de Norman: "normalmente essas línguas omitem o conjunto dos tipos polimórficos" ). Esta afirmação está correta, mas refere-se aos outros usos foralle não ao ScopedTypeVariablesuso.

Tipos Rank-N:

Vamos começar com o mayb :: b -> (a -> b) -> Maybe a -> bequivalente a mayb :: forall a b. b -> (a -> b) -> Maybe a -> b, exceto quando ScopedTypeVariablesestá ativado.

Isso significa que ele funciona para todos ae b.

Digamos que você queira fazer algo assim.

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

Qual deve ser o tipo disso liftTup? É liftTup :: (forall x. x -> f x) -> (a, b) -> (f a, f b). Para ver o porquê, vamos tentar codificá-lo:

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 .. por que o GHC infere que a tupla deve conter duas do mesmo tipo? Vamos dizer que elas não precisam ser"

-- 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. então aqui GHC não vamos aplicar liftFuncem vcausa v :: be liftFuncquer um x. Nós realmente queremos que nossa função obtenha uma função que aceite qualquer possível x!

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

Portanto, não é isso liftTupque funciona para todos x, é a função que ele obtém.

Quantificação Existencial:

Vamos usar um exemplo:

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

Como isso é diferente dos Rank-N-Types?

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

Com Rank-N-Types, forall asignifica que sua expressão deve atender a todos os as possíveis . Por exemplo:

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

Uma lista vazia funciona como uma lista de qualquer tipo.

Portanto, com Quantificação Existencial, foralls nas datadefinições significa que, o valor contido pode ser de qualquer tipo adequado, não que deve ser de todos os tipos adequados.

yairchu
fonte
OK, recebi minhas seis horas e agora posso decodificar sua resposta. :) Entre você e Norman, recebi exatamente o tipo de resposta que estava procurando. Obrigado.
APENAS MINHA OPINIÃO correta
2
Na verdade, você ScopedTypeVariablesparece pior do que é. Se você escrever o tipo b -> (a -> b) -> Maybe a -> bcom esta extensão, ainda será exatamente equivalente a forall a b. b -> (a -> b) -> Maybe a -> b. No entanto, se você quiser se referir ao mesmo b (e não tê-lo quantificado implicitamente) , precisará escrever a versão quantificada explicitamente. Caso contrário, STVseria uma extensão extremamente intrusiva.
Nominolo 19/06/10
1
@nominolo: Eu não quis me rebaixar ScopedTypeVariablese não acho que seja ruim. imho, é uma ferramenta muito útil para o processo de programação, e especialmente para iniciantes em Haskell, e sou grato por ele existir.
yairchu
2
Essa é uma pergunta bastante antiga (e resposta), mas pode valer a pena atualizá-la para refletir o fato de que tipos existenciais podem ser expressos usando GADTs de uma maneira que (pelo menos para mim) torne a quantificação muito mais fácil de entender.
dfeuer
1
Pessoalmente, acho que é mais fácil explicar / entender a notação existencial em termos de sua tradução para a forma GADT do que por si só, mas você certamente é livre para pensar o contrário.
Dfeuer
117

Alguém pode explicar completamente a palavra-chave forall em inglês claro e claro?

Não. (Bem, talvez Don Stewart possa.)

Aqui estão as barreiras para uma explicação simples e clara ou forall:

  • É um quantificador. Você precisa ter pelo menos um pouco de lógica (cálculo predicado) para ver um quantificador universal ou existencial. Se você nunca viu cálculo de predicado ou não se sente à vontade com quantificadores (e eu vi estudantes durante os exames de qualificação para doutorado que não se sentem à vontade), então para você, não há uma explicação fácil forall.

  • É um quantificador de tipo . Se você não viu o Sistema F e aprendeu a escrever tipos polimórficos, ficará forallconfuso. A experiência com Haskell ou ML não é suficiente, porque normalmente esses idiomas omitem os foralltipos polimórficos. (Na minha opinião, isso é um erro de design de linguagem.)

  • Em Haskell, em particular, forallé usado de maneiras que acho confusas. (Eu não sou um teórico de tipos, mas meu trabalho me põe em contato com muita teoria de tipos, e estou bastante à vontade com ela.) Para mim, a principal fonte de confusão é que ela forallé usada para codificar um tipo que Eu mesmo preferiria escrever com exists. Isso é justificado por um pouco complicado de isomorfismo de tipo envolvendo quantificadores e setas, e toda vez que quero entender, tenho que procurar as coisas e descobrir o isomorfismo.

    Se você não se sente à vontade com a idéia de isomorfismo de tipo, ou se não tem prática de pensar em isomorfismos de tipo, esse uso forallirá impedi-lo.

  • Embora o conceito geral de forallseja sempre o mesmo (obrigatório para introduzir uma variável de tipo), os detalhes de diferentes usos podem variar significativamente. O inglês informal não é uma ferramenta muito boa para explicar as variações. Para realmente entender o que está acontecendo, você precisa de matemática. Nesse caso, a matemática relevante pode ser encontrada no texto introdutório de Benjamin Pierce, Tipos e linguagens de programação , que é um livro muito bom.

Quanto aos seus exemplos particulares,

  • runST deve fazer sua cabeça doer. Tipos de classificação mais alta (todos à esquerda de uma flecha) raramente são encontrados na natureza. Convido você a ler o artigo que apresentou runST: "Threads de Estado Funcional Preguiçoso" . Este é um artigo realmente bom, e lhe dará uma intuição muito melhor para o tipo de runSTem particular e para os tipos de classificação mais alta em geral. A explicação leva várias páginas, está muito bem feita e não vou tentar condensá-la aqui.

  • Considerar

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

    Se eu ligar bar, posso simplesmente escolher qualquer tipo aque quiser e transmitir uma função de um tipo apara outro a. Por exemplo, eu posso passar a função (+1)ou a função reverse. Você pode pensar no forallque diz: "Preciso escolher o tipo agora". (A palavra técnica para escolher o tipo é instanciação .)

    As restrições de chamada foosão muito mais rigorosas: o argumento foo deve ser uma função polimórfica. Com esse tipo, as únicas funções às quais posso passar foosão idou uma função que sempre diverge ou com erros, como undefined. O motivo é que foo, com , forallestá à esquerda da seta, para que o responsável pela chamada foonão consiga escolher o que aé - é a implementação defoo que começa a escolher o que aé. Como forallestá à esquerda da seta, e não acima da seta como em bar, a instanciação ocorre no corpo da função e não no site da chamada.

Resumo: Um completo explicação da forallpalavra - chave requer matemática e só pode ser entendida por alguém que estudou a matemática. Mesmo explicações parciais são difíceis de entender sem a matemática. Mas talvez minhas explicações parciais, não matemáticas, ajudem um pouco. Vá ler Launchbury e Peyton Jones em runST!


Termo aditivo: jargão "acima", "abaixo", "à esquerda de". Isso não tem nada a ver com a maneira como os tipos de texto são escritos e tudo a ver com as árvores de sintaxe abstrata. Na sintaxe abstrata, a forallleva o nome de uma variável de tipo e, em seguida, existe um tipo completo "abaixo" do forall. Uma seta pega dois tipos (argumento e tipo de resultado) e forma um novo tipo (o tipo de função). O tipo de argumento é "à esquerda" da seta; é o filho esquerdo da seta na árvore de sintaxe abstrata.

Exemplos:

  • No forall a . [a] -> [a] , o forall está acima da seta; o que está à esquerda da seta é [a].

  • No

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

    o tipo entre parênteses seria chamado "um forall à esquerda de uma seta". (Estou usando tipos como este em um otimizador em que estou trabalhando.)

Norman Ramsey
fonte
Na verdade, eu tenho o acima / abaixo / à esquerda sem ter que pensar sobre isso. Eu sou um idiota, sim, mas um velho idiota que já teve que lutar com isso antes. (Escrevendo um compilador ASN.1, entre outros .;) Obrigado pelo adendo.
APENAS MINHA OPINIÃO correta
12
@ APENAS obrigado, mas estou escrevendo para a posteridade. Encontrei mais de um programador que pensa que forall a . [a] -> [a], o forall está à esquerda da seta.
Norman Ramsey
OK, repassando sua resposta em detalhes, agora tenho que lhe agradecer, Norman, do fundo do meu coração. Um monte de coisas se encaixou com um clique alto agora, e as coisas que eu ainda não entendo, pelo menos reconheço que não tenho a intenção de entendê-las e que apenas passarão forallnessas circunstâncias, como efetivamente barulho. Vou dar uma olhada no artigo ao qual você vinculou (obrigado pelo link também!) E ver se ele está no meu domínio da compreensão. Parabéns.
APENAS MINHA OPINIÃO correta
10
Eu li à esquerda e olhei, literalmente, à esquerda. Portanto, não estava claro para mim até que você dissesse "analisar árvore".
Paul Nathan
Graças ao ponteiro do livro de Pierce. Ele tem uma explicação muito clara do Sistema F. Ele explica por que existsnunca foi implementado. (Não faz parte do sistema F!) Em Haskell, parte do sistema F é implícita, mas forallé uma das coisas que não pode ser varrida para debaixo do tapete completamente. É como se eles tivessem começado com Hindley-Milner, o que permitiria foralltornar-se implícito, e depois optaram por um sistema de tipos mais poderoso, confundindo aqueles de nós que estudavam o 'tudo' e 'existe' da FOL e paravam ali.
T_S_
50

Minha resposta original:

Alguém pode explicar completamente a palavra-chave forall em inglês claro e claro

Como Norman indica, é muito difícil dar uma explicação clara e clara em inglês de um termo técnico da teoria dos tipos. Estamos todos tentando embora.

Há apenas uma coisa a lembrar sobre 'forall': vincula tipos a algum escopo . Depois de entender isso, tudo fica bem fácil. É o equivalente a 'lambda' (ou uma forma de 'let') no nível de tipo - Norman Ramsey usa a noção de "esquerda" / "acima" para transmitir esse mesmo conceito de escopo em sua excelente resposta .

A maioria dos usos de 'forall' é muito simples e você pode encontrá-los introduzidos no Manual do Usuário do GHC, S7.8 ., Particularmente o excelente S7.8.5 em formas aninhadas de 'forall'.

Em Haskell, geralmente deixamos de lado o fichário para tipos, quando o tipo é universalmente quantificado, da seguinte forma:

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

é equivalente a:

length :: [a] -> Int

É isso aí.

Como você pode vincular variáveis ​​de tipo agora a algum escopo, pode ter escopos diferentes do nível superior (" quantificado universalmente "), como seu primeiro exemplo, em que a variável de tipo é visível apenas na estrutura de dados. Isso permite tipos ocultos (" tipos existenciais "). Ou podemos ter um aninhamento arbitrário de ligações ("tipos de classificação N").

Para entender profundamente os sistemas de tipos, você precisará aprender algum jargão. Essa é a natureza da ciência da computação. No entanto, usos simples, como acima, devem poder ser compreendidos intuitivamente, por analogia, com 'let' no nível de valor. Uma ótima introdução é Launchbury e Peyton Jones .

Don Stewart
fonte
5
tecnicamente, length :: forall a. [a] -> Intnão é equivalente a length :: [a] -> Intquando ScopedTypeVariablesestá ativado. Quando forall a.existe, afeta lengtha wherecláusula (se houver) e altera o significado das variáveis ​​de tipo nomeadas anela.
Yairchu
2
De fato. ScopedTypeVariables complicam um pouco a história.
Don Stewart
3
@ DonStewart, pode "vincular tipos a algum escopo" melhor formulado como "vincula variáveis ​​de tipo a algum escopo" na sua explicação?
Romildo 27/08
31

Eles estão densamente repletos de suposições que eu já li em qualquer ramo da matemática discreta, teoria das categorias ou álgebra abstrata que é popular nesta semana. (Se eu nunca mais ler as palavras "consulte o documento para obter detalhes sobre a implementação" novamente, será muito cedo).

E quanto à lógica simples de primeira ordem? forallé claramente uma referência à quantificação universal e, nesse contexto, o termo existencial também faz mais sentido, embora fosse menos complicado se houvesse uma existspalavra - chave. Se a quantificação é efetivamente universal ou existencial depende da localização do quantificador em relação ao local onde as variáveis ​​são usadas em qual lado de uma seta de função e tudo é um pouco confuso.

Portanto, se isso não ajudar, ou se você apenas não gostar da lógica simbólica, de uma perspectiva mais funcional da programação, você pode pensar nas variáveis ​​de tipo apenas como parâmetros do tipo (implícitos) para a função. As funções que tomam os parâmetros de tipo nesse sentido são tradicionalmente escritas usando uma lambda maiúscula por qualquer motivo, que vou escrever aqui como /\.

Portanto, considere a idfunção:

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

Podemos reescrevê-lo como lambdas, movendo o "parâmetro de tipo" para fora da assinatura de tipo e adicionando anotações de tipo em linha:

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

Aqui está a mesma coisa feita para const:

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

Portanto, sua barfunção pode ser algo como isto:

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

Observe que o tipo de função atribuída barcomo argumento depende do barparâmetro de tipo. Considere se você tivesse algo parecido com isto:

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

Aqui bar2está aplicando a função a algo do tipo Char, portanto, fornecer bar2qualquer parâmetro de tipo diferente de Charcausará um erro de tipo.

Por outro lado, eis o que foopode parecer:

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

Ao contrário bar, foona verdade não aceita nenhum tipo de parâmetro! É preciso uma função que em si leva um parâmetro de tipo, em seguida, aplica essa função para dois diferentes tipos.

Portanto, quando você vir uma forallassinatura de tipo, pense nela como uma expressão lambda para assinaturas de tipo . Assim como lambdas regulares, o escopo de forallse estende o mais para a direita possível, entre parênteses, e assim como variáveis ​​ligadas em um lambda regular, as variáveis ​​de tipo vinculadas por a forallestão apenas no escopo da expressão quantificada.


Post scriptum : Talvez você deva se perguntar - agora que estamos pensando em funções que aceitam parâmetros de tipo, por que não podemos fazer algo mais interessante com esses parâmetros do que colocá-los em uma assinatura de tipo? A resposta é que nós podemos!

Uma função que coloca variáveis ​​de tipo juntas com um rótulo e retorna um novo tipo é um construtor de tipos , que você pode escrever algo como isto:

Either = /\a b -> ...

Mas precisaríamos de uma notação completamente nova, porque a maneira como esse tipo é escrito, como Either a b, já é sugestivo de "aplicar a funçãoEither a esses parâmetros".

Por outro lado, uma função que tipo de "correspondência de padrão" em seus parâmetros de tipo, retornando valores diferentes para tipos diferentes, é um método de uma classe de tipo . Uma pequena expansão na minha /\sintaxe acima sugere algo como isto:

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]

Pessoalmente, acho que prefiro a sintaxe real de Haskell ...

Uma função que "padroniza" seus parâmetros de tipo e retorna um tipo existente arbitrário é uma família de tipos ou uma dependência funcional - no caso anterior, ela ainda se parece muito com uma definição de função.

CA McCann
fonte
1
Uma tomada interessante aqui. Isso me dá outro ângulo de ataque ao problema que pode ser proveitoso a longo prazo. Obrigado.
APENAS MINHA OPINIÃO correta
@KennyTM: Ou, a propósito λ, mas a extensão de sintaxe unicode do GHC não suporta isso porque λ é uma carta , um fato infeliz que hipoteticamente também se aplicaria às minhas hipotéticas abstrações big-lambda. Portanto, /\ por analogia com \ . Acho que eu poderia ter utilizado , mas eu estava tentando evitar cálculo de predicados ...
CA McCann
29

Aqui está uma explicação rápida e suja em termos simples, com a qual você provavelmente já deve estar familiarizado.

A forallpalavra-chave é realmente usada apenas de uma maneira no Haskell. Sempre significa a mesma coisa quando você a vê.

Quantificação universal

Um tipo universalmente quantificado é um tipo do formulário forall a. f a. Um valor desse tipo pode ser pensado como uma função que aceita um tipo a como argumento e retorna um valor do tipo f a. Exceto que em Haskell esses argumentos de tipo são transmitidos implicitamente pelo sistema de tipos. Essa "função" deve fornecer o mesmo valor, independentemente do tipo que receber, portanto, o valor é polimórfico .

Por exemplo, considere o tipo forall a. [a]. Um valor desse tipo pega outro tipo ae retorna uma lista de elementos desse mesmo tipo a. Existe apenas uma implementação possível, é claro. Teria de lhe dar a lista vazia, porque apoderia ser absolutamente qualquer tipo. A lista vazia é o único valor de lista polimórfico em seu tipo de elemento (já que não possui elementos).

Ou o tipo forall a. a -> a. O chamador de uma função fornece um tipo ae um valor do tipo a. A implementação deve retornar um valor desse mesmo tipo a. Há apenas uma implementação possível novamente. Teria que retornar o mesmo valor que foi dado.

Quantificação existencial

Um tipo existencialmente quantificado teria a forma exists a. f a, se Haskell suportasse essa notação. Um valor desse tipo pode ser pensado como um par (ou um "produto") que consiste em um tipo ae um valor do tipo f a.

Por exemplo, se você tem um valor do tipo exists a. [a], você tem uma lista de elementos de algum tipo. Pode ser de qualquer tipo, mas mesmo que você não saiba o que é, há muito o que fazer nessa lista. Você pode revertê-lo ou contar o número de elementos ou executar qualquer outra operação de lista que não dependa do tipo dos elementos.

OK, então espere um minuto. Por que Haskell usa forallpara denotar um tipo "existencial" como o seguinte?

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

Pode ser confuso, mas está realmente descrevendo o tipo do construtor de dados SB :

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

Uma vez construído, você pode pensar em um valor do tipo ShowBoxcomo consistindo em duas coisas. É um tipo sjunto com um valor do tipo s. Em outras palavras, é um valor de um tipo quantificado existencialmente. ShowBoxpoderia realmente ser escrito como exists s. Show s => sse Haskell apoiasse essa notação.

runST e amigos

Dado isso, como são diferentes?

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

Vamos primeiro pegar bar. Ele pega um tipo ae uma função do tipo a -> ae produz um valor do tipo (Char, Bool). Podemos escolher Intcomo o ae atribuir a ele uma função do tipo, Int -> Intpor exemplo. Mas fooé diferente. Requer que a implementação de fooseja capaz de passar qualquer tipo que desejar para a função que lhe damos. Portanto, a única função que podemos razoavelmente dar a ela é id.

Agora devemos ser capazes de entender o significado do tipo de runST:

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

Portanto runST, deve ser capaz de produzir um valor do tipo a, não importa qual o tipo que damos a. Para fazer isso, ele usa um argumento do tipo forall s. ST s aque certamente deve produzir o a. Além disso, ele deve ser capaz de produzir um valor do tipo, aindependentemente do tipo que a implementação runSTdecida fornecer s.

Tá, e daí? O benefício é que isso impõe uma restrição ao chamador runST, pois o tipo anão pode envolver o tipo s. Você não pode transmitir um valor do tipo ST s [s], por exemplo. O que isso significa na prática é que a implementação de runSTé livre para realizar mutações com o valor do tipo s. O tipo garante que essa mutação seja local para a implementação de runST.

O tipo de runSTé um exemplo de um tipo polimórfico de classificação 2 porque o tipo de seu argumento contém um forallquantificador. O tipo fooacima também é de classificação 2. Um tipo polimórfico comum, como o de bar, é de classificação 1, mas se torna de classificação 2 se for necessário que os tipos de argumentos sejam polimórficos, com seu próprio forallquantificador. E se uma função recebe argumentos de classificação 2, seu tipo é classificação 3, e assim por diante. Em geral, um tipo que recebe argumentos polimórficos de classificação ntem classificação n + 1.

Apocalisp
fonte
11

Alguém pode explicar completamente a palavra-chave forall em inglês claro e claro (ou, se existir em algum lugar, apontar para uma explicação tão clara que eu perdi) que não assume que eu sou um matemático mergulhado no jargão?

Vou tentar explicar apenas o significado e talvez a aplicação forallno contexto de Haskell e seus sistemas de tipos.

Mas antes que você entenda que eu gostaria de direcioná-lo para uma conversa muito acessível e agradável de Runar Bjarnason intitulada " Restrições Liberam, Liberdades Limitam ". A palestra está cheia de exemplos de casos de uso do mundo real, bem como de exemplos no Scala, para apoiar esta afirmação, embora não mencione forall. Vou tentar explicar a forallperspectiva abaixo.

                CONSTRAINTS LIBERATE, LIBERTIES CONSTRAIN

É muito importante digerir e acreditar que esta declaração deve prosseguir com a explicação a seguir, por isso peço que você assista à palestra (pelo menos partes dela).

Agora, um exemplo muito comum, mostrando a expressividade do sistema de tipos Haskell é esta assinatura de tipo:

foo :: a -> a

Diz-se que, dada essa assinatura de tipo, existe apenas uma função que pode satisfazer esse tipo e essa é a identityfunção ou o que é conhecido popularmente id.

Nos estágios iniciais de aprendizado de Haskell, sempre me perguntei as funções abaixo:

foo 5 = 6

foo True = False

ambos satisfazem a assinatura do tipo acima, então por que o pessoal da Haskell afirma que é id somente isso que satisfaz a assinatura de tipo?

Isso ocorre porque há um implícito foralloculto na assinatura do tipo. O tipo real é:

id :: forall a. a -> a

Então, agora vamos voltar à declaração: restrições liberam, liberdades restringem

Traduzindo isso para o sistema de tipos, esta declaração se torna:

Uma restrição no nível do tipo se torna uma liberdade no nível do termo

e

Uma liberdade no nível do tipo se torna uma restrição no nível do termo


Vamos tentar provar a primeira afirmação:

Uma restrição no nível do tipo.

Então, colocando uma restrição em nossa assinatura de tipo

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

torna-se uma liberdade no nível do termo nos dá a liberdade ou flexibilidade para escrever todos esses

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

O mesmo pode ser observado restringindo-se aa qualquer outra classe, etc.

Então agora o que este tipo de assinatura: foo :: (Num a) => a -> atraduz é:

a , st a -> a, a  Num

Isso é conhecido como quantificação existencial, que significa que existem algumas instâncias apara as quais uma função é alimentada com algo do tipoa retorna algo do mesmo tipo, e todas essas instâncias pertencem ao conjunto de Números.

Portanto, podemos ver a adição de uma restrição (que adeve pertencer ao conjunto de Números), libera o nível de termo para ter várias implementações possíveis.


Agora, vamos para a segunda declaração e a que realmente traz a explicação de forall:

Uma liberdade no nível do tipo se torna uma restrição no nível do termo

Então agora vamos liberar a função no nível de tipo:

foo :: forall a. a -> a

Agora isso se traduz em:

a , a -> a

o que significa que a implementação dessa assinatura de tipo deve ser tal que seja a -> apara todas as circunstâncias.

Então agora isso começa a nos restringir no nível do termo. Não podemos mais escrever

foo 5 = 7

porque essa implementação não seria satisfatória se colocarmos acomo a Bool. apode ser um Charou um [Char]ou um tipo de dados personalizado. Sob todas as circunstâncias, ele deve retornar algo do tipo semelhante. Essa liberdade no nível de tipo é conhecida como Quantificação Universal e a única função que pode satisfazer isso é

foo a = a

que é comumente conhecida como a identityfunção


Portanto, forallexiste um libertyno nível de tipo, cujo objetivo real é constraino nível de termo para uma implementação específica.

Abhiroop Sarkar
fonte
9

A razão pela qual existem diferentes usos dessa palavra-chave é que ela é realmente usada em pelo menos duas extensões de sistema de tipos diferentes: tipos de classificação mais alta e existenciais.

Provavelmente, é melhor apenas ler e entender essas duas coisas separadamente, em vez de tentar obter uma explicação do porquê 'forall' é uma parte apropriada da sintaxe das duas ao mesmo tempo.


fonte
3

Como é existencial existencial?

Com Existencial-Quantificação, foralls em datadefinições significa que, o valor contido pode ser de qualquer tipo adequado, não que deve ser de todos os tipos adequados. - resposta de yachiru

Uma explicação de por forallem datadefinições são isomorfo a (exists a. a)(pseudo-Haskell) pode ser encontrada em "Haskell / tipos existencialmente quantificadas" das Wikibooks .

A seguir, um breve resumo literal:

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

Ao fazer a correspondência / desconstrução de padrões MkT x, qual é o tipo x?

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

xpode ser de qualquer tipo (conforme declarado em forall) e, portanto, é do tipo:

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

Portanto, o seguinte é isomórfico:

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

forall significa forall

Minha simples interpretação de tudo isso é que " forallrealmente significa 'para todos'". Uma distinção importante a ser feita é o impacto forallsobre a definição versus aplicação de função .

A forallsignifica a definição do valor ou função deve ser polimórfica.

Se o que está sendo definido é um valor polimórfico , significa que o valor deve ser válido para todos os adequados a, o que é bastante restritivo.

Se a coisa que está sendo definida é uma função polimórfica , significa que a função deve ser válida para todos os adequados a, o que não é tão restritivo, porque apenas porque a função é polimórfica não significa que o parâmetro a ser aplicado deve ser polimórfico. Ou seja, se a função é válida para todos a, inversamente, qualquer adequado apode ser aplicado à função. No entanto, o tipo do parâmetro pode ser escolhido apenas uma vez na definição da função.

Se a forallestiver dentro do tipo de parâmetro da função (ou seja, a Rank2Type), significa que o parâmetro aplicado deve ser verdadeiramente polimórfico, para que seja consistente com a idéia de definição de forallmeios polimórficos. Nesse caso, o tipo do parâmetro pode ser escolhido mais de uma vez na definição da função ( "e é escolhido pela implementação da função", conforme apontado por Norman )

Portanto, a razão pela qual existenciais datadefinições permite que qualquer a é porque o construtor de dados é um polimórfico função :

MkT :: forall a. a -> T

tipo de MkT :: a -> *

O que significa que qualquer um apode ser aplicado à função. Em oposição a, digamos, um valor polimórfico :

valueT :: forall a. [a]

tipo de valueT :: a

O que significa que a definição de valueT deve ser polimórfica. Nesse caso, valueTpode ser definido como uma lista vazia []de todos os tipos.

[] :: [t]

Diferenças

Mesmo que o significado para forallseja consistente em ExistentialQuantificatione RankNType, existenciais tenha uma diferença, pois o dataconstrutor pode ser usado na correspondência de padrões. Conforme documentado no guia do usuário do ghc :

Quando a correspondência de padrões, cada correspondência de padrões apresenta um novo tipo distinto para cada variável de tipo existencial. Esses tipos não podem ser unificados com nenhum outro tipo, nem podem escapar do escopo da correspondência de padrões.

Louis Pan
fonte