Podem listas de ser definido de uma forma especial, de modo que eles contêm coisas de tipo diferente?

Question

No https://www.seas.harvard.edu/courses/cs152/2019sp/lectures/lec18-monads.pdf está escrito que

Um tipo de $ au$ lista é o tipo de listas com elementos do tipo $ au$

Por que deve conter uma lista de elementos do mesmo tipo?Por que não pode conter elementos de tipos diferentes?Há uma maneira de definir uma lista polimorficamente em digitado cálculo lambda, por isso leva elementos de qualquer tipo?

Podemos usar a Lista de mônada em listas, definido polimorficamente?

Answer 1

A resposta curta é que $ au\ ext{lista}$ é definido como um tipo de construtor, juntamente com as regras para a formação e eliminação, e assim poderíamos da mesma forma definir um tipo de construtor que permitiu termos de tipos diferentes para formar uma única variável:-digitado lista".No entanto, as listas não podem assumir diferentes tipos, na definição dada, simplesmente porque eles são definidos com respeito a um único tipo.Em ambos os casos, a adição de listas, ou variavelmente escrito listas, envolve expandir simplesmente escreveu $\lambda$-cálculo, como as listas de qualquer tipo não existem no habitual apresentação.

Se temos um pouco mais rico do tipo de sistema que simplesmente escreveu $\lambda$-cálculo, podemos codificar de forma variável-digitado listas usando o padrão de $ au\ ext{lista}$s.

• Se temos uma forma de subtyping, podemos armazenar termos de tipos diferentes, desde que eles compartilham um supertipo.No entanto, quando nos elementos do projeto de fora da lista, já não podemos dizer especificamente que tipo eles foram para começar (o que pode ser familiar de programação orientada a objeto), de modo que este é um pouco limitado.
• Se nós dependente soma tipos de (também chamado de $\Sigma$-tipos) e um universo tipo $\mathcal U$ (i.é."um tipo de" tipos), podemos formar o tipo de $(\Sigma_{A :\mathcal U} A)\ ext{lista}$, cujos elementos são pares consistindo de um tipo de $A$ e um termo de tipo.

Finalmente, eu só vou note que o polimorfismo não ajuda se nós queremos heterogêneos listas:ele apenas nos permite manipular homogênea listas para diferentes $ au$ de forma mais eficaz.Polimórficos os tipos devem ser uniforme em certo sentido, que é por isso que nós precisamos aqui, em vez de dependência.

---

Para responder a uma pergunta:se temos dois variavelmente-listas ordenadas usando o dependente do tipo de abordagem, podemos concatenar e achate-as listas de tão comuns listas.

• O $\mathrm{Lista}$ mônada tem uma operação $\mathrm{juntar}$ (na linguagem Haskell), então é dada uma lista de variavelmente escrito listas, $$l = [[(A, A), (B, b)], [(C, c), (D, d)]] :(\Sigma_{X :\mathcal U} X)\ ext{lista}$$ podemos realizar $\mathrm{juntar}$ para obter uma nova lista: $$\mathrm{juntar}(l) = [(A, A), (B, b), (C, c), (D, d)] :(\Sigma_{X :\mathcal U} X)\ ext{lista}$$
• Da mesma forma, $ au\ ext{lista}$ pode ser equipado com uma operação de concatenação $+\!+$, assim, as duas listas no exemplo anterior, podemos concatená-las para um resultado semelhante:$$[(A, A), (B, b)]\ {+\!+}\ [(C, c), (D, d)] = [(A, A), (B, b), (C, c), (D, d)] :(\Sigma_{X :\mathcal U} X)\ ext{lista}$$

Answer 2

Não, isso não é possível, pelo menos não de uma maneira útil.Pense sobre o que o tipo de head seria.Quando cada elemento possui o mesmo tipo de head tem o tipo de $ au \;\mathsf{lista} o au$.Sem essa garantia, não haveria maneira de escrever um coerente tipo de head.Para o tipo de lista a ser útil, nós queremos ser capazes de tirar conclusões úteis sobre o que o tipo de saída de head é;e que exige que todos os elementos da lista para ter o mesmo tipo.

Eu suponho que você poderia definir uma "lista" de alguma outra forma, mas ele não seria útil (você não conseguia raciocinar sobre o tipo de valores você sair de la com head) ou que não correspondem a algo que os cientistas da computação chamam um "lista".

Answer 3

Você não pode ser útil definir um tipo de $\mathsf{lista}$ que não indicar o tipo dos seus elementos.Isso não significa que você não pode ter listas que contêm coisas de diferentes tipos:é ainda um $ au \, \mathsf{lista}$, mas você pode colocar o "contêm coisas de diferentes tipos de" parte no $ au$.

(Estas idéias básicas já estavam em D. W. e varkor's respostas.É importante perceber que essas respostas não são contraditórias!Eles estão olhando para os diferentes aspectos da imagem maior.)

Se o tipo de sistema permite que você defina um tipo de $\mathsf{lista}$ que pode conter elementos de qualquer tipo, em seguida, considerar o tipo de retorno de um processo de destruição, como $\mathsf{cabeça}$ ou $\mathsf{n}$, ou o tipo de argumento de função para $\mathsf{dobra}$.Você não tem nenhuma informação sobre o tipo de elementos, então eles teriam que permitir qualquer tipo.Isso significa que, por exemplo, $\lambda x.\mathsf{cabeça}(\mathsf{contras}(x, \mathsf{nil}))$ não vai lhe dar de volta um valor do mesmo tipo, como $x$ (ou $x \, \mathsf{opção}$, assim que $\mathsf{cabeça}$ pode voltar $\mathsf{None}$ em listas vazias).Mas então o que você voltar da $\mathsf{cabeça}$?

• Se $\mathsf{cabeça}$ permite que o chamador para especificar qualquer tipo de retorno, em seguida, o tipo de sistema é praticamente inútil, pois permite arbitrário coerção entre tipos através de $\lambda x.\mathsf{cabeça}(\mathsf{contras}(x, \mathsf{nil}))$.É inútil para a lógica desde o Curry-Howard correspondência mapeia um arbitrário coerção entre tipos para ter toda proposição implica a de todos os outros proposição, para você ter uma lógica inconsistente.
• Se não, então você não pode voltar para um valor de tipo original através de $\lambda x.\mathsf{cabeça}(\mathsf{contras}(x, \mathsf{nil}))$.Portanto, você pode ser capaz de criar listas, mas você não pode obter elementos fora deles.

Um exemplo da vida real que, na verdade, demonstra que ambos os comportamentos acima é versões anteriores de Java, antes ele tinha medicamentos genéricos.Java tem um tipo estático e um sistema de tipo dinâmico do sistema.No tipo estático do sistema, any1 valor pode ser transparente coagido a Object, porque Object é considerado um supertipo de tudo.Assim, você pode colocar qualquer valor em um List.Mas o que você voltar de fora, é o valor original do elenco para Object, não o valor original em si.O tipo dinâmico do sistema, você pode utilizar qualquer tipo para qualquer outro tipo, assim, na prática, para obter um valor de uma lista, você forçá-lo para o tipo desejado.Mas ter coerções derrota o propósito de um tipo de sistema.Este problema é a principal razão por que o Java adquiridos genéricos:eles permitem que a linguagem para ter $ au \, \mathsf{lista}$ em vez de $\mathsf{lista}$ (ou em Java notação, List<T> em vez de List).

Só porque uma lista de tipo de elementos de $ au \, \mathsf{lista}$ é uma lista de elementos do tipo $ au$ — não significa que você não pode organizar para colocar valores de diferentes tipos em uma mesma lista.Praticamente qualquer linguagem que permite a definição de um tipo de lista não permitindo que algébricas do tipo de dados definições, algo como isto:$$ au \, \mathsf{lista} ::= \mathsf{nil} \mid \mathsf{contras} \: au \:( au \, \mathsf{lista}) $$ Suponha que você deseja colocar os dois inteiros e strings na mesma lista.Definir um tipo de $$ U ::= \mathsf{I} \:\mathsf{int} \mid \mathsf{S} \:\mathsf{string} $$ Agora $U \, \mathsf{lista}$ é o tipo de lista que pode conter uma mistura de inteiros e strings, por exemplo, $[\mathsf{I}(3), \mathsf{S}( exttt{"foo"}), \mathsf{I}(4)]$.

Você pode fazer listas heterogêneas, desta forma, na medida em que o tipo de sistema permite heterogêneos tipos.Note que "heterogêneo listas" não é muito correta:a lista em si é homogênea:é uma lista de elementos do tipo U $$.A heterogeneidade é o tipo U $$.Para colocar um elemento na lista, você pode aplicar um construtor de U $$ primeiro.Depois de obter um elemento da lista, aplica um processo de destruição de U $$ para obter o valor original com o seu tipo original.

Você pode fazer isso com qualquer tipo que a língua oferece suporte.Se você quer um completamente heterogêneo lista, você precisa de um idioma que suporta um tipo "any".O que é Object em Java, por exemplo.Fortemente tipada pode ter um "qualquer" tipo se eles carregam as necessárias informações de tipo em tempo de execução.O Java faz isso o tempo todo.As línguas que são estaticamente tipada (como OCaml e outros ML dialetos, Haskell, Limpo, Swift ou Ferrugem) pode fazer isso com um $\mathsf{dyn}$ digite cujo tempo de execução de representação contém o tipo do valor.Com tal tipo $\mathsf{dyn} \, \mathsf{lista}$ é um tipo de lista que pode conter um valor de qualquer tipo.Este tipo de coexiste com outros tipos de lista, como $\mathsf{int} \, \mathsf{lista}$ (onde os elementos da lista não levar runtime type information).

Uma abordagem que envolva a construção de estruturas de dados heterogêneas existencial tipos de.Existencial tipos de deixar o pacote um tipo com um valor desse tipo: $(\existe au :P( au).a)$ onde $a$ é uma expressão de algum tipo de $T$ de tal forma que $P(T)$ é verdade.Por exemplo, $\mathsf{dyn}$ pode ser modelado como um caso especial onde $P$ é verdade de todos os tipos (não vinculante existencial).Um uso comum para existencial tipos é dizer que $ au$ é um registro, ou módulo de classe com alguns elementos específicos ou métodos, sem dar todos os detalhes:existencial tipos são uma forma de modelo de tipos abstratos.Com um limitado existencial, você ainda pode fazer algumas coisas úteis com o valor, mesmo sem informações de tipo de tempo de execução (por exemplo,você pode chamar os métodos que $P$ descreve), mas não obter o tipo de original.Uma lista cujos elementos têm a existência de um tipo de $T_E = (\existe au \ldots)$ pode ser visto como uma lista heterogênea (e porque os seus elementos têm diferentes "real" tipos"), mas ainda é homogênea no sentido de que, se você obter um valor da lista, tudo que você sabe é o seu tipo de pacote $T_E$.

Se o idioma tiver dependentes de tipos, você pode empacotar um valor com tipo em uma maneira que permite recuperar o valor original: $\mathsf{pacote} ::= \sum_{ au:\mathsf{TIPO}} au$ onde $\mathsf{TIPO}$ é o tipo de tipos.Este é um dependente do tipo de soma onde o primeiro componente passa a ser um tipo.O $\mathsf{package}$ tipo é uma forma de implementar unbounded existentials em uma dependência linguagem.Você pode construir delimitada existentials adicionando restrições $ au$.Mais uma vez, você pode construir listas heterogêneas, no sentido de que um $\mathsf{pacote} \, \mathsf{lista}$ contém elementos cuja "real" tipos são diferentes, mas a lista em si é homogênea, no sentido de que cada elemento da lista tem o tipo de $\mathsf{package}$.Como existencial tipos, você não pode extrair um valor de uma lista de e diretamente recuperar a sua "real" do tipo.É possível destruir um valor do tipo $\mathsf{package}$ aplicando a segunda-elemento de projeção, mas tudo o que você sabe sobre o resultado é que seu tipo é o primeiro elemento de projeção: $p :\mathsf{pacote} \vdash \pi_2(p) :\pi_1(p)$.

Até agora, temos visto que em um não-degenerada tipo de sistema, as listas são homogéneos.É possível construir listas heterogêneas, mas o tipo de lista de construtor de si é homogênea:a heterogeneidade vem do tipo de elemento.Em uma linguagem que tem tanto algébrica tipos de dados e tipos que dependem de um número inteiro (ou algo isomórficas para os naturais), é possível definir uma verdadeira heterogenenous tipo de lista.Dado um tipo de família $(T_n)_{n \in \mathbb{N}}$, você pode definir o tipo de lista cujo $n$th elemento tem o tipo de $T_n$.Aqui uma definição na língua do cálculo indutivo e construções, especificamente em Coq sintaxe.Primeiro, definir um exemplo de uma família de tipos indexados por um número inteiro: tuple A n é o tipo de n-elemento de tuplas cujos componentes têm todos o tipo de A.Para manter a definição simples, todas as tuplas têm um valor adicional U no início de tipo de unidade.Então eu definir o tipo indutivo hlist_ o que é parametrizada por um tipo de família T e um número inteiro n, que é uma lista heterogênea, cuja kth elemento tem o tipo de n + k.O parâmetro n é necessário manter a definição construtiva.Finalmente vou mostrar alguns exemplos de termos do tipo hlist (tuple bool), isto é, listas de cujo nth elemento é um nth-elemento da tupla de bool valores (com U anexado).

Inductive unit : Type := U : unit.
Fixpoint tuple (A : Type) (n : nat) : Type :=
  match n with
    | 0 => unit
    | S m => (tuple A m) * A
  end.

Inductive hlist_ (T : nat -> Type) n :=
  | Hnil : hlist_ T n
  | Hcons : (T n) -> hlist_ T (S n) -> hlist_ T n.
Definition hlist T := hlist_ T 0.

Check (Hcons (tuple bool) 0 U (Hnil _ _) : hlist (tuple bool)).
Check (Hcons (tuple bool) 0 U (Hcons _ 1 (U, true) (Hnil _ _)) : hlist (tuple bool)).
Check (Hcons (tuple bool) 0 U (Hcons _ 1 (U, true) (Hcons _ 2 (U, true, true) (Hnil _ _))) : hlist (tuple bool)).

¹ _{Exceto para alguns tipos de dados primitivos, na verdade, mas isso não é importante aqui.Quando eu digo "nenhum" sobre Java nessa resposta, quero dizer que somente os objetos, e não de tipos de dados primitivos.}