Olá, Habitantes! Muitos erros de programação são causados por incompatibilidades de tipo de dados. Um sistema de tipo forte evita uma classe inteira de erros e garante a integridade dos dados em todo o aplicativo. Ao aprender a dominar os tipos na prática diária, um desenvolvedor criará um código melhor e economizará o tempo que levaria para encontrar erros de dados complicados.
O livro mostra como usar a digitação para criar um software que não apenas é seguro e funciona sem problemas, mas também é fácil de manter.
Exemplos de solução de problemas, escritos em TypeScript, o ajudarão a desenvolver suas habilidades no trabalho com tipos, de tipos de dados simples a conceitos mais complexos, como functores e mônadas.
Neste livro:
- Criação de estruturas de dados baseadas em tipos simples, arrays e referências.
- Programação e tipos orientados a objetos.
- Usando genéricos e tipos de ordem superior.
Este livro requer experiência com uma das principais linguagens de programação, como TypeScript, Java, JavaScript, C # ou C ++.
Para quem é este livro
O livro destina-se a programadores praticantes. O leitor deve ser bom em escrever código em uma das linguagens de programação, como Java, C #, C ++ ou JavaScript / TypeScript. Os exemplos de código estão em TypeScript, mas a maior parte do material é aplicável a qualquer linguagem de programação. Na verdade, os exemplos nem sempre usam o TypeScript típico. Sempre que possível, eles se adaptaram para que os programadores em outras linguagens de programação possam entendê-los. A montagem dos exemplos de código é descrita no Apêndice A, e uma breve folha de dicas do TypeScript é descrita no Apêndice B.
Se você está envolvido no desenvolvimento de código orientado a objetos para o trabalho, pode ter ouvido falar sobre tipos de dados algébricos (ADTs), expressões lambda, genéricos, functores, mônadas e deseja entender melhor o que são e como usá-los em seu trabalho .
Este livro mostrará como usar o sistema de tipos de uma linguagem de programação para projetar um código menos sujeito a erros, mais modular e compreensível. Você verá como transformar erros de tempo de execução que podem travar todo o sistema em erros de compilação e detectá-los antes que tenham problemas.
A maior parte da literatura sobre sistemas de tipo é altamente formalizada. O livro se concentra em aplicações práticas de sistemas de tipo; portanto, há muito pouca matemática nele. No entanto, é aconselhável que você compreenda os conceitos básicos de álgebra, como funções e conjuntos. Isso é necessário para esclarecer alguns dos conceitos de que precisamos.
Algoritmos e Interatores Generalizados
Neste capítulo
- Usar as operações map (), filter () e reduce () não é apenas para arrays.
- Resolvendo uma ampla gama de problemas usando um conjunto de algoritmos comuns.
- Fornece suporte de tipo de dados genérico para o contrato desejado.
- Implementação de uma variedade de algoritmos usando diferentes categorias de iteradores.
- Implementação de algoritmos adaptativos.
Este capítulo concentra-se inteiramente em algoritmos genéricos e reutilizáveis, adequados para uma ampla variedade de tipos e estruturas de dados.
Vimos uma versão de cada uma das operações map (), filter () e reduce () no Capítulo 5, quando discutimos as funções de ordem superior. Essas funções funcionam com matrizes, mas, como vimos nos capítulos anteriores, os iteradores são uma ótima abstração para trabalhar com qualquer estrutura de dados. Começaremos implementando versões genéricas dos três algoritmos acima que funcionam com iteradores e, portanto, são aplicáveis ao processamento de árvores binárias, listas, matrizes e qualquer outra estrutura de dados iterável.
As operações map (), filter () e reduce () não são exclusivas. Falaremos sobre outros algoritmos genéricos e bibliotecas de algoritmos disponíveis na maioria das linguagens de programação modernas. Veremos por que é melhor substituir a maioria dos loops por chamadas para algoritmos de biblioteca. Também falaremos um pouco sobre APIs fluidas e interfaces de algoritmos amigáveis.
A seguir, examinaremos as restrições dos tipos de parâmetro; algoritmos e estruturas de dados genéricos podem especificar os recursos que devem estar presentes em seus tipos de parâmetro. Essa especialização leva a estruturas de dados e algoritmos menos universais que não podem ser usados em todos os lugares.
Entraremos em mais detalhes sobre iteradores e falaremos sobre suas diferentes categorias. Quanto mais especializado é um iterador, mais algoritmos eficientes são possíveis com sua participação. No entanto, nem todas as estruturas de dados são capazes de suportar iteradores especializados.
Por fim, daremos uma olhada rápida nos algoritmos adaptativos. Eles permitem implementações mais versáteis, mas menos eficientes, para iteradores com menos recursos e implementações mais eficientes, mas menos versáteis, para iteradores com mais recursos.
10.1. Operações aprimoradas de mapa (), filtro () e redução ()
No Capítulo 5, falamos sobre as operações map (), filter () e reduce () e examinamos uma das possíveis implementações de cada uma. Esses algoritmos são funções de ordem superior porque pegam outra função como argumento e a aplicam a uma sequência de dados.
A operação map () aplica uma função a cada elemento na sequência e retorna os resultados. A operação filter () aplica uma função de filtro a cada elemento e retorna apenas aqueles para os quais esta função retorna true. A operação reduz () agrupa todos os valores em uma sequência usando uma função e retorna um único valor como resultado.
Nossa implementação do Capítulo 5 usou o parâmetro genérico do tipo T e representou as sequências como matrizes de elementos do tipo T.
10.1.1. Operação de mapa ()
Vamos lembrar como implementamos a operação map (). Tínhamos dois parâmetros de tipo: T e U. A função recebe como argumento um array de valores do tipo T e uma função que converte de T em U como o segundo argumento. Ele retorna uma matriz de valores U, conforme mostrado na Listagem 10.1.
Agora, com nosso conhecimento de iteradores e geradores, vamos ver na Listagem 10.2 como implementar map () para que ele possa funcionar com qualquer Iterable <T>, não apenas arrays.
Embora a implementação original tenha se limitado a arrays, esta pode funcionar com qualquer estrutura de dados que forneça um iterador. Além disso, o código se tornou muito mais compacto.
10.1.2. Operação de filtro ()
Vamos fazer o mesmo com filter () (Listagem 10.3). Nossa implementação original esperava um array de elementos do tipo T e um predicado como entrada. Deixe-me lembrá-lo de que um predicado é uma função que pega um elemento de algum tipo e retorna um booleano. Se uma determinada função retornar true para um valor passado a ela, diz-se que o valor satisfaz o predicado.
Assim como na operação map (), usaremos um Iterable <T> em vez de um array e implementaremos este Iterable como um gerador que produz valores que satisfazem o predicado, conforme mostrado na Listagem 10.4.
Mais uma vez, surgiu uma implementação mais lacônica, capaz de funcionar não apenas com matrizes. Finalmente, modificamos a função reduz ().
10.1.3. Operação de redução ()
Nossa implementação original de reduce () esperava um array de elementos do tipo T, um valor inicial do tipo T (no caso de o array estar vazio) e uma operação op (). Esta operação é uma função que recebe dois valores do tipo T como argumentos e retorna um valor do tipo T. A operação reduz () aplica a operação ao valor inicial e o primeiro elemento da matriz, armazena o resultado, aplica o mesma operação para o resultado e o próximo elemento da matriz, e etc. (Listagem 10.5)
Você pode reescrever essa função para usar Iterable <T> em vez de uma matriz e trabalhar com qualquer sequência, conforme mostrado na Listagem 10.6. Nesse caso, não precisamos de gerador. Ao contrário das duas funções anteriores, reduz () não retorna uma sequência de elementos, mas um único valor.
O resto da implementação não mudou.
10.1.4. Filtrar () / reduzir () pipeline
Vamos ver como combinar esses algoritmos em um pipeline que seleciona apenas números pares de uma árvore binária e os soma. Vamos usar a classe BinaryTreeNode <T> do Capítulo 9 com sua travessia de árvore centralizada e concatená-la com um filtro de número par e uma função reduce () que usa adição como uma operação (Listagem 10.7).
Este exemplo é uma prova viva da eficácia dos tipos genéricos. Em vez de implementar uma nova função para percorrer uma árvore binária e somar números pares, simplesmente formamos um pipeline de processamento especificamente para o cenário desejado.
10.1.5. Exercícios
- Crie um pipeline para lidar com um iterável do tipo string: a concatenação de todas as strings não vazias.
- Crie um pipeline para processar um iterável do tipo número: escolhendo todos os números ímpares e elevando-os ao quadrado.
10,2. Algoritmos comuns
Discutimos os algoritmos map (), filter () e reduce () e também mencionamos take () no Capítulo 9. Muitos outros algoritmos são freqüentemente usados em pipelines. Vou listar alguns deles. Não vamos olhar para implementações - vou apenas descrever quais argumentos (além de Iterable) eles recebem e como processam os dados. Além disso, listarei os vários nomes aos quais esses algoritmos podem ser referidos:
- map () toma como entrada uma sequência de valores do tipo T e uma função (valor: T) => U, e retorna uma sequência de valores do tipo U após aplicar esta função a todos os valores da entrada seqüência. Ele também aparece sob os nomes fmap (), select ();
- filter() T (value: T) => boolean, T, , true. where();
- reduce() T T (x: T, y: T) => T. reduce() T. fold(), collect(), accumulate(), aggregate();
- any() T (value: T) => boolean. true, ;
- all() T (value: T) => boolean. true, ;
- none() T (value: T) => boolean. true, ;
- take() T n. , n . limit();
- drop() T n. , , n. skip();
- zip() T U, , T U, , .
Existem muitos outros algoritmos para classificar, reverter, dividir e concatenar sequências. Felizmente, esses algoritmos são tão úteis e aplicáveis em tantas áreas que você não precisa implementá-los sozinho. Para a maioria das linguagens de programação, existem bibliotecas com implementações prontas. JavaScript tem pacotes underscore.js e lodash, cada um com muitos algoritmos semelhantes. (No momento em que este artigo foi escrito, essas bibliotecas não suportavam iteradores - apenas o array JavaScript integrado e os tipos de objeto.) Em Java, eles podem ser encontrados no pacote java.util.stream. Em C #, eles estão localizados no namespace System.Linq. Em C ++, no arquivo de cabeçalho da biblioteca padrão <algrithm>.
10.2.1. Algoritmos em vez de loops
Você pode se surpreender, mas há uma boa regra prática: sempre que escrever um algoritmo, verifique se há um algoritmo de biblioteca ou pipeline para a tarefa. Os loops são geralmente escritos para processar sequências - exatamente o que os algoritmos discutidos acima fazem.
Algoritmos de biblioteca são preferidos em vez de loops personalizados porque há menos chance de erro. Os algoritmos de biblioteca são comprovados e implementados de forma eficiente e podem ser usados para tornar o código mais legível, especificando operações explicitamente.
Vimos várias implementações neste livro para entender melhor os aspectos internos, mas raramente você precisa implementar os algoritmos sozinho. Se você se deparar com uma tarefa que está além do poder dos algoritmos existentes, é melhor criar uma implementação genérica e reutilizável do que uma única especializada.
10.2.2. Implementando uma tubulação de fluido
A maioria das bibliotecas fornece uma API fluida para algoritmos de pipelining. APIs fluidas são APIs encadeadas que tornam seu código muito mais fácil de ler. Vejamos a diferença entre uma API fluida e uma API não fluida usando o pipeline de filtro / convolução da Seção 10.1.4 (Listagem 10.8) como exemplo.
E embora primeiro apliquemos a operação filter () e depois passemos o resultado para a operação reduce (), quando lermos o código da esquerda para a direita, veremos reduce () antes de filter (). Também é muito difícil descobrir quais argumentos se referem a uma função específica em um pipeline. A API fluida torna seu código muito mais fácil de ler.
Atualmente, todos os nossos algoritmos tomam um objeto iterável como o primeiro argumento e retornam um iterador. A programação orientada a objetos melhorará nossa API. É possível coletar todos os nossos algoritmos em uma classe de wrapper iterável. Em seguida, chame qualquer um dos iteráveis sem especificá-lo explicitamente como o primeiro argumento, porque agora o iterável é um membro da classe. Faremos isso para map (), filter () e reduce (), agrupando-os em uma nova classe FluentIterable <T> que envolve um objeto Iterable, conforme mostrado na Listagem 10.9.
Com base no Iterable <T>, podemos criar um FluentIterable <T>, para que possamos reescrever nosso filtro / reduzir o pipeline para ser mais fluido. Vamos criar um objeto FluentIterable <T>, chamar filter () nele, criar um novo objeto FluentIterable <T> com base em seus resultados e chamar a redução () nele, conforme mostrado na Listagem 10.10.
Agora, filter () vem antes de reduz (), e está bem claro que os argumentos se referem a esta função. O único problema é a necessidade de criar um novo FluentIterable <T> após cada chamada de função. Você pode melhorar esta API reescrevendo as funções map () e filter () para retornar um FluentIterable <T> em vez de um IterableIterator <T>. Observe que você não precisa alterar o método reduce () porque reduce () retorna um único valor do tipo T, não um iterável.
Mas, como estamos usando geradores, não podemos simplesmente alterar o tipo de retorno. A razão de ser dos geradores é fornecer uma sintaxe conveniente para funções, mas eles sempre retornam um IterableIterator <T>. Em vez disso, podemos mover as implementações para dois métodos privados, mapImpl () e filterImpl (), e converter de IterableIterator <T> para FluentIterable <T> nos métodos map () e filter () públicos, conforme mostrado na Listagem 10.11.
Essa implementação aprimorada torna mais fácil encadear algoritmos porque todos eles agora retornam um FluentIterable em que todos os algoritmos são descritos como métodos, conforme mostrado na Listagem 10.12.
Agora, nesta versão verdadeiramente fluida, o código é fácil de ler da esquerda para a direita e a sintaxe para concatenar qualquer número de algoritmos que compõem o pipeline parece bastante natural. Uma abordagem semelhante é usada na maioria das bibliotecas algorítmicas, tornando o mais fácil possível encadear vários algoritmos.
Dependendo da linguagem de programação, uma das desvantagens das APIs Fluent é desorganizar a classe FluentIterable com métodos para todos os algoritmos, dificultando a extensão. Se estiver incluído na biblioteca, o código de chamada não terá como adicionar um novo algoritmo sem modificar a classe. C # tem os chamados métodos de extensão que permitem adicionar métodos a uma classe ou interface sem ter que modificar seu código. No entanto, nem todos os idiomas possuem esses recursos. No entanto, na maioria dos casos, é melhor usar uma biblioteca existente de algoritmos do que implementar uma nova do zero.
10.2.3. Exercícios
- Estenda a classe FluentIterable para incluir um algoritmo take () que retorna os primeiros n elementos do iterador.
- Estenda a classe FluentIterable para incluir um algoritmo drop () que ignora os primeiros n elementos do iterador e retorna todo o resto.
10.3. Limitando tipos de parâmetros
Já vimos como estruturas de dados genéricas definem uma forma de dados que não depende de um parâmetro de tipo específico T. Também vimos um conjunto de algoritmos que usam iteradores para processar sequências de valores do tipo T, independentemente de qual tipo isso é. Agora, na Listagem 10.13, considere um cenário em que um determinado tipo de dados é importante: uma função genérica renderAll () que recebe um Iterable <T> como argumento e chama render () em cada elemento retornado pelo iterador.
A tentativa de compilar esta função termina com a seguinte mensagem de erro: Propriedade 'render' não existe no tipo 'T' (tipo 'T' está faltando a propriedade 'render').
Estamos tentando chamar o método render () de um tipo genérico T, que pode não ter tal método. Nesse cenário, você precisaria restringir o tipo T apenas às encarnações específicas que contêm o método render ().
Limitações de tipos de parâmetro
As restrições informam ao compilador sobre os recursos que um tipo de argumento deve ter. Sem restrições, o tipo de argumento pode ser qualquer coisa. Quando é necessário que um tipo de dado genérico tenha certos membros de classe, é com a ajuda de restrições que reduzimos o conjunto de tipos permitidos para aqueles que têm esses membros necessários.
Em nosso caso, podemos definir a interface IRenderable, que declara o método render (), conforme mostrado na Listagem 10.14. Você pode então adicionar uma restrição no tipo de T usando a palavra-chave extends para dizer ao compilador que apenas os tipos de argumento que incorporam IRenderable são permitidos.
10.3.1. Estruturas de dados genéricos restritos
A maioria das estruturas de dados genéricas não requer restrições de tipo de parâmetro. Qualquer tipo de valor pode ser armazenado em uma lista, árvore e array encadeados. No entanto, existem algumas exceções, em particular o conjunto com hash.
A estrutura de dados do conjunto modela o conjunto em um sentido matemático, de modo que valores únicos são armazenados nele e as duplicatas são descartadas. As estruturas de dados do conjunto normalmente incluem métodos para unir, cruzar e subtrair de outros conjuntos, e também permitindo que você verifique se um determinado valor está incluído em um conjunto. Para realizar esta verificação, você pode comparar este valor com cada um dos elementos do conjunto, embora esta não seja uma abordagem muito eficiente. No pior dos casos, a comparação com cada um dos elementos do conjunto requer percorrer todo o conjunto. Essa travessia é realizada em tempo linear, O (n). Você pode revisar essas notações na barra lateral “Notação Big O”, abaixo.
A implementação mais eficiente é fazer o hash de todos os valores e armazená-los em uma estrutura de dados de valor-chave, como um mapa de hash ou dicionário. Estruturas como essas são mais eficientes, podem recuperar valores em tempo constante , O (1). O conjunto hash envolve o mapa hash, fornecendo uma verificação eficiente para a inclusão de um elemento. Mas tem uma limitação: o tipo T deve fornecer uma função hash que recebe um valor do tipo T e retorna seu valor hash do tipo número.
Em algumas linguagens de programação, o hash de todos os valores é possível ao descrever o método de hash no tipo superior. Por exemplo, o tipo de objeto Java superior inclui um método hashCode () e o tipo de objeto C # superior inclui o método GetHashCode (). Mas se a linguagem não oferece essa possibilidade, então uma restrição de tipo é necessária para que apenas os tipos que podem ser hash possam ser armazenados em nossas estruturas de dados. Por exemplo, podemos definir a interface IHashable e usá-la como uma restrição de tipo no tipo de chave de nosso hashmap ou dicionário genérico.
Sobre o autor
Vlad Rishkutsia é um especialista em desenvolvimento de software na Microsoft com mais de dez anos de experiência. Durante esse tempo, ele gerenciou vários projetos de software importantes e treinou muitos jovens profissionais.
Mais detalhes sobre o livro podem ser encontrados no site da editora
» Índice
» Trecho
Para Habitantes desconto de 25% no cupom - TypeScript
Mediante o pagamento da versão em papel do livro, é enviado um e-book por e- correspondência.