Embed Size (px)
Citation preview
Programação Funcional em OCaml
José Romildo Malaquias
BCC222: Programação Funcional
Universidade Federal de Ouro PretoDepartamento de Computação
2015–1
Sumário
1 OCaml 1-11.1 A linguagem OCaml . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1-1
1.1.1 História de OCaml . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1-11.1.2 Características de OCaml . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1-21.1.3 Por que OCaml? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1-21.1.4 Usos e Aplicações . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1-2
1.2 O Sistema OCaml . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1-31.2.1 Ferramentas da distribuição OCaml . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1-31.2.2 O ambiente interativo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1-31.2.3 Pacotes e bibliotecas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1-31.2.4 Editores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1-4
1.3 Instalação das ferramentas de desenvolvimento em OCaml . . . . . . . . . . . . . . . . . . . . 1-41.3.1 Instalação do OCaml no Windows: Instalador oficial . . . . . . . . . . . . . . . . . . . 1-41.3.2 Instalação do OCaml no Windows: WODI . . . . . . . . . . . . . . . . . . . . . . . . 1-61.3.3 Instalação do OCaml no Ubuntu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1-141.3.4 Instalação do ambiente interativo no Eclipse . . . . . . . . . . . . . . . . . . . . . . . . 1-14
1.4 Usando o ambiente interativo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1-17
2 Valores, Tipos e Funções 2-12.1 Considerações léxicas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2-1
2.1.1 Comentários . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2-12.1.2 Palavras reservadas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2-12.1.3 Identificadores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2-2
2.2 Alguns tipos básicos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2-22.3 Constantes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2-32.4 Aplicação de função . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2-42.5 Definindo variáveis e funções . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2-62.6 Tipos função . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2-72.7 Checagem de tipos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2-72.8 Inferência de tipos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2-82.9 Exercícios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2-8
3 Expressão Condicional 3-13.1 Expressão condicional . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3-13.2 Definição de função com expressão condicional . . . . . . . . . . . . . . . . . . . . . . . . . . 3-2
4 Definições Locais 4-14.1 Expressão let . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4-14.2 Exercícios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4-3
5 Funções Recursivas 5-15.1 Recursividade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5-15.2 Recursividade mútua . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5-45.3 Recursividade de cauda . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5-55.4 Vantagens da recursividade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5-7
6 Tuplas, Listas, e Polimorfismo Paramétrico 6-16.1 Tuplas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6-16.2 Listas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6-26.3 Polimorfismo paramétrico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6-4
6.3.1 Operação sobre vários tipos de dados . . . . . . . . . . . . . . . . . . . . . . . . . . . 6-46.3.2 Variáveis de tipo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6-46.3.3 Valor polimórfico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6-56.3.4 Instanciação de variáveis de tipo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6-5
2
6.4 Funções polimórficas predefinidas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6-5
7 Casamento de Padrão 7-17.1 Casamento de padrão . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7-1
7.1.1 Casamento de padrão . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7-17.1.2 Padrão constante . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7-27.1.3 Padrão variável . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7-27.1.4 Padrão curinga . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7-27.1.5 Padrão tupla . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7-27.1.6 Padrões lista . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7-37.1.7 Padrões combinados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7-47.1.8 Padrões faixa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7-57.1.9 Padrões nomeados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7-5
7.2 Casamento de padrão em definições com let . . . . . . . . . . . . . . . . . . . . . . . . . . . 7-67.3 Definição de função usando padrões . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7-67.4 Expressão de Seleção Múltipla . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7-7
7.4.1 Forma e regras de tipo da expressão match . . . . . . . . . . . . . . . . . . . . . . . . 7-87.4.2 Avaliação de expressões match . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7-87.4.3 Exemplos de expressões match . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7-87.4.4 Expressão match com guardas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7-11
7.5 Exercícios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7-11
8 OcaIDE 8-18.1 OcaIDE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8-18.2 Desenvolvimento de projetos Ocaml . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8-2
9 Programas Interativos 9-19.1 Interação com o mundo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9-19.2 Expressão sequência . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9-1
9.2.1 Ignorando o resultado de uma expressão . . . . . . . . . . . . . . . . . . . . . . . . . . 9-29.2.2 Blocos de programa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9-2
9.3 Estrutura de um programa em OCaml . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9-29.4 Canais de entrada e saída . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9-59.5 Funções de saída na saída padrão . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9-59.6 Funções de saída na saída de erro padrão . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9-69.7 Funções de entrada na entrada padrão . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9-69.8 Exercícios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9-6
10 Valores Aleatórios 10-110.1 Valores aleatórios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10-110.2 Jogo adivinha o número . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10-210.3 Jogo craps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10-610.4 Jogo nim . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10-7
11 Expressões Lambda 11-111.1 Valores de primeira classe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11-1
11.1.1 Valores de primeira classe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11-111.1.2 Valores de primeira classe: Literais . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11-111.1.3 Valores de primeira classe: Variáveis . . . . . . . . . . . . . . . . . . . . . . . . . . . 11-211.1.4 Valores de primeira classe: Argumentos . . . . . . . . . . . . . . . . . . . . . . . . . . 11-211.1.5 Valores de primeira classe: Resultado . . . . . . . . . . . . . . . . . . . . . . . . . . . 11-211.1.6 Valores de primeira classe: Componentes . . . . . . . . . . . . . . . . . . . . . . . . . 11-3
11.2 Expressão lambda . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11-311.2.1 Expressões lambda with fun . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11-311.2.2 Exemplos de expressões lambda . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11-311.2.3 Uso de expressões lambda . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11-411.2.4 Exercícios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11-411.2.5 Expressões lambda with function . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11-5
11.3 Aplicação parcial de funções . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11-511.3.1 Aplicação parcial de funções . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11-511.3.2 Aplicação parcial de funções: exemplos . . . . . . . . . . . . . . . . . . . . . . . . . . 11-6
11.4 Currying . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11-711.4.1 Funções curried . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11-7
3
11.4.2 Por que currying é útil? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11-811.4.3 Convenções sobre currying . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11-8
11.5 Utilidade de expressões lambda . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11-811.5.1 Exercícios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11-9
12 Funções de Ordem Superior 12-112.1 Funções de Ordem Superior . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12-112.2 Composição de funções . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12-112.3 A função List.filter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12-212.4 A função map . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12-312.5 fold_left . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12-312.6 fold_right . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12-412.7 Cupom fiscal do supermercado . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12-5
13 Tipos Algébricos 13-113.1 Novos tipos de dados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13-113.2 Tipos variantes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13-213.3 Exemplo: formas geométricas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13-2
4
1 OCaml
ResumoAs atividades de programação serão desenvolvidas usando a linguagem OCaml (http://www.
ocaml.org/).Nesta aula o aluno será apresentado à linguagem OCaml, passando a conhecer suas principais
características. Serão apresentados os passos necessários para instalar o sistema de programação emOCaml e as principais ferramentas utilizadas durante o processo de desenvolvimento em OCaml.
Haverá oportunidade de familiarização com o ambiente de programação em OCaml através daavaliação de expressões no ambiente interativo e compilação em batch.
Sumário1.1 A linguagem OCaml . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1-1
1.1.1 História de OCaml . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1-11.1.2 Características de OCaml . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1-21.1.3 Por que OCaml? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1-21.1.4 Usos e Aplicações . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1-2
1.2 O Sistema OCaml . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1-31.2.1 Ferramentas da distribuição OCaml . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1-31.2.2 O ambiente interativo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1-31.2.3 Pacotes e bibliotecas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1-31.2.4 Editores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1-4
1.3 Instalação das ferramentas de desenvolvimento em OCaml . . . . . . . . . . . . . . . . . . 1-41.3.1 Instalação do OCaml no Windows: Instalador oficial . . . . . . . . . . . . . . . . . . . 1-41.3.2 Instalação do OCaml no Windows: WODI . . . . . . . . . . . . . . . . . . . . . . . . 1-61.3.3 Instalação do OCaml no Ubuntu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1-141.3.4 Instalação do ambiente interativo no Eclipse . . . . . . . . . . . . . . . . . . . . . . . . 1-14
1.4 Usando o ambiente interativo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1-17
1.1 A linguagem OCaml
1.1.1 História de OCamlML é uma família muito grande de linguagens de programação que inclui Satandard ML, OCaml, F#, SML#,
Manticore, MetaOCaml, JoCaml, Alice ML, Dependent ML, Flow Caml, e muitas outras. Todas as linguagensML compartilham várias características fundamentais, além de uma boa dose de sintaxe. Elas são de ordemsuperior, estritas, na maior parte puras, e tipadas, com tipos algébricos e outros tipos de dados. Seus sistemas detipo são derivados de Hindley-Milner. O desenvolvimento dessas linguagens inspirou um conjunto significativode pesquisas em Ciência da Computação e influenciou a concepção de muitas outras linguagens de programação,incluindo Haskell, Scala e Clojure, Rust, ATS e muitas outras.
OCaml1 é uma linguagem de programação de uso geral, com ênfase na expressividade e segurança. De-senvolvida há mais de 20 anos no INRIA2 por um grupo de pesquisadores líderes, OCaml beneficia-se de umdos sistemas de tipos mais avançados e suporta os estilos de programação funcional, imperativo e orientado aobjetos, que facilitam o desenvolvimento de um software flexível e confiável. Usado em ambientes onde umúnico erro pode custar milhões e onde velocidade é importante, OCaml é apoiada por uma comunidade ativa quedesenvolveu um rico conjunto de bibliotecas e irá ajudá-lo a tirar o máximo de possibilidades de OCaml.
OCaml é uma linguagem de programação moderna, de alto nível, com muitos recursos úteis. É um produtode código aberto de mais de vinte anos de pesquisa de ponta que permite o desenvolvimento rápido de softwarerobusto, conciso e correto.
1http://www.ocaml.org2Institut National de Recherche en Informatique et en Automatique.
1-1
OCaml começou com a ML original criada na universidade de Edinburgo por Robin Milner, no começoda década de 1970. ML significa Meta Language pois ela foi feita para funcionar como a meta-linguagem doprovador de teoremas LCF.
Os primeiros usuários de ML perceberam que ela funcionava bem para programar outras coisas, então ela foiseparada do seu sistema de origgem.
Várias variações de ML foram desenvolvidas em universidades e institutos da Europa. No INRIA3 Pierre-Louis Curien criou a Categorial Abstract Machine (CAM), uma máquina virtual e modelo de computação ade-quado para execução de linguagens funcionais.
Gérard Huet e outros pesquisadores criaram uma versão de ML usando a máquina CAM, e a chamaram deCAML, em meados da década de 1980.
Como o código executado por CAML era lento e usava muita memória, Xavier Leroy e Damien Doligezcriaram Caml Light no início da década de 1990, muito mais rápida e compacta.
A linguagem foi estendida na década de 1990 para incluir suporte a orientação a objetos, resultando emObjective Caml.
Em 2011 o nome foi mudado para OCaml.
1.1.2 Características de OCaml• Estaticamente tipada
• Inferência de tipos
• Orientada a expressões
• Compilação nativa ou para bytecode
• Uso interativo ou em batch
• Tipos algébricos e casamento de padrão
• Módulos
• Objetos e classes
• Avaliação estrita
1.1.3 Por que OCaml?• Aprendizagem de um novo paradigma de programação.
• Desempenho e expressividade
Programas escritos em OCaml tendem a ter desempenho mais próximo de linguagens como C++, mas comcódigo mais sucinto, geralmente mais próximo de linguagens como Python e Ruby.
1.1.4 Usos e AplicaçõesOCaml não é somente experimental. Existem aplicações de complexidade e tamanho significativos escritos
em OCaml. Estas aplicações tendem a ser de domínios realativamente complexos ou que usam pesquisas deponta. Algumas delas funcionam em ambientes que requer alta confiabilidade.
• Jane Street Capital empresa financeira especializada na compra e venda de produtos financeitos em altafrequência (Hight-Speed Trading).
• Coq sistema assistente para provas que pode ser usado
– para auxílio na prova de teoremas matemáticos (e verificar as provas criadas),
– para verificação de outros sistemas de software (provar que um programa segue sua especificação), e
– como sistema de programação, para criar os chamados produtos certificados.
• Mirage OS sistema operacional criado especificamente para a computação em nuvens.
• Microsoft criou o projeto SLAM que resultou na ferramenta SDV (Static Driver Verifier) para verificaçãode drivers.
• Facebook compilador da linguagem Hack e algumas ferramentas internas.
3O INRIA (Institute national de recherche en informatique et en automatique) é uma organização pública francesa de carácter científicoe tecnológico.
1-2
1.2 O Sistema OCaml
Para o desenvolvimento de aplicações em OCaml é necessário o compilador de OCaml e um conjunto debibliotecas. A distribuição de OCaml oferece dois compiladores:
• ocamlc: um compilador para bytecode
• ocamlopt: um compilador nativo
Existe também um ambiente interativo (ocaml) onde o programador pode carregar módulos e avaliar expressões,facilitando o desenvolvimento incremental.
Para preparar os programas é necessário um editor de texto e um terminal, ou um ambiente de desenvolvi-mento integrado (IDE).
O desenvolvimento baseado na linha de comando usa um terminal e um editor de textos. O programador digitaos arquivos fontes em um editor de texto e compila a aplicação em um terminal executando um dos compiladores.
Emacs (juntamente com o plugin Tuareg) é um bom editor de texto com facilidades para desenvolvimento emOCaml. Porém o grau de dificuldade de sua aprendizagem é considerado elevado. Emacs está disponível para amaioria das platformas, incluindo Linux e Windows.
Notepad++ é uma opção mais simples disponível no Windows. No Linux temos outras opções como o gedit(parte do ambiente GNOME) e o kate (parte do ambiente KDE).
Eclipse é um ambiente de desenvolvimento integrado muito usado com várias linguagens de programaçãocomo Java e C++. O plugin OcaIDE oferece suporte para desenvolvimento em OCaml no Eclipse.
1.2.1 Ferramentas da distribuição OCaml
• ocamlc: compilador para bytecode.
• ocamlopt: compilador para código nativo.
• ocaml: ambiente interativo.
• ocamldoc: gerador de documentação baseado em comentários.
• ocamlbuild: ferramenta para compilação de projetos OCaml.
• ocamldep: analisador de dependências entre módulos, geralmente usado para determinar a ordem de com-pilação dos arquivos.
• ocamllex e ocamlyacc: geradores de analisadores léxicos e sintáticos, usados principalmente na criaçãode compiladores e interpretadores para linguagens de programação.
• ocamlmktop: possibilita a criação de ambientes interativos customizados para OCaml.
1.2.2 O ambiente interativo
O REPL (Read Eval Print Loop) lê declarações e expressões digitadas pelo usuário, compila-as para byte-code, e executa-as. Ele é útil para testar e explorar novas idéias.
O ambiente interativo padrão (ocaml) tem algumas deficiências, como por exemplo a edição da entrada ébastante básica e não há suporte para um histórico de linhas digitadas. Sugere-se adicionar estas capacidadesusando utilitários como ledit ou rlwrap. Pode-se também usar o ambiente interativo alternativo utop, que ébastante melhorado.
1.2.3 Pacotes e bibliotecas
• findlib: ferramenta para instalação, gerenciamento e uso de bibliotecas usando a ferramenta ocamlfind.
• OPAM (OCaml Package Manager): sistema de gerenciamento de pacotes avançado com resolução dedependência. Ainda não disponível para Windows.
1-3
1.2.4 Editores
Vários editores suportam a linguagem OCaml, como por exemplo:
• Emacs
• VIM
• Sublime Text
• Textmate
• Atom
1.3 Instalação das ferramentas de desenvolvimento em OCaml
O compilador de OCaml e suas bibliotecas podem ser instalados de várias maneiras. As mais usadas são:
• usando OPAM, um gerenciador de pacotes específicos para OCaml (ainda não disponível para Windows),
• usando um gerenciador de pacotes suportado para sua plataforma, ou
• a partir do código fonte.
A página Install OCaml4 apresenta maiores detalhes.
1.3.1 Instalação do OCaml no Windows: Instalador oficial
Há várias maneiras de instalar OCaml no Windows. Vamos usar o instalador oficial, disponível na páginahttp://protz.github.com/ocaml-installer/.
1. Faça o donwload da versão mais recente do programa de instalação disponível na página http://protz.github.io/ocaml-installer/. No momento em que estas instruções foram escritas a versão mais re-cente era para OCaml-4.01.0, acessível pelo link http://gallium.inria.fr/~protzenk/caml-installer/ocaml-4.01.0-i686-mingw64-installer3.exe.
2. Execute o programa de instalação, que poderá instalar:
• OCaml, findlib e flexdll.
• Emacs (opcional), um editor de texto, com suporte para OCaml.
• ActiveTCL (opcional), uma biblioteca para aplicações com interface gráfica. Necessário para usarOCamlBrowser ou para criar aplicações com interface gráfica usando Tcl/Tk (labltk).
• Cygwin (opcional), uma coleção de ferramentas que permitem que o Windows possa de certa formaagir como um sistema Unix. Necessário para compilação nativa de programas em OCaml. O pro-grama de instalação do Cygwin será executado com os pacotes necessários ao OCaml previamenteselecionados.
Certifique-se de habilitar a instalação do Cygwin.
4http://ocaml.org/docs/install.html
1-4
O ambiente interativo poderá ser executado usando o item OCamlWin no menu de programas. Será abertauma janela onde você pode avaliar expressões e declarações.
Para desenvolver um programa, edite o texto do programa em um editor de texto, como o Notepad++:
Em seguida compile o programa no terminal:
1-5
E execute o programa no terminal:
1.3.2 Instalação do OCaml no Windows: WODI
Esta é uma forma alternativa de instalar OCaml no Windows.
GODI5 é um sistema de gerenciamento de pacotes baseada em código fonte para o ecossistema OCaml. Elefornece um método fácil e consistente de configuração, construção, instalação, atualização e remoção de softwarenecessária para os desenvolvedores OCaml: O próprio compilador OCaml e uma grande lista de bibliotecas eferramentas de desenvolvimento.
WODI6 é uma adapatação extendida de GODI para Windos. Seu sistema de compilação e pacotes ferramentasde empacotamento são baseadas no Cygwin, mas as bibliotecas e programas são compilados com mingw-w64 eOCaml, sendo independentes do Cygwin.
É recomendado instalar WODI como usuário normal, não como administrador. É mais fácil manter WODI sevocê tem acesso completo à gravação dentro do seu ambiente cygwin. WODI deve ser instalado em uma pastaque não contém quaisquer caracteres em branco em seu nome.
1. Faça o donwload da versão mais recente do programa de instalação disponível na página http://wodi.forge.ocamlcore.org/download.html. No momento em que estas instruções foram escritas a ver-são mais recente era para OCaml-4.02.1, acessível pelo link http://ml.ignorelist.com/wodi/8/wodi32.exe para sistemas de 32 bits, ou pelo link http://ml.ignorelist.com/wodi/8/wodi64.exepara sistemas de 64 bits.
2. Execute o programa de instalação. Primeiro o instalador irá criar um ambiente Cygwin personalizado e,em seguida, instalar OCaml e programas como findlib. Você pode baixar as bibliotecas e os programasadicionais mais tarde, com o gerenciador de pacotes WODI.
Ferramentas baseadas Cygwin são necessários para WODI, para ocamlbuild, e para a compilação de pro-gramas fonte OCaml para código nativo. Você não pode usar WODI sem Cygwin. Cygwin será baixadoda internet durante a instalação.
5http://godi.camlcity.org/6http://wodi.forge.ocamlcore.org/
1-6
1-7
1-8
1-9
1-10
1-11
O ambiente interativo poderá ser executado de diferentes maneiras a partir do menu Wodi64:
• Usando o terminal do Cygwin: Wodi64 Cygwin. No terminal digite o comando rlwrap ocaml.
• Usando o editor ocaml-top.
1-12
• Usando a ferramenta ocamltop-win.
Para compilar um programa, edite o texto do programa em um editor de texto, como por exemplo o Note-pad++:
Em seguida compile e execute o programa no terminal do Cygwin:
1-13
1.3.3 Instalação do OCaml no Ubuntu
OCaml é muito fácil de ser instalado no Ubuntu. Use o gerenciador de pacotes para instalar os seguintespacotes:
• ocaml, para desenvolvimento de aplicações
• ocaml-native-compilers, para compilação de programas para código nativo
• ocaml-doc, para ter acesso ao manual de referência
• tuareg-mode, um plugin para o editor Emacs
• ocaml-findlib, para instalar e usar bibliotecas e suas dependências facilmente
• menhir, um gerador de analisadores sintáticos
• rlwrap, para facilitar a edição da linha de entrada do ambiente interativo,
1.3.4 Instalação do ambiente interativo no Eclipse
Para instalar OcaIDE, um plugin para Eclipse:
1. Instale a máquina virtual do Java versão 1.7 ou superior (http://java.com/en/download/index.jsp).
2. Instale uma versão recente do Eclipse (http://www.eclipse.org/downloads/).
3. Inicie o Eclipse.
4. No Eclipse acesse o menu Help→Install New Software....
1-14
5. Clique Add para configurar um novo repositório.
6. No campo Name digite OcaIDE e no campo Location digite http://www.algo-prog.info/ocaide/.
7. Clique em Ok.
8. Selecione a categoria OcaIDE na lista de plugins.
1-15
9. Clique Next.
10. Clique Next.
11. Aceite os termos do acordo de licença.
12. Clique Finish. Será feito o download do plugin.
13. Aceite a instalação (o plugin não tem assinatura digital).
14. Reinicie o Eclipse quando solicitado.
15. Após o reinício do Eclipse, o ambiente já está pronto para uso.
16. Para acessar a ajuda online clique no menu Help→Help Contents e escolha OCaml Development UserGuide na lista de tópicos disponíveis.
17. Verifique os caminhos onde o OCaml pode ser encontrado. Para tanto acesse o menu Window→Preferencese selecione a aba OcaIDE→Paths. Se necessário preencha o campo Ocaml Binaires Directory parainidicar a localização correta dos programas executáveis do OCaml e em seguida clique em Apply. Podeser necessário indicar também o caminho das bibliotecas do OCaml no campo Ocaml lib path. Concluaclicando em OK.
1-16
1.4 Usando o ambiente interativo
No ambiente interativo do OCaml podemos digitar expressões e declarações da linguagem OCaml. Elas sãocompiladas e avaliadas, e o tipo e o valor obtido são exibidos.
O ambiente interativo padrão pode ser iniciado a partir de um terminal usando o comando ocaml.Em um sistema Unix:
$ ocamlOCaml version 4.01.0
#
Para adicionar facilidades de edição da linha de entrada e histórico, use os utilitários ledit ou rlwrap:Em um sistema Unix:
$ rlwrap ocamlOCaml version 4.01.0
#
1-17
Expressões da linguagem OCaml podem ser digitadas no prompt. A entrada deve ser encerrada com doissinais de ponto-e-vírgula: ;;.
Por exemplo:
# 2 + 3*4;;- : int = 14
# (2 + 3)*4;;- : int = 20
# print_string "Hello, world!\n";;Hello, world!- : unit = ()
Observe que o ambiente interativo responde informando o tipo e o valor calculados.Para encerrar o ambiente interativo use a diretiva #quit ou digite Control+D (no Linux) ou Control+Z (no
Windows).Para mudar o diretório atual use a diretiva #cd "nome-do-diretório".Para ler, compilar e executar expressões e declarações de um dado arquivo use a diretiva #use "nome-do-arquivo".
1-18
2 Valores, Tipos e Funções
ResumoAs linguagens funcionais modernas apresentam um sistema de tipos robusto que permite ao com-
pilador verificar se os operandos usados nas operações estão corretos. Com a inferência de tipos istopode ser feito sem o programador ter que necessariamente anotar os tipos das variáveis e funçõesusadas nos programas.
Nesta aula vamos conhecer alguns tipos básicos de OCaml.
Sumário2.1 Considerações léxicas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2-1
2.1.1 Comentários . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2-12.1.2 Palavras reservadas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2-12.1.3 Identificadores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2-2
2.2 Alguns tipos básicos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2-22.3 Constantes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2-32.4 Aplicação de função . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2-42.5 Definindo variáveis e funções . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2-62.6 Tipos função . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2-72.7 Checagem de tipos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2-72.8 Inferência de tipos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2-82.9 Exercícios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2-8
2.1 Considerações léxicas
2.1.1 ComentáriosComentários são usados para fazer anotações no programa que podem ajudar a entender o funcionamento
do mesmo. Os comentários são ignorados pelo compilador.Comentários são delimitados por (* e *) . Comentários podem ser aninhados. Comentários não podem
ocorrer em literais caracter e literais string.
2.1.2 Palavras reservadasAs seguintes palavras são reservadas e não podem ser usadas como identificadores:
and as assert asr begin classconstraint do done downto else endexception external false for fun functionfunctor if in include inherit initializerland lazy let lor lsl lsrlxor match method mod module mutablenew object of open or privaterec sig struct then to truetry type val virtual when whilewith
As seguintes sequências de caracteres também são reservadas:
!= # & && ’ ( ) * + , --. -> . .. : :: := :> ; ;; <<- = > >] >} ? [ [< [> [| ]_ ‘ { {< | |] || } ~
2-1
2.1.3 Identificadores
Identificadores são usados para nomear elementos em um programa. São formados por uma sequência deletras, dígitos decimais, sublinhado (_) e apóstrofo (’) começando com uma letra ou sublinhado, e não pode seruma palavra reservada.
São exemplos de identificadores:
pesoaltura_alunoEstruturanome3x’__conceito
Não são identificadores:
7anosnome-do-professorlet
2.2 Alguns tipos básicos
Um tipo é uma coleção de valores relacionados. Tipos servem para classificar os valores de acordo com assuas características.
Em OCaml nomes de tipo são sequências de letras, dígitos decimais, sublinhados e apóstrofo, começandocom uma letra minúscula ou sublinhado.
Por exemplo, o tipo bool contém os dois valores lógicos false e true, comumente usados nas operaçõeslógicas.
Alguns tipos básicos de OCaml são apresentados a seguir.
2-2
tipo características exemplos de va-lores
algumas ope-rações
int – inteiros de precisão fixa– limitado, sendo a faixa de valores deter-
minada pelo tamanho da palavra da plata-forma:
– 32 bits: de −230 até 230 − 1
– 64 bits: de −262 até 262 − 1
77038767_703_876-186050b1001010o20120x2FA3
+-*/modmin_intmax_int
float – aproximação de números reais em pontoflutuante
– precisão dupla de acordo com o padrãoIEEE 754, com 53 bits de mantissa e ex-poente de −1022 até 1023
78643-78643-7.893_001_999418..2015.987.3201E-6034e8
+.-.*.**ceilfloorsqrtexploglog10sincostanasinacosatan
bool – valores lógicos falsetrue
not&&||=<><<=>>=
char – enumeração cujos valores representam ca-racteres ISO 8859-1
– representados internamente como inteirosde 8 bits entre 0 e 255
’B’’!’’\n’’\t’’\066’’\x42’
string – sequências finitas de caracteres "Brasil""""bom\ndia"
^lengthgetuppercaselowercase
unit – possui um único valor: a tupla vazia– útil para expressões que são avaliadas ape-
nas pelo efeito que produzem, não tendoum valor interessante para ser o resultado
()
Diferentemente da maioria das linguagens de programação, os literais, as funções e os operadores para ostipos numéricos não são sobrecarregados. Assim o literal 2342 é somente do tipo int e nunca do tipo float.O operador + pode ser usado apenas com inteiros, e nunca com números em ponto flutuante. Para números emponto flutuante existe o operador +..
2.3 Constantes
As formas mais simples de expressões são as constantes. Elas representam valores em sua forma mais simples,ou seja, já estão reduzidos à sua forma canônica.
São constantes:
• os literais inteiros, fracionários, caracteres e strings,
2-3
• os construtores constantes dos tipos algébricos,
• as constantes especiais false, true, () (tupla vazia), [] (lista vazia), e [||] (array vazio), e
• begin end, que é equivalente a ().
Algumas destas constantes somente serão apresentadas posteriormente.
2.4 Aplicação de função
Aplicação de função é uma das formas de expressões mais comuns na programação funcional, uma vez queos programas são organizados em funções.
Sintaticamene uma aplicação de função em notação prefixa consiste em escrever a função seguida dos argu-mentos, se necessário separados por caracteres brancos (espaços, tabuladores, mudança de linha, etc.).
Exemplos:
# sqrt 25.0;;- : float = 5.# cos 0.0;;- : float = 1.# exp 1.0;;- : float = 2.71828182845904509# compare "ana" "paula";;- : int = -1# max 18 501;;- : int = 501
Observe que, diferentemente de várias outras linguagens de programação, os argumentos não são escri-tos entre parênteses e nem separados por vírgula.
Parênteses podem ser usados para agrupar subexpressões. Por exemplo:
# sqrt (max 25.0 0.36);;- : float = 5.# min (sqrt 9.0) 0.81;;- : float = 0.81
Aplicações de função também podem ser escritas em notação infixa, onde a função é escrita entre os seusargumentos. Neste caso dizemos que as funções são operadores infixos. Os nomes dos operadores infixos sãosequências de caracteres simbólicos
! $ % & * + - . / : < = > ? @ ^ | ~
começando com um dos caracteres
= < > @ ^ | & + - * / $ %
tais como <=> e !!. Exemplos:
# 2 + 3;;- : int = 5# 10 / 4;;- : int = 2# (12 - 7) * 6;;- : int = 30# 6 <= 17;;- : bool = true# ’A’ = ’B’;;- : bool = false# ’A’ <> ’B’;;- : bool = true# true || false;;- : bool = true# true && false;;- : bool = false
2-4
Assim como na Matemática e em outras linguagens de programação, os operadores possuem um nível deprecedência (ou prioridade) e uma associativade. Parênteses podem ser usados para agrupar subexpressõesdentro de expressões maiores quebrando a precedência ou associatividade dos operadores.
A tabela 2.1 lista a precedência relativa e a associatividade dos operadores e outras construções de OCaml.O nível de precedência e associatividade de um operador infixo é determinado pelo seu primeiro caracter. Natabela 2.1 *... significa qualquer operador infixo começando com *.
operador ou construção associativadesímbolo prefixo -. -.(.[.{# -aplicação de função esquerdaaplicação de construtoraplicação de tagassertlazy- (prefixo) --. (prefixo)**... direitalsllsrasr*... esquerda/...%...modlandlorlxor+... esquerda-...:: direita@... direita^...=... esquerda<...>...|...&...$...!=& direita&&or direita||, -<- direita:=if -; direitalet -matchfunfunctiontry
Tabela 2.1: Precedências e associatividades dos operadores e construções de OCaml.
Exemplos:
2-5
# 2 + 3 * 4;; (* * tem maior precedência que + *)- : int = 14# 5.0 ** 2.0 -. 10.0;; (* ** tem maior precedência que -. *)- : float = 15.# 2.0 ** 3.0 ** 2.0;; (* ** associa-se à direita *)- : float = 512.
Aplicações de função em notação prefixa tem precedência maior do que todos os operadores. Exemplos:
# abs 10 - 20;; (* abs tem precedência maior que - *)- : int = -10# abs (10 - 20);;- : int = 10# succ 9 + max 5 4 * 3;; (* succ e max tem precedência maior que + e * *)- : int = 25
Um operador pode ser associativo à esquerda, associativo à direita, ou não-associativo. Quando dois opera-dores com a mesma precedência disputam um operando,
• se eles forem associativos à esquerda, o operador da esquerda é escolhido,
• se eles forem associativos à direita, o operador da direta é escolhido,
• se eles forem não associativos, a expressão é mal formada e contém um erro de sintaxe,
Exemplos:
# 15 - 4 - 6;; (* - associa-se à esquerda *)- : int = 5# 15 - (4 - 6);;- : int = 17# 10 - 2 + 5;; (* + e - tem a mesma precedência e associam-se à esquerda *)- : int = 13# 10 - (2 + 5);;- : int = 3# 2.0 ** 3.0 ** 4.0;; (* ** associa-se à direita *)- : float = 2.41785163922925835e+24
Qualquer operador infixo pode ser usado em notação prefixa, bastando escrevê-lo entre parênteses. Exemplos:
# (+) 4 5;;- : int = 9# (/.) 18.2 2.0;;- : float = 9.1# (>=) 10 20;;- : bool = false# sqrt ((+.) 4.1 4.9);;- : float = 3.
2.5 Definindo variáveis e funções
Além de poder usar as funções das bibliotecas, o programador também pode definir e usar suas própriasvariáveis e funções. Variáveis e funções são definidas usando a palavra reservada let.
Nomes de variáveis e funções são identificadores que que começam com letra minúscula ou sublinhado.Uma declaração global de variável é da forma:
let nome = expressão
sendo nome o nome da variável, e expressão uma expressão qualquer. Quando elaborada, esta declaração avaliaa expressão associando o seu valor ao nome indicado.
Exemplos:
2-6
# let idade = 21;;val idade : int = 21# let x = 2*idade - 1;;val x : int = 41# idade <= 30;;- : bool = true
Uma declaração global de função é da forma:
let nome par1 ... parn = expressão
sendo nome o nome da função, par1, . . . , parn (n > 0) os nomes dos parâmetros formais da função, e expressãoo corpo da função. Quando elaborada, esta declaração cria uma função associando-a ao nome indicado.
Exemplos:
# let dobro x = x + x;;val dobro : int -> int = <fun># dobro 5;;- : int = 10# let quadruplo x = dobro (dobro x);;val quadruplo : int -> int = <fun># quadruplo 5;;- : int = 20
2.6 Tipos função
Nas linguagens funcionais uma função é um valor de primeira classe e, assim como os demais valores, temum tipo. Este tipo é caracterizado pelos tipos dos argumentos e pelo tipo do resultado da função.
Em OCaml um tipo função é escrito usando o operador de tipo ->:
t1 -> ... -> tn
onde
• t1, . . . , tn−1 são os tipos dos argumentos
• tn é o tipo do resultado
Exemplos:
bool -> booltipo das funções com um argumento do tipo bool, e resultado do tipo bool, como por exemplo a funçãonot
bool -> bool -> booltipo das funções com dois argumentos do tipo bool, e resultado do tipo bool, como por exemplo osoperadores && e ||
int -> float -> float -> booltipo das funções com três argumentos, sendo o primeiro do tipo int, o segundo e o terceiro do tipo float,e o resultado do tipo bool
2.7 Checagem de tipos
Toda expressão sintaticamente correta tem o seu tipo calculado em tempo de compilação. Se não for possíveldeterminar o tipo de uma expressão ocorre um erro de tipo.
A aplicação de uma função a um ou mais argumentos de tipo inadequado constitui um erro de tipo. Porexemplo:
# not ’A’;;Error: This expression has type char but an expression was expected of type
bool
2-7
Explicação:A função not requer um valor booleano, porém foi aplicada ao argumento ’A’, que é um caracter.
OCaml é uma linguagem fortemente tipada, com um sistema de tipos muito avançado. Todos os possíveiserros de tipo são encontrados em tempo de compilação (tipagem estática). Isto torna os programas mais segurose mais rápidos, eliminando a necessidade de verificações de tipo em tempo de execução.
2.8 Inferência de tipos
Toda expressão bem formada tem um tipo mais geral, que pode ser calculado automaticamente em tempo decompilação usando um processo chamado inferência de tipos.
A capacidade de inferir tipos automaticamente facilita a programação, deixando o programador livre paraomitir anotações de tipo ao mesmo tempo que permite a verificação de tipos.
A inferência de tipo é feita usando as regras de tipagem de cada forma de expressão.
Literais inteiros Os literais inteiros são do tipo int.
Literais fracionários Os literais fracionários são do tipo float.
Literais caracteres Os literais caracteres são do tipo char.
Literais strings Os literais strings são do tipo string.
Construtores constantes Os consrutores constantes de um tipo são do tipo associado. Assim:
• os construtores constantes booleanos true e false são do tipo bool, e
Aplicação de funçãox1 :: a1
...xn :: an
f :: a1 → . . . → an → b
f x1 . . . xn :: b
Em uma aplicação de função:
• o tipo dos argumentos deve ser compatível com os domínios da função
• o tipo do resultado deve ser compatível com o contra-domínio da função
2.9 Exercícios
Tarefa 2.1: Movimento Retilínio Uniformementne Variado
A posição s de um corpo em movimento retilínio uniformemente variado, em função do tempo t, é dadopela equação
s = s0 + v0t +12
at2
onde s0 é a posição inicial do corpo, v0 é a sua velocidade inicial, e a é a sua acelaração.
Utilize o ambiente interativo do OCaml para calcular a posição de uma bola em queda livre no instantet = 8 s, considerando que a posição inicial é s0 = 100 m, a velocidade inicial é v0 = 15 m/s e a acelaraçãoda gravidade é a = −9.81 m/s2.
Dica:Use a declaração let para criar variáveis correspondentes aos dados e em seguida avalie a expressãocorrespondente à função horária do movimento usando estas variáveis.
2-8
Tarefa 2.2: Expressões matemáticas
Utilize o ambiente interativo para avaliar as expressões aritméticas seguintes, considerando que x = 3 ey = 4.
1.43π sin x2 − 1
2.x2 y3
(x − y)2
3.1
x2 − y− e−4x +
3
√35y
√x y
4.24 + 4.53
e4.4 − log1012560
5. cos5π6
sin2 7π8
+tan ( π6 ln 8)√
7 + 2
Tarefa 2.3
Defina uma função para calcular o quadrado do dobro do seu argumento.
Tarefa 2.4
Defina uma função para calcular o dobro do quadrado do seu argumento.
Tarefa 2.5: Lados de um triângulo
Os lados de qualquer triângulo respeitam a seguinte restrição:
A soma dos comprimentos de quaisquer dois lados de um triângulo é superior ao compri-mento do terceiro lado.
Escreva uma função que receba o comprimento de três segmentos de reta e resulte em um valor lógicoindicando se satisfazem esta restrição.
Tarefa 2.6: Energia armazenada em uma mola
A força requerida para comprimir uma mola linear é dada pela equação
F = k x
onde F é a força em N (Newton), x é a compressão da mola em m (metro), e k é a constante da mola emN/m.
A energia potencial armazenada na mola comprimida é dada pela equação
E =12
k x2
onde E é a energia em J (joule).Defina funções para calcular a compressão e a energia potencial armazenada em uma mola, dadas a
constante elástica da mola e a força usada para comprimi-la.
Tarefa 2.7: Custo da energia elétrica
Sabe-se que o quilowatt de energia elétrica custa um quinto do salário mínimo. Defina uma função quereceba o valor do salário mínimo e a quantidade de quilowatts consumida por uma residência, e resultano valor a ser pago com desconto de 15%.
2-9
Tarefa 2.8: Receptor de rádio
Uma versão simplificada da parte frontal de um receptor de rádio AM é apresentada na figura abaixo.Esse receptor é composto por um circuito que contém um resistor R, um capacitor C e um indutor Lconectados em série. O circuito é conectado a uma antena externa e aterrado conforme mostra a figura.
Terra
R
−
+
VR
CL
Antena
−
+
V0
O circuito permite que o rádio selecione uma estação específica dentre as que transmitem na faixaAM. Na frequência de resonância do circuito, essencialmente todo o sinal V0 da antena vai até o resistor,que representa o resto do rádio. Em outras palavras, o rádio recebe seu sinal mais forte na frequência deressonância. A frequência de ressonância do circuito indutor-capacitor é dada pela equação
f0 =1
2π√
LC
onde L é a indutância em H (henry) e C é a capcitância em F (farad).Defina uma função que receba a indutância L e a capacitância C, e resulta na frequência de ressonância
desse aparelho de rádioTeste sua função pelo cálculo da frequência do rádio quando L = 0,25mH e C = 0,10nF.
Tarefa 2.9: Força gravitacional
A lei da gravitação universal, proposta por Newton a partir das observações de Kepler sobre os movimen-tos dos corpos celestes, diz que:
Dois corpos quaisquer se atraem com uma força diretamente proporcional ao produto de suasmassas e inversamente proporcional ao quadrado da distância entre eles.
Essa lei é formalizada pela seguinte equação:
F = Gm1m2
d2
onde:
• F é força de atração em Newtons (N),
• G é a constante de gravitação universal (6.67 × 10−11 N m2/kg2),
• m1 e m2 são as massas dos corpos envolvidos, em quilos (kg), e
• d é a distância entre os corpos em metros (m).
1. Defina uma variável para denotar a constante de gravitação universal.
2. Defina uma função que recebe as massas dos dois corpos e a distância entre eles, e resulta na forçade atração entre esses dois corpos. Use a variável definida em 1.
3. Teste suas definições no ambiente interativo calculando a força de atração entre a terra e a luasabendo que a massa da terra é 6 × 1024 kg, a massa da lua é 1 × 1023 kg, e a distância entre eles é4 × 105 km.
2-10
Tarefa 2.10: Salário líquido
Defina uma função que recebe o salário base de um funcionário e resulta no salário líquido a receber,sabendo-se que o funcionário tem gratificação de 10% sobre o salário base e paga imposto de 7% sobre osalário base.
Tarefa 2.11
Defina uma função que verifica se uma equação do segundo grau
ax2 + bx + c = 0
possui raízes reais. Para tanto é necessário que o discriminante ∆ = b2 − 4ac seja não negativo.
Tarefa 2.12: Área do círculo
Defina uma função que recebe a medida do raio r de um círculo e resulta na área A do círculo, dada por:
A = π × r2
Tarefa 2.13: Número de degraus
Defina uma função que recebe a altura dos degraus de uma escada e a altura que o usuário deseja alcançarsubindo a escada, e resulta na quantidade mínima de degraus que ele deverá subir para atingir seu objetivo,sem se preocupar com a altura do usuário.
Tarefa 2.14
Determine o tipo de cada função definida a seguir.
1) let dobro x = x * 2
2) let aprovado nota = nota >= 6
3) let myLog x b = log x / log b
2-11
3 Expressão Condicional
ResumoExpressões condicionais permitem a escolha entre duas alternativas na obtenção do valor da
expressão, com base em uma condição (expressão lógica).Nesta aula vamos nos familiarizar com o uso de expressões condicionais. Vamos também apren-
der a fazer declarações locais a uma equação.
Sumário3.1 Expressão condicional . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3-13.2 Definição de função com expressão condicional . . . . . . . . . . . . . . . . . . . . . . . . . 3-2
3.1 Expressão condicional
Uma expressão condicional tem a forma
if condição then exp1 else exp2
onde condição é uma expressão booleana (chamada predicado) e exp1 (chamada consequência) e exp2 (cha-mada alternativa) são expressões de um mesmo tipo. O valor da expressão condicional é o valor de exp1 se acondição é verdadeira, ou o valor de exp2 se a condição é falsa.
Seguem alguns exemplos de expressões condicionais e seus valores.
if true then 1 else 2 1if false then 1 else 2 2if 2>1 then "OK" else "FAIL" "OK"if 5 mod 2 = 0 then 3+2 else 3-2 1
A expressão condicional é uma expressão, e portanto sempre tem um valor. Assim uma expressão condicionalpode ser usada dentro de outra expressão. Veja os exemplos seguintes.
5 * (if true then 10 else 20) 505 * if true then 10 else 20 50String.length (if 2<=1 then "OK" else "FAIL") 4
Veja na tabela 2.1 a precedência relativa da expressão condicional. Ela mostra que a precedência da expressãocondicional só não é menor do que a precedência do operador ; e também das expressões let, match, fun,function e try.
(if 12 mod 2 = 0 then 10 else 20) + 1 11if 12 mod 2 = 0 then 10 else 20 + 1 10
Regra de inferência de tipo
test :: boole1 :: ae2 :: a
if test then e1 else e2 :: a
Observe que a consequência e a alternativa devem ser do mesmo tipo, que também é o tipo do resultado.Exemplos no ambiente interativo:
3-1
# if 4>5 then ’S’ else ’N’;;- : char = ’N’# if 8 mod 2 <> 0 then 10 else 20;;- : int = 20# if 17 mod 2 = 0 then 12.0 else 5.1;;- : float = 5.1
# if ’A’ then "ok" else "bad";;Error: This expression has type char but an expression was expected of type
bool# if 17 mod 2 <> 0 then not true else ’H’;;Error: This expression has type char but an expression was expected of type
bool
else opcional
A cláusula else de uma expressão condicional é opcional. Quando ela é omitida e o valor do teste é falso,o resultado é () (ou seja, a tupla vazia), do tipo unit. Como de forma geral o compilador não pode determinarse o valor do teste é verdadeiro ou falso, impõe-se a restrição de que o tipo da primeira alternativa também sejaunit, contemplando assim a possibilidade de o valor do teste ser verdadeiro ou falso, com resultados do mesmotipo para a expressão condicional.
# if true then print_endline "ok";;ok- : unit = ()# if true then 10;;Error: This expression has type int but an expression was expected of type
unit
Tarefa 3.1
Determine o valor e o tipo das expressões seguintes caso a expressão esteja correta. Se a expressão estiverincorreta, indique qual é o problema encontrado.
a) if sqrt (abs_float (10.0 -. 35.0) *. 100.0) < 5.0 then "aceito" else "negado"
b) if pred (int_of_char ’B’) then 10 else 20
c) if 1 mod 2 <> 0 then sqrt 0.09 else Char.lowercase ’B’
d) 4 * if ’B’ < ’A’ then 2 + 3 else 2 - 3
e) compare (if ’B’ < ’A’ then 2 + 3 else 2) 3
f) if 5 > 0 then "minas gerais"
g) if 5 > 0 then print_string "minas gerais"
3.2 Definição de função com expressão condicional
Como na maioria das linguagens de programação, funções podem ser definidas usando expressões condi-cionais. Por exemplo, a função para calcular o valor absoluto de um número inteiro pode ser definida comosegue:
let valorAbsoluto n =if n >= 0 then n else -n
valorAbsoluto recebe um inteiro n e resulta em n se ele é não-negativo, e -n caso contrário.Expressões condicionais podem ser aninhadas, como mostra o exemplo a seguir onde é definida uma função
para determinar o sinal de um número inteiro.
3-2
let sinal n =if n < 0 then-1
elseif n = 0 then0
else1
Veja outro exemplo onde é definida uma função para análise do índice de massa corporal de uma pessoa:
let analisaIMC imc =if imc <= 18.5 then"Você está abaixo do peso, seu emo!"
else if imc <= 25.0 then"Você parece normal. Deve ser feio!"
else if imc <= 30.0 then"Você está gordo! Perca algum peso!"
else"Você está uma baleia. Parabéns!"
Tarefa 3.2: Maior de três valores
Defina uma função max3 que recebe três valores e resulta no maior deles. Use expressões condicionaisaninhadas.
Teste sua função no ambiente interativo.
Tarefa 3.3: Conceito obtido por estudante
O conceito obtido por um estudante a partir da média ponderada de suas notas (no intervalo [0 − 10]) édada pela tabela seguinte:
média ponderada conceito[8,10] A[7,8[ B[6,7[ C[5,6[ D[0,5[ E
Defina uma função conceito_obtido do tipo float -> char que recebe a média ponderada obtidapor um estudante e resulta no conceito.
Teste sua função no ambiente interativo do OCaml.
3-3
4 Definições Locais
ResumoNesta aula vamos aprender a fazer definições locais a uma expressão usando a expressão let.
Sumário4.1 Expressão let . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4-14.2 Exercícios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4-3
4.1 Expressão let
Em muitas situações é desejável poder definir valores e funções auxiliares na avaliação de uma expressãoprincipal. Isto pode ser feito escrevendo-se expressões let.
Uma expressão let é formada por uma definição de variável ou função, e por um corpo (que é uma expressão),introduzidos pelas palavras chave let e in:
let definição in expressão
O escopo dos nomes definidos em uma expressão let restringe-se ao corpo da própria expressão let. O tipode uma expressão let é o tipo do seu corpo. O valor de uma expressão let é o valor do seu corpo, calculado emum contexto que inclui os nomes introduzidos na definição local.
Veja alguns exemplos:
# let x = 3+2 in (x+1)*(x-1) + 2*x - 4;;- : int = 30
# let quadrado x = x*x in quadrado 5 + quadrado 3;;- : int = 34
A expressão let é uma expressão, e portanto sempre tem um valor. Assim uma expressão let pode ser usadadentro de outra expressão. Por exemplo:
# 5 * (let x = 3+2 in (x+1)*(x-1) + 2*x - 4) + 1;;- : int = 151
Expressões let podem ser aninhadas, como no exemplo a seguir:
# let x = 3+2 in let y = 5-1 in x*x + 2*x - y;;- : int = 31
Na tabela 2.1 vemos que a expressão let, juntamente com as expressões match, fun, function e try tema menor precedência.
Lembre-se que os nomes definidos em uma expressão local são válidos apenas no corpo da expressão let,como ilustra o exemplo a seguir:
# (let x = 3+2 in x*x + 2*x - 1) + 3*x;;Error: Unbound value x
Se a variável sendo definida na expressão let já existir no escopo em que a expressão let é usada, a variávellocal criada esconde a variável já existente. Por exemplo:
# let x = 1001;;val x : int = 1001
4-1
# let x = 2 in x * x * 4;;- : int = 16
# x;;- : int = 1001
Observe que em OCaml a mesma palavra chave let é usada para fazer definições de variáveis e funções tantolocais quanto globais. A palavra chave in é usada somente no caso de definições locais.
Expressões let são interessantes para dividir uma expressão maior em subexpressões menores que são nome-adas. Os nomes são então usados na expressão principal. Isto pode aumentar o legibilidade do código.
Expressões let também são interessantes quando uma determinada subexpressão é usada várias vezes nocódigo. Ao dar um nome à subexpressão em uma expressão let evitamos que a subexpressão seja escrita eavaliada várias vezes.
Na prática expressões let são usadas para criar variáveis ou funções locais dentro de outras funções. Digamosque precisamos de uma função para calcular a raiz positiva de uma equação do segundo grau, se houver (se nãohouver, retorna o valor infinito):
let raiz_positiva a b c =if (b *. b -. 4.0 *. a *. c) >= 0.0 then(-.b +. sqrt (b *. b -. 4.0 *. a *. c)) /. (2.0 *. a)
elseinfinity
Além da repetição do cálculo do discriminante na fórmula da equação do segundo grau, o cálculo da raiz com umaexpressão muito longa torna o código mais difícil de entender. Usando uma variável local para o discriminante(normalmente chamado de delta), a mesma função fica mais legível:
let raiz_positiva a b c =let delta = b *. b -. 4.0 *. a *. c inif delta >= 0.0 then(-.b +. sqrt delta) /. (2.0 *. a)
elseinfinity
Tipicamente a formatação da expressão let é feita colocando a definição em uma linha començando com lete terminando com in, e o resto da código continuando na linha seguinte, com a mesma indentação.
O exemplo seguinte usa uma expressão let na definição de uma função que calcula a área da superfície de umcilindro, dados o raio da base e a altura do cilindro:
let areaSuperfCilindro r h =let pi = acos (-1.0) inlet areaLado = 2.0 *. pi *. r *. h inlet areaBase = pi *. r**2.0 inareaLado +. 2.0*.areaBase
Por exemplo, considere a fórmula de Heron
A =√
s(s − a)(s − b)(s − c)
para calcular a área de um triângulo com lados a, b e c, sendo
s =a + b + c
2
o semiperímetro do triângulo. Como s aparece várias vezes na fórmula, podemos defini-lo localmente uma únicavez e usá-lo quantas vezes forem necessárias.
a
b
c
4-2
let areaTriangulo a b c =let s = (a +. b +. c) /. 2.0 insqrt (s *. (s -. a) *. (s -. b) *. (s -. c))
Esta definição assume que os argumentos da função são valores válidos para os lados de um triângulo.
# areaTriangulo 5. 6. 8.;;- : float = 14.9812382665786341
Uma definição mais elaborada para esta função somente calcula a área se os argumentos forem lados de umtriângulo (um lado deve ser positivo e menor do que a soma dos outros dois lados):
let areaTriangulo a b c =if a > 0.0 && b > 0.0 && c > 0.0 &&a < b +. c &&b < a +. c &&c < a +. b thenlet s = (a +. b +. c) /. 2.0 insqrt (s *. (s -. a) *. (s -. b) *. (s -. c))
else0.0
Veja outro exemplo de definição local:
let g x y =let square x = x*x inlet a = square (y+1) inif x <= 10 thenx + a
else if x > 10 thenx - a
elsex
O escopo de a inclui os dois possíveis resultados determinados pelas guardas.O próximo exemplo mostra uma função para análise do índice de massa corporal.
let analisaIMC peso altura =let imc = peso /. altura ** 2.0 inif imc <= 18.5 then "Você está abaixo do peso, seu emo!"else if imc <= 25.0 then "Você parece normal. Deve ser feio!"else if imc <= 30.0 then "Você está gordo! Perca algum peso!"else "Você está uma baleia. Parabéns!"
Ou ainda:
let analisaIMC peso altura =let imc = peso /. altura ** 2.0 inlet magro = 18.5 inlet normal = 25.0 inlet gordo = 30.0 inif imc <= magro then "Você está abaixo do peso, seu emo!"else if imc <= normal then "Você parece normal. Deve ser feio!"else if imc <= gordo then "Você está gordo! Perca algum peso!"else "Você está uma baleia. Parabéns!"
4.2 Exercícios
4-3
Tarefa 4.1: Área de um triângulo usando relações métricas
A área de um triângulo de lados a, b e c pode ser calculada usando relações métricas em um triânguloqualquer.
a
b
c α
90o
h
Pela lei dos cossenos temos:
a2 = b2 + c2 − 2bc cos α =⇒ cos α =b2 + c2 − a2
2bcPela relação fundamental da trigonometria temos:
sin2 α + cos2 α = 1 =⇒ sin α =√
1 − cos2 α
Pela definição de seno temos:
sin α =hb
=⇒ h = b sin α
Pela definição da área de um triângulo temos:
A =ch2
Defina uma função para calcular a área de um triângulo de lados a, b e c usando as esquações apre-sentadas. Caso a , b e c não possam ser lados de um triângulo a função deve resultar em zero.
Dica Faça definições locais para os valores cos α, sin α e h.
Tarefa 4.2: Número de raízes reais da equação do segundo grau
Defina uma função chamada numRaizes que recebe os três coeficientes de uma equação do segundo grau
ax2 + bx + c = 0
e calcula a quantidade de raízes reais distintas da equação. Assuma que a equação é não degenerada (istoé, o coeficiente do termo de grau dois não é zero).
Use uma definição local para calcular o discriminante da equação.
∆ = b2 − 4ac
Se ∆ for positivo a equação tem duas reais reais e distintas, se for nulo, a equação tem uma raiz real,e se for negativo, a equação não tem raízes reais.
Tarefa 4.3: Notas de um estudante
A nota final de um estudante é calculada a partir de três notas atribuídas respectivamente a um trabalho delaboratório, a uma avaliação semestral e a um exame final. A média ponderada das três notas mencionadasobedece aos pesos a seguir:
nota pesotrabalho de laboratório 2avaliação semestral 3exame final 5
O programa a seguir, que está incompleto, recebe as três notas e determina e exibe o conceito obtido peloaluno usando a tabela:
4-4
média ponderada conceito[8.0 – 10.0] A[7.0 – 8.0[ B[6.0 – 7.0[ C[5.0 – 6.0[ D[0.0 – 5.0[ E
Considera-se que as notas digitadas são válidas.
let conceito n1 n2 n3 =(* complete a definição da função *)
let main =print_string "Digite a nota do trabalho de laboratório ...: ";let laboratorio = read_float () inprint_string "Digite a nota da avaliação semestral .......: ";let semestral = read_float () inprint_string "Digite a nota do exame final ...............: ";let final = read_float () inprint_newline ();print_string "Conceito obtido: ";print_char (conceito laboratorio semestral final);print_newline ()
Exemplo de execução da aplicação
Digite a nota do trabalho de laboratório ...: 7.8Digite a nota da avaliação semestral .......: 8.0Digite a nota do exame final ...............: 4.9
Conceito obtido: C
Você deve completar a definição do função conceito. Use uma definição local para calcular a média.
4-5
5 Funções Recursivas
ResumoDefinições recursivas são comuns na programação funcional. Nesta aula vamos aprender a definir
funções recursivas.
Sumário5.1 Recursividade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5-15.2 Recursividade mútua . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5-45.3 Recursividade de cauda . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5-55.4 Vantagens da recursividade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5-7
5.1 Recursividade
Recursividade é uma idéia inteligente que desempenha um papel central na programação funcional e naciência da computação em geral. Recursividade é o mecanismo de programação no qual uma definição defunção ou de outro objeto refere-se ao próprio objeto sendo definido. Assim função recursiva é uma função queé definida em termos de si mesma. São sinônimos: recursividade, recursão, recorrência.
Recursividade é o mecanismo básico para repetições nas linguagens funcionais.Definições recursivas em OCaml são introduzidas pela declaração let rec.Estratégia para a definição recursiva de uma função:
1. dividir o problema em problemas menores do mesmo tipo
2. resolver os problemas menores (dividindo-os em problemas ainda menores, se necessário)
3. combinar as soluções dos problemas menores para formar a solução final
Ao dividir o problema sucessivamente em problemas menores eventualmente os casos simples são alcançados:
• não podem ser mais divididos
• suas soluções são definidas explicitamente
De modo geral, uma definição de função recursiva é dividida em duas partes:
• Há um ou mais casos base que dizem o que fazer em situações simples, onde não é necessária nenhumarecursão.
– Nestes casos a resposta pode ser dada de imediato, sem chamar recursivamente a função sendodefinida.
– Isso garante que a recursão eventualmente pode parar.
• Há um ou mais casos recursivos que são mais gerais, e definem a função em termos de uma chamada maissimples a si mesma.
Como exemplo de função recursiva, considere o cálculo do fatorial de um número natural. A função quecalcula o fatorial de um número natural pode ser definida recursivamente como segue:
let rec fatorial n =if n = 0 then1
elseif n > 0 thenfatorial (n-1) * n
elseraise (Invalid_argument "fatorial")
Nesta definição:
5-1
• A primeira alternativa estabelece que o fatorial de 0 é 1. Este é o caso base.
• A segunda alternativa estabelece que o fatorial de um número positivo é o produto deste número e dofatorial do seu antecessor. Este é o caso recursivo.
Observe que no caso recursivo o subproblema fatorial (n-1) é mais simples que o problema original
fatorial n e está mais próximo do caso base fatorial 0 .Aplicando a função fatorial:
fatorial 6 fatorial 5 * 6 (fatorial 4 * 5) * 6 ((fatorial 3 * 4) * 5) * 6 (((fatorial 2 * 3) * 4) * 5) * 6 ((((fatorial 1 * 2) * 3) * 4) * 5) * 6 (((((fatorial 0 * 1) * 2) * 3) * 4) * 5) * 6 (((((1 * 1) * 2) * 3) * 4) * 5) * 6 ((((1 * 2) * 3) * 4) * 5) * 6 (((2 * 3) * 4) * 5) * 6 ((6 * 4) * 5) * 6 (24 * 5) * 6 120 * 6 720
Tarefa 5.1: Aplicando fatorial
Digite a função fatorial em um arquivo fonte e carregue-o no ambiente interativo.
a) Mostre que fatorial 7 = 5040 usando uma sequência de passos de simplificação.
b) Determine o valor da expressão fatorial 7 usando o ambiente interativo.
c) Determine o valor da expressão fatorial 31 usando o ambiente interativo. Se você tiver umacalculadora científica, verifique o resultado na calculadora. Explique porque os resultados diferem.
d) O que acontece ao se calcular o valor da expressão fatorial (-2)?
Vejamos outro exemplo. A função que calcula a potência de dois (isto é, a base é dois) para números naturaispode ser definida recursivamente como segue:
let rec pot_dois n =if n = 0 then1
elseif n > 0 then2 * pot_dois (n-1)
elseraise (Invalid_argument "pot_dois")
Nesta definição:
• A primeira alternativa estabelece que 20 = 1. Este é o caso base.
• A segunda alternativa estabelece que 2n = 2 × 2n−1, sendo n > 0. Este é o caso recursivo.
Observe que no caso recursivo o subproblema pot_dois (n-1) é mais simples que o problema original
pot_dois n e está mais próximo do caso base pot_dois 0 .Aplicando a função potência de dois:
5-2
pot_dois 4 2 * pot_dois 3 2 * (2 * pot_dois 2) 2 * (2 * (2 * pot_dois 1)) 2 * (2 * (2 * (2 * pot_dois 0))) 2 * (2 * (2 * (2 * 1))) 2 * (2 * (2 * 2)) 2 * (2 * 4) 2 * 8 16
Tarefa 5.2
Considere a seguinte definição para a função potência de dois:
let rec pot_dois’ n =if n = 0 then1
else2 * pot_dois’ (n-1)
O que acontece ao calcular o valor da expressão pot_dois’ (-3)?
Vejamos mais um exemplo de definição recursiva. A multiplicação de inteiros está disponível na bibliotecacomo uma operação primitiva por questões de eficiência. Porém ela pode ser definida usando adicão e recursivi-dade em um de seus argumentos:
let rec mul m n =if n = 0 then0
else if n > 0 thenm + mul m (n-1)
else- (mul m (- n))
Nesta definição:
• A primeira alternativa estabelece que quando o multiplicador é zero, o produto também é zero. Este é ocaso base.
• A segunda alternativa estabelece que m × n = m + m × (n − 1), sendo n > 0. Este é um caso recursivo.
• A terceira alternativa estabelece que m × n = −(m × (−n)), sendo n < 0. Este é outro caso recursivo.
Aplicando a função de multiplicação:
% mul 7 (-3) - (mul 7 (- (-3))) - (mul 7 3) - (7 + mul 7 2) - (7 + (7 + mul 7 1)) - (7 + (7 + (7 + mul 7 0))) - (7 + (7 + (7 + 0))) - (7 + (7 + 7)) - (7 + 14) - 21 -21
A definição recursiva da multiplicação formalisa a idéia de que a multiplicação pode ser reduzida a adiçõesrepetidas.
Tarefa 5.3
Mostre que mul 5 6 = 30.
5-3
Vamos analisar outro exemplo de função recursiva: a sequência de Fibonacci. Na seqüência de Fibonacci
0,1,1,2,3,5,8,13, . . .
os dois primeiros elementos são 0 e 1, e cada elemento subseqüente é dado pela soma dos dois elementos que oprecedem na seqüência. A função a seguir calcula o n-ésimo número de Fibonnaci, para n ≥ 0:
let rec fib n =if n = 0 then0
else if n = 1 then1
else if n > 1 thenfib (n-2) + fib (n-1)
elseraise (Invalid_argument "fib")
Nesta definição:
• A primeira e a segunda alternativa são os casos base.
• A terceira alternativa é o caso recursivo.
Neste caso temos recursão múltipla, pois a função sendo definida é usada mais de uma vez em sua própriadefinição.
Aplicando a função de fibonacci:
fib 5 fib 3 + fib 4 (fib 1 + fib 2) + (fib 2 + fib 3) (1 + (fib 0 + fib 1)) + ((fib 0 + fib 1) + (fib 1 + fib 2)) (1 + (0 + 1)) + ((0 + 1) + (1 + (fib 0 + fib 1))) (1 + 1) + (1 + (1 + (0 + 1))) 2 + (1 + (1 + 1)) 2 + (1 + 2) 2 + 3 5
Tarefa 5.4
Mostre que fib 6 = 8.
5.2 Recursividade mútua
Recursividade mútua ocorre quando duas ou mais funções são definidas em termos uma da outra. EmOCaml funções mutuamente recursivas devem ser definidas simultaneamente.
Em OCaml declarações simultâneas são introduzidas por let ou let rec e são separadas por and. Vejaalguns exemplos:
# let x = 2 and y = 3 in x + y - 1;;- : int = 4
# let x = 2 and y = 2*x in x + y - 1;;Error: Unbound value x
# let x = 2 in let y = 2*x in x + y - 1;;- : int = 5
Para exemplificar funções mutuamente recursivas vamos definir as funções par e ímpar que determinam seum número é par ou ímpar, respectivamente. Uma definição eficiente destas funções usa o resto da divisão pordois:
5-4
let par n =n mod 2 = 0
let impar n =n mod 2 <> 0
No entanto elas também podem ser definidas usando recursividade mútua:
let rec par n =if n = 0 thentrue
else if n > 0 thenimpar (n-1)
elsepar (-n)
and impar n =if n = 0 thenfalse
else if n > 0 thenpar (n-1)
elseimpar (-n)
Nestas definições observamos que:
• Zero é par, mas não é ímpar.
• Um número positivo é par se seu antecessor é ímpar.
• Um número positivo é ímpar se seu antecessor é par.
• Um número negativo é par (ou ímpar) se o seu oposto for par (ou ímpar).
Aplicando as função par e impar:
par (-5) par 5 impar 4 par 3 impar 2 par 1 impar 0 false
5.3 Recursividade de cauda
Uma função recursiva apresenta recursividade de cauda se o resultado final da chamada recursiva é o resul-tado final da própria função. Se o resultado da chamada recursiva deve ser processado de alguma maneira paraproduzir o resultado final, então a função não apresenta recursividade de cauda.
Por exemplo, a função recursiva a seguir não apresenta recursividade de cauda:
let rec fatorial n =if n = 0 then1
elseif n > 0 thenfatorial (n-1) * n
elseraise (Invalid_argument "fatorial")
5-5
No caso recursivo, o resultado da chamada recursiva fatorial (n-1) é multiplicado por n para produzir oresultado final.
A função recursiva a seguir também não apresenta recursividade de cauda:
let rec par n =if n = 0 thentrue
else if n > 0 thennot (par (n-1))
elseraise (Invalid_argument "par")
No caso recursivo, a função not é aplicada ao resultado da chamada recursiva par (n-1) para produzir oresultado final.
Já a função recursiva potencia_dois’ a seguir apresenta recursividade de cauda:
let potencia_dois n =let rec potencia_dois’ x y =if x = 0 theny
else if x > 0 thenpotencia_dois’ (x-1) (2*y)
elseraise (Invalid_argument "potencia_dois’")
inpotencia_dois’ n 1
No caso recursivo, o resultado da chamada recursiva potencia_dois’ (n-1) (2*y) é o resultado final.
Tarefa 5.5
Mostre que potencia_dois 5 = 32.
Tarefa 5.6
Faça uma definição recursiva da função par usando recursividade de cauda.
Otimização de chamada de cauda Em muitas implementações de linguagens de programação uma chamadade função usa um espaço de memória (chamado de quadro, frame ou registro de ativação) em uma área damemória (chamada pilha ou stack) onde são armazenadas informações importantes, como:
• argumentos da função
• variáveis locais
• variáveis temporárias
• endereço de retorno da função
Uma chamada de cauda acontece quando uma função chama outra função como sua última ação, não tendomais nada a fazer além desta última ação. O resultado final da função é dado pelo resultado da chamada decauda. Em tais situações o programa não precisa voltar para a função que chama quando a função chamadatermina. Portanto, após a chamada de cauda, o programa não precisa manter qualquer informação sobre a funçãochamadora na pilha.
Algumas implementações de linguagem tiram proveito desse fato e na verdade não utilizam qualquer espaçoextra de pilha quando fazem uma chamada de cauda, pois o espaço na pilha da própria função chamadora éreutilizado, já que ele não será mais necessário para a função chamadora. Esta técnica é chamada de eliminaçãoda cauda, otimização de chamada de cauda ou ainda otimização de chamada recursiva. A otimização dechamada de cauda permite que funções com recursividade de cauda recorram indefinidamente sem estourar apilha.
Estruturas de repetição Muitas linguagens funcionais não possuem estruturas de repetição e usam funçõesrecursivas para fazer repetições. Nestes casos a otimização de chamada de cauda é fundamental para uma boaeficiência dos programas.
Em particular o núcleo funcional da linguagem OCaml não usa estruturas de repetição.
5-6
5.4 Vantagens da recursividade
A recursividade permite que:
• muitas funções possam ser naturalmente definidas em termos de si mesmas,
• propriedades de funções definidas usando recursão podem ser provadas usando indução, uma técnica ma-temática simples, mas poderosa.
Tarefa 5.7: Fatorial duplo
O fatorial duplo de um número natural n é o produto de todos os números de 1 (ou 2) até n, contados de 2em 2. Por exemplo, o fatorial duplo de 8 é 8×6×4×2 = 384, e o fatorial duplo de 7 é 7×5×3×1 = 105.
Defina uma função para calcular o fatorial duplo usando recursividade.
Tarefa 5.8: Multiplicação em um intervalo
Defina uma função recursiva que recebe dois números naturais m e n, e retorna o produto de todos osnúmeros no intervalo [m,n]:
m × (m + 1) × · · · × (n − 1) × n
Tarefa 5.9: Fatorial
Usando a função definida no exercício 5.8, escreva uma definição não recursiva para calcular o fatorial deum número natural.
Tarefa 5.10: Adição
Defina uma função recursiva para calcular a soma de dois números naturais, sem usar os operadores + e-. Utilize as funções succ e pred da biblioteca, que calculam respectivamente o sucessor e o antecessorde um valor.
Tarefa 5.11: Potenciação
Defina uma função recursiva para calcular a potência de um número, considerando que o expoente é umnúmero natural. Utilize o método das multiplicações sucessivas:
xn = x × x × . . . × x︸ ︷︷ ︸n vezes
Tarefa 5.12: Raiz quadrada inteira
A raiz quadrada inteira de um número inteiro positivo n é o maior número inteiro cujo quadrado é menorou igual a n. Por exemplo, a raiz quadrada inteira de 15 é 3, e a raiz quadrada inteira de 16 é 4.
Defina uma função recursiva para calcular a raiz quadrada inteira.
Tarefa 5.13: Quociente e resto da divisão inteira
Defina duas funções recursivas que calculam o quociente e o resto da divisão inteira de dois númerosnaturais usando subtrações sucessivas.
Tarefa 5.14: Máximo divisor comum
Defina uma função recursiva para calcular o máximo divisor comum de dois números inteiros não nega-tivos a e b, usando o algoritmo de Euclides:
mdc(a,b) =
a se b = 0,mdc(b,a mod b) se b > 0,mdc(a,−b) se b < 0
5-7
Tarefa 5.15: Fatorial
Considere a seguinte função para calcular o fatorial de um número:
let fat n =let rec fat_aux x f =if x = 0 thenf
else if x > 0 thenfat_aux (x-1) (x*f)
elseraise (Invalid_argument "fat_aux")
infat_aux n 1
a) Mostre que fat 6 = 720.
b) Compare o cálculo de fat 6 com o cálculo de fatorial 6 apresentado anteriormente. Qualversão da função fatorial é mais eficiente: fatorial ou fat? Explique.
Tarefa 5.16: Sequência de Fibonacci
Defina uma função com recursividade de cauda para calcular o n-ésimo (n ≥ 0) número de Fibonacci.
5-8
6 Tuplas, Listas, e Polimorfismo Paramétrico
ResumoNesta aula vamos conhecer os tipos tuplas e listas, que são tipos polimórficos pré-definidos em
OCaml. Vamos aprender também sobre funções polimórficas.
Sumário6.1 Tuplas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6-16.2 Listas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6-26.3 Polimorfismo paramétrico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6-4
6.3.1 Operação sobre vários tipos de dados . . . . . . . . . . . . . . . . . . . . . . . . . . . 6-46.3.2 Variáveis de tipo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6-46.3.3 Valor polimórfico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6-56.3.4 Instanciação de variáveis de tipo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6-5
6.4 Funções polimórficas predefinidas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6-5
6.1 Tuplas
Tupla é uma estrutura de dados formada por uma sequência de valores possivelmente de tipos diferentes.Os componentes de uma tupla são identificados pela posição em que ocorrem na tupla.
Em OCaml uma expressão tupla é formada por uma sequência de expressões separadas por vírgula e comu-mente delimitada por parênteses:
( exp1 , . . . , expn )
onde n >= 0 e n , 1, e exp1, . . ., expn são expressões cujos valores são os componentes da tupla. Os parêntesesnão são obrigatórios, mas são comumente usados por lembrar a notação matemática para tuplas.
O tipo de uma tupla é o produto cartesiano dos tipos dos seus componentes. Ele é expresso usando ooperador binário de tipos *:
t1 * . . . * tn
onde n >= 0 e n , 1, e t1, . . ., tn são os tipos dos respectivos componentes da tupla. Observe que o tamanho deuma tupla (quantidade de componentes) é codificado no seu tipo.
Observe que () é a tupla vazia, do tipo unit .Não existe tupla de um único componente.A tabela a seguir mostra alguns exemplos de tuplas:
tupla tipo(’A’, ’t’) char * char(’A’, ’t’, ’o’) char * char * char(’A’, true) char * bool("Joel", ’M’, true, "COM") string * char * bool * string(true, ("Ana", ’f’), 43) bool * (string * char) * int() unit("nao eh tupla") string
Vejamos algumas operações com tuplas definidas na biblioteca padrão:
• fst: seleciona o primeiro componente de um par:
# fst ("pedro", 19);;- : string = "pedro"
# fst (10, 20, 30);;Error: This expression has type ’a * ’b * ’c
but an expression was expected of type ’d * ’e
6-1
• snd: seleciona o segundo componente de um par:
# snd ("pedro", 19);;- : int = 19
6.2 Listas
Lista é uma estrutura de dados formada por uma sequência de valores (elementos) do mesmo tipo. Oselementos de uma lista são identificados pela posição em que ocorrem na lista.
Em OCaml uma expressão lista é formada por uma sequência de expressões separadas por ponto e vírgula edelimitada por colchetes:
[ exp1 ; . . . ; expn ]
onde n >= 0, e exp1, . . ., expn são expressões cujos valores são os elementos da lista.Um tipo lista é formado usando o construtor de tipo list precedido pelo tipo dos seus elementos:
t list
onde t é o tipo dos elementos da lista. Observe que o tamanho de uma lista (quantidade de elementos) nãoé codificado no seu tipo. Normalmente construtores de tipos usam a notação posfixa: primeiro escreve-se osargumentos de tipo, seguidos do construtor de tipo. No exemplo int list, int é um argumento de tipo e listé um construtor de tipo.
A tabela a seguir mostra alguns exemplos de listas:
lista tipo[’O’; ’B’; ’A’] char list[’B’; ’A’; ’N’; ’A’; ’N’; ’A’] char list[false; true; true] bool list[ [false]; []; [true; false; true] ] bool list list[1.; 8.; 6.; 10.48; -5.] float list
Estruturalmente uma lista pode ser de duas formas:
• lista vazia
– não contém nenhum elemento– é denotada pelo construtor constante []
• lista não vazia
– contém pelo menos um elemento– é formada por uma cabeça (o primeiro elemento da sequência) e por uma cauda (uma lista dos demais
elementos da sequência)– é construída pelo construtor (::) , um operador binário infixo com associatividade à direita e pre-
cedência imediatamente inferior à precedência dos operadores aditivos (+) e (-)
* o operando da esquerda é a cabeça da lista
* o operando da direita é a cauda da lista
Por exemplo, a lista formada pela sequência dos valores 1, 8, e 6 pode ser escrita como
lista[1; 8; 6]1 :: [8; 6]1 :: (8 :: [6])1 :: (8 :: (6 :: []))1 :: 8 :: 6 :: []
Observe que os parênteses neste exemplo são desnecessários, já que o operador (::) associa-se à direita.Os exemplos anteriores podem ser reescritos com estes construtores de lista:
notação estendida notação básica[’O’; ’B’; ’A’] ’O’ :: ’B’ :: ’A’ :: [][’B’; ’A’; ’N’; ’A’; ’N’; ’A’] ’B’ :: ’A’ :: ’N’ :: ’A’ :: ’N’ :: ’A’ :: [][false; true; true] false :: true :: true :: [][ [false]; []; [true; false; true] ] (false :: []) :: [] :: (true :: false :: true :: []) :: [][1.; 8.; 6.; 10.48; -5.] 1. :: 8. :: 6. :: 10.48 :: -5. :: []
6-2
Vejamos algumas operações com listas definidas na biblioteca padrão:
• List.hd: seleciona a cabeça (primeiro elemento) de uma lista:
# List.hd [1; 2; 3; 4; 5];;- : int = 1
# List.hd [];;Exception: Failure "hd".
# List.hd [10, 20, 30];;- : int * int * int = (10, 20, 30)
• List.tl: seleciona a cauda da lista, ou seja, a lista formada por todos os elementos exceto o primeiro:
# List.tl [1; 2; 3; 4; 5];;- : int list = [2; 3; 4; 5]
# List.tl [5*4, 6*5];;- : (int * int) list = []
# List.tl [5*4; 6*5];;- : int list = [30]
# List.tl [8-1];;- : int list = []
# List.tl [];;Exception: Failure "tl".
• List.lenght: calcula o tamanho (quantidade de elementos) de uma lista:
# List.length [1; 2; 3; 4; 5];;- : int = 5
# List.length [];;- : int = 0
• List.nth: seleciona o i-ésimo elemento de uma lista (0 ≤ i < n, onde n é o comprimento da lista):
# List.nth [10; 20; 30; 40; 50] 2;;- : int = 30
# List.nth [10; 20; 30; 40; 50] 0;;- : int = 10
# List.nth [10; 20; 30; 40; 50] 10;;Exception: Failure "nth".
# List.nth [10; 20; 30; 40; 50] (-4);;Exception: Invalid_argument "List.nth".
• List.mem: verifica se um valor é elemento de uma lista
# List.mem 30 [10; 20; 30; 40];;- : bool = true
# List.mem 25 [10; 20; 30; 40];;- : bool = false
• List.append ou (@): concatena duas listas.
6-3
# List.append [1; 2; 3] [40; 50];;- : int list = [1; 2; 3; 40; 50]
# [1; 2; 3] @ [40; 50];;- : int list = [1; 2; 3; 40; 50]
• List.rev: inverte uma lista:
# List.rev [1; 2; 3; 4; 5];;- : int list = [5; 4; 3; 2; 1]
• List.rev_append: inverte a primeira lista e concatena o resultado com a segunda lista:
# List.rev_append [1; 2; 3] [40; 50];;- : int list = [3; 2; 1; 40; 50]
• List.combine: junta duas listas em uma única lista formada pelos pares dos elementos correspondentes:
# List.combine ["pedro"; "ana"; "carlos"] [19; 17; 22];;- : (string * int) list = [("pedro", 19); ("ana", 17); ("carlos", 22)]
• List.split: separa uma lista de pares em duas listas formadas pelos componentes dos pares:
# List.split [("pedro", 19); ("ana", 17); ("carlos", 22)];;- : string list * int list = (["pedro"; "ana"; "carlos"], [19; 17; 22])
6.3 Polimorfismo paramétrico
6.3.1 Operação sobre vários tipos de dados
Algumas funções podem operar sobre vários tipos de dados. Por exemplo: a função List.hd recebe umalista e retorna o primeiro elemento da lista:
List.hd [’b’; ’a’; ’n’; ’a’; ’n’; ’a’] ’b’List.hd ["maria"; "paula"; "peixoto"] "maria"List.hd [true; false; true; true] trueList.hd [("ana", 2.8); ("pedro", 4.3)] ("ana", 2.8)
Não importa qual é o tipo dos elementos da lista. Qual deve ser o tipo de List.hd?
char list -> charstring list -> stringbool list -> bool(string * float) list -> string * float
Observamos que na verdade List.hd pode ter vários tipos.
6.3.2 Variáveis de tipo
Quando um tipo pode ser qualquer tipo da linguagem, ele é representado por uma variável de tipo.No exemplo dado, sendo ’a o tipo dos elementos da lista que é passada como argumento para a função
List.hd, então o tipo de List.hd é ’a list -> ’a . ’a é uma variável de tipo e pode ser substituída porqualquer tipo. O tipo de List.hd estabelece que List.hd recebe uma lista com elementos de um tipo qualquer,e retorna um valor deste mesmo tipo.
Em OCaml variáveis de tipo devem começar com um apóstrofo, e são geralmente denominadas ’a, ’b, ’c,etc.
6-4
6.3.3 Valor polimórfico
Um valor é chamado polimórfico (de muitas formas) se o seu tipo contém uma ou mais variáveis de tipo.Por exemplo, o tipo da função List.hd pode ser escrito como ’a list -> ’a . Ou seja, para qualquer
tipo ’a, List.hd recebe uma lista de valores do tipo ’a e retorna um valor do tipo ’a.Já o tipo da função List.length, que recebe uma lista e resulta no tamanho da lista, é ’a list -> int .
Ou seja, para qualquer tipo ’a, List.length recebe uma lista de valores do tipo ’a e retorna um inteiro.A função fst é do tipo ’a * ’b -> ’a . Ou seja, para quaisquer tipos ’a e ’b, fst recebe um par de
valores do tipo ’a * ’b e retorna um valor do tipo ’a.
6.3.4 Instanciação de variáveis de tipo
As variaveis de tipo podem ser instanciadas para diferentes tipos em diferentes circunstâncias.Por exemplo, a função List.length do tipo ’a list -> int , pode ser aplicada em diferentes tipos listas,
como mostra a tabela:
expressão valor instanciação da variável de tipoList.length [false; true] 2 ’a = boolList.length [5; 4; 3; 2; 1] 5 ’a = charList.length ["ana"; "joel"; "mara"] 3 ’a = stringList.length [("ana", true)] 1 ’a = string * boolList.length [(&&),(||)] 2 ’a = bool -> bool -> bool
6.4 Funções polimórficas predefinidas
Muitas das funções definidas na biblioteca padrão são polimórficas. Algumas delas são mencionadas na tabelaseguinte:
função tipo descriçãofst ’a * ’b -> ’a seleciona o primeiro elemento de um parsnd ’a * ’b -> ’b seleciona o segundo elemento de um parList.hd ’a list -> ’a seleciona o primeiro elemento de uma listaList.tl ’a list -> ’a list seleciona a cauda de uma listaList.combine ’a list -> ’b list -> (’a * ’b) list combina duas listas, elemento a elementoList.split (’a * ’b) list -> ’a list * ’b list transforma uma lista de pares em um par de listas
Observe que a lista vazia é polimórfica. O seu tipo é ’a list.
Tarefa 6.1: Tipo de expressões
Verifique se as seguintes expressões são válidas e determine o seu tipo em caso afirmativo.
a) [’a’; ’b’; ’c’]
b) (’a’, ’b’, ’c’)
c) [(false, ’0’); (true, ’1’)]
d) ([false; true], [’0’; ’1’])
e) [List.tl; List.rev]
f) [[]]
g) [[10; 20; 30]; []; [5; 6]; [24]]
h) (10e-2, 20e-2, 30e-3)
i) [(2, 3); (4, 5.6); (6, 4.55)]
j) (["bom"; "dia"; "brasil"]; fst; "Velho mundo")
k) [List.length]
6-5
Tarefa 6.2: Tipo de funções
Determine o tipo de cada uma das funções definidas a seguir, e explique o que elas calculam.
a) let second xs = List.hd (List.tl xs)
b) let const x y = x
c) let swap (x, y) = (y, x)
d) let apply f x = f x
e) let flip f x y = f y x
f) let pair x y = (x, y)
g) let palindrome xs = List.rev xs = xs
h) let twice f x = f (f x)
i) let mostra (nome, idade) = "Nome: " ^ nome ^ ", idade: " ^ string_of_int idade
Tarefa 6.3: Último
Defina uma função chamada ultimo que seleciona o último elemento de uma lista não vazia, usando asfunções da biblioteca padrão.
Tarefa 6.4: Primeiros
Defina uma função chamada primeiros que seleciona todos os elementos de uma lista não vazia, excetoo último., usando as funções da biblioteca padrão.
Tarefa 6.5: Equação do segundo grau
Defina uma função para calcular as raízes reais do polinômio
ax2 + bx + c
O resultado da função deve ser a lista das raízes reais.
6-6
7 Casamento de Padrão
ResumoLinguagens funcionais modernas usam casamento de padrão em várias situações, como por
exemplo na seleção de componentes de estruturas de dados, na escolha de alternativas em expressõesde seleção múltipla, e na aplicação de funções.
Nesta aula vamos aprender as principais formas de padrão e como funciona a operação casamentode padrão. Vamos ainda conhecer algumas construções de OCaml que usam casamento de padrão,como definições de valores e funções e expressões de seleção múltipla.
Sumário7.1 Casamento de padrão . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7-1
7.1.1 Casamento de padrão . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7-17.1.2 Padrão constante . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7-27.1.3 Padrão variável . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7-27.1.4 Padrão curinga . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7-27.1.5 Padrão tupla . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7-27.1.6 Padrões lista . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7-37.1.7 Padrões combinados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7-47.1.8 Padrões faixa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7-57.1.9 Padrões nomeados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7-5
7.2 Casamento de padrão em definições com let . . . . . . . . . . . . . . . . . . . . . . . . . . 7-67.3 Definição de função usando padrões . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7-67.4 Expressão de Seleção Múltipla . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7-7
7.4.1 Forma e regras de tipo da expressão match . . . . . . . . . . . . . . . . . . . . . . . . 7-87.4.2 Avaliação de expressões match . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7-87.4.3 Exemplos de expressões match . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7-87.4.4 Expressão match com guardas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7-11
7.5 Exercícios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7-11
7.1 Casamento de padrão
7.1.1 Casamento de padrão
Em ciência da computação, casamento de padrão1 é o ato de verificação da presença de um padrão em umdado ou em um conjunto de dados. O padrão é rigidamente especificado. O casamento de padrão é usado paratestar se o objeto de estudo possui a estrutura desejada.
Algumas linguagens de programação funcionais como Haskell, ML e Mathematica possuem uma sintaxeespecial para expressar padrões e uma construção na linguagem para execução condicional baseada no casamentode padrões.
Em OCaml um padrão é uma construção da linguagem de programação que permite analisar a estrutura deum valor e associar variáveis aos seus componentes.
Casamento de padrão é uma operação envolvendo um padrão e uma expressão que faz a correspondência(casamento) entre o padrão e o valor da expressão. Um casamento de padrão pode suceder ou falhar, dependendoda forma do padrão e da expressão envolvidos. Quando o casamento de padrão sucede as variáveis que ocorremno padrão são associadas aos componentes correspondentes do valor.
Por exemplo o padrão ("ana", peso, _) especifica valores que são triplas onde o primeiro componenteé a string "ana", o segundo componente é chamado de peso, e o terceiro componente é irrelevante. O valor("ana", 58.7, ’F’) casa com este padrão e em consequência a variável peso é associada ao valor 58.7. Já ovalor ("pedro", 75.3, ’M’) não casa com esse padrão.
Em um casamento de padrão, o padrão e a expressão devem ser do mesmo tipo.Existem várias formas de padrão. Na seqüência algumas delas são apresentadas.
1Pattern matching em inglês.
7-1
7.1.2 Padrão constante
O padrão constante é simplesmente uma constante. O casamento sucede se e somente se o padrão foridêntico ao valor. Nenhuma associação de variável é produzida.
Veja os exemplos seguintes, onde X indica sucesso e × indica falha:
padrão valor casamento10 10 X10 28 ×
10 ’P’ erro de tipo’P’ ’P’ X’P’ ’q’ ×
’P’ true erro de tipotrue true Xtrue false ×
true 65 erro de tipo
7.1.3 Padrão variável
O padrão variável é simplesmente um identificador de variável de valor (e como tal deve começar com letraminúscula ou sublinhado). O casamento sucede sempre. A variável é associada ao valor.
Exemplos:
padrão valor casamentox 10 X x 7→ 10alfa 563.1223 X alfa 7→ 563.1223letra ’K’ X letra 7→ ’K’nomeCliente "Ana Maria" X nomeCliente 7→ "Ana Maria"pessoa ("Ana",’F’,16) X pessoa 7→ ("Ana", ’F’, 16)notas [5.6; 7.1; 9.0] X notas 7→ [5.6; 7.1; 9.0]
7.1.4 Padrão curinga
O padrão curinga é escrito como um sublinhado ( _ ). O casamento sucede sempre. Nenhuma associaçãode variável é produzida. _ é também chamado de variável anônima, pois, assim como a variável, casa comqualquer valor, porém não nomeia o valor.
Exemplos:
padrão valor casamento_ 10 X_ 28 X_ ’P’ X_ () X_ (18, 3, 2012) X_ "Ana Maria" X_ [5.6; 7.1; 9.0] X
7.1.5 Padrão tupla
Uma tupla de padrões também é um padrão:
( padrão1, . . ., padrãon )
O casamento sucede se e somente se cada um dos padrões casar com o componente correspondente do valor. Seas aridades (tamanhos) do padrão tupla e do valor tupla forem diferentes, então ocorre um erro de tipo.
Exemplos de padrão tupla:
7-2
padrão valor casamento(18, true) (18, true) X(97, true) (18, true) ×
(18, false) (18, true) ×
(18, ’M’) (18, true) erro de tipo(18, true, ’M’) (18, true) erro de tipo() () X(x, y) (5, 9) X x 7→ 5
y 7→ 9(d, _, a) (5, 9, 2012) X d 7→ 5
a 7→ 2012(x, y, z) (5, 9) erro de tipo(18, m, a) (18, 3, 2012) X m 7→ 3
a 7→ 2012(d, 5, a) (18, 3, 2012) ×
(nome, sexo, _) ("Ana", ’F’, 18) X nome 7→ "Ana"sexo 7→ ’F’
(_, _, idade) ("Ana", ’F’, 18) X idade 7→ 18(_, (_, fam), 9) (’F’, ("Ana", "Dias"), 9) X fam 7→ "Dias"(_, (_, fam), 5) (’F’, ("Ana", "Dias"), 9) ×
7.1.6 Padrões listaEstruturalmente uma lista pode ser vazia ou não vazia:
• padrão lista vazia
[]
– é um padrão constante
– o casamento sucede se e somente se o valor for a lista vazia
• padrão lista não vazia
pad1 :: pad2
– é formado por dois padrões pad1 e pad2
– o casamento sucede se e somente se o valor for uma lista não vazia cuja cabeça casa com pad1 e cujacauda casa com pad2
– :: é o construtor de lista não vazia, um operador binário infixo associativo à direita com precedêncialogo abaixo dos operadores aritméticos aditivos (+) e (-).
Exemplos de padrões lista:
• O padrão [] casa somente com a lista vazia.
padrão valor casamento[] [] X[] [1; 2; 3] ×
• O padrão x::xs casa com qualquer lista não vazia, associando as variáveis x e xs com a cabeça e com acauda da lista, respectivamente.
padrão valor casamentox::xs [] ×
x::xs [1; 2; 3; 4] X x 7→ 1xs 7→ [2; 3; 4]
x::xs [’A’] X x 7→ ’A’xs 7→ []
• O padrão x::y::_ casa com qualquer lista que tenha pelo menos dois elementos, associando as variáveisx e y ao primeiro e segundo elementos da lista, respectivamente.
7-3
padrão valor casamentox::y::_ [] ×
x::y::_ ["ana"] ×
x::y::_ [1; 2] X x 7→ 1y 7→ 2
x::y::_ [1; 2; 3; 4] X x 7→ 1y 7→ 2
• O padrão x::_::z::[] casa com qualquer lista que tenha exatamente três elementos, associando asvariáveis x e z ao primeiro e ao terceiro elementos da lista, respectivamente.
padrão valor casamentox::_::z::[] [] ×
x::_::z::[] ["ana"] ×
x::_::z::[] [1; 2; 3] X x 7→ 1z 7→ 3
x::_::z::[] [1; 2; 3; 4; 5] ×
• O padrão 0::a::_ casa com qualquer lista de números inteiros que tenha pelo menos dois elementos,sendo o primeiro igual a zero, associando a variável a ao segundo elemento da lista.
padrão valor casamento0::a::_ [] ×
0::a::_ [0] ×
0::a::_ [0; 2; 3] X a 7→ 20::a::_ [0; 10; 6; 3] X a 7→ 100::a::_ [7; 0; 8] ×
• O padrão (m,_)::_ casa com qualquer lista não vazia de pares, associando a variável m ao primeirocomponente do primeiro elemento da lista.
padrão valor casamento(m,_)::_ [] ×
(m,_)::_ [("fim", true)] X m 7→ "fim"(m,_)::_ [(10, ’M’); (20, ’F’)] X m 7→ 10
Padrão lista na notação especialO padrão
[ padrão1 ; . . . ; padrãon ]
é uma abreviação sintática para
padrão1 :: . . . :: padrãon :: []
Observe que o casamento sucede somente se o valor for uma lista com exatamente n elementos.Exemplos: o padrão [1; alfa] casa com qualquer lista de dois números que começa com 1, associando a
variável alfa ao segundo elemento da lista.
padrão valor casamento[1; alfa] [] ×
[1; alfa] [1] ×
[1; alfa] [1; 5] X alfa 7→ 5[1; alfa] [9; 5] ×
[1; alfa] [1; 2; 3] ×
7.1.7 Padrões combinadosUm padrão combinado é escrito como
pad1 | ... | padn
7-4
onde pad1, . . . , padn são padrões. O casamento de um padrão combinado sucede se e somente se o casamento deum dos padrões padi sucede.
Qualquer variável que seja usada em um padrão combinado deve ocorrer em todos os padrões da combinação.Exemplos de padrões combinados:
• O padrão ’a’|’e’|’i’|’o’|’u’ casa com qualquer caracter que seja uma das vogais a, e, i, o ou u:
padrão valor casamento’a’|’e’|’i’|’o’|’u’ ’a’ X’a’|’e’|’i’|’o’|’u’ ’e’ X’a’|’e’|’i’|’o’|’u’ ’H’ ×
• O padrão [x]|[x;_]|[x;_;_] casa com qualquer lista de até três elementos e seleciona o primeiro ele-mento da lista:
padrão valor casamento[x]|[x;_]|[x;_;_] [] ×
[x]|[x;_]|[x;_;_] [10] X x 7→ 10[x]|[x;_]|[x;_;_] [10; 20] X x 7→ 10[x]|[x;_]|[x;_;_] [10; 20; 30] X x 7→ 10[x]|[x;_]|[x;_;_] [10; 20; 30; 40] ×
• O padrão (0,k)|(k,1) casa com pares onde o primeiro componente é 0, selecionando o segundo compo-nente, ou onde o segundo elemento é 1, selecionando o primeiro componente:
padrão valor casamento(0,k)|(k,1) (0, 3) X k 7→ 3(0,k)|(k,1) (7, 1) X k 7→ 7(0,k)|(k,1) (0, 1) X k 7→ 1(0,k)|(k,1) (4, 5) ×
7.1.8 Padrões faixaO padrão
c1 .. c2
onde c1 e c2 são literais caracter, casa com qualquer caracter na faixa de valoes entre c1 e c2, inclusive.Exemplos:
padrão valor casamento’a’..’z’ ’a’ X’a’..’z’ ’h’ X’a’..’z’ ’M’ ×
’a’..’z’ ’#’ ×
’0’..’9’ ’8’ X’0’..’9’ ’h’ ×
7.1.9 Padrões nomeadosO padrão
padrão1 as nome
onde padrão1 é um padrão e nome é um identificador de valor, casa com os mesmos valores que padrão1. Se ocasamento do padrão padrão1 sucede, o identificador nome é associado ao valor casado, além das associações devariáveis realizadas pelo casamento do padrão padrão1.
Exemplos:
padrão valor casamento(_, 0) as par (’M’, 0) X par 7→ (’M’, 0)(_, 0) as par (5, 1) ×
_::_ as lista [2; 4; 6] X lista 7→ [2; 4; 6]_::_ as lista [] ×
_::k::_ as xs [2; 4; 6] X xs 7→ [2; 4; 6]k 7→ 4
(("ana", _) as nome, _, id) (("ana", "pera"), ’f’, 19) X nome 7→ ("ana", "pera")id 7→ 19
7-5
7.2 Casamento de padrão em definições com let
Definições de variáveis com let podem ocorrer em um módulo (globais ao módulo), ou em uma expressão let(locais a uma expressão).
O lado esquerdo da definição pode ser um padrão e o lado direito deve ser uma expressão. O valor daexpressão e o padrão devem casar. Caso o casamento de padrão falhe uma exceção Match_failure é lançada.
Por exemplo:
# let (prefixo, sufixo) = List.split [(10,"ana"); (20,"pedro"); (30,"carlos")];;val prefixo : int list = [10; 20; 30]val sufixo : string list = ["ana"; "pedro"; "carlos"]
# let tupla = 1.2, 3.4, 0.75, 0.11;;val tupla : float * float * float * float = (1.2, 3.4, 0.75, 0.11)
# let x, y, z, w = tupla;;val x : float = 1.2val y : float = 3.4val z : float = 0.75val w : float = 0.11
Portanto o lado esquerdo na definição com let pode ser um padrão. Em geral é recomendável usar no letapenas padrões irrefutáveis, ou seja, padrões cujo casamento não podem falhar, para evitar a ocorrência de umaexceção caso o casamento falhe. Veja os exemplos:
# let _ :: segundo :: _ = [10; 20; 30; 40; 50];;Warning 8: this pattern-matching is not exhaustive.Here is an example of a value that is not matched:[]val segundo : int = 20
# let _ :: segundo :: _ = [10];;Warning 8: this pattern-matching is not exhaustive.Here is an example of a value that is not matched:[]Exception: Match_failure ("//toplevel//", 1, 4).
7.3 Definição de função usando padrões
Em uma definição de função em OCaml os parâmetros que representam os argumentos são padrões. Istosignifica que eles não precisam ser necessariamente variáveis, como na maioria das linguagens convencionais,mas podem ser padrões de qualquer uma das formas existentes na linguagem.
Quando a função é aplicada a seus argumentos, é feito o casamento de padrão entre os argumentos e osrespectivos parâmetros da função. Se algum dos casamentos de padrão falhar ocorre uma exceção que, se nãofor tratada no programa, culmina em um erro de execução.
Geralmente o uso de padrões para especificar os argumentos torna a definição da função mais clara e concisa.Exemplo: a função maximo resulta no maior componente de um par de inteiros:
let maximo par =let x = fst par inlet y = snd par inif x > y thenx
elsey
Nesta definição par é um padrão variável e casa com qualquer argumento.
maximo (20, 30) 30maximo (2+3, 2-3) 5
7-6
Alternativamente a função maximo pode ser definida usando um padrão mais específico para pares que permitaacessar diretamente os seus componentes:
let maximo (x, y) =if x > y thenx
elsey
Nesta versão o parâmetro formal é o padrão (x, y) que casa com qualquer par associando x ao primeiro com-ponente, e y ao segundo componente do par.
Outros exemplos:
let fst (x,_) = x
let snd (_,y) = y
fst (1+2, 1-2) 3snd (5/2, 5>2) true
Tarefa 7.1: Distância entre dois pontos
A distância entre dois pontos (x1, y1, z1) e (x2, y2, z2) no espaço é dada por√(x1 − x2)2 + (y1 − y2)2 + (z1 − z2)2
Defina uma função que recebe dois pontos no espaço e retorna a distância entre eles. Considere queum ponto no espaço é representado por uma tripla de números que são as coordenadas do ponto. Usecasamento de padrão.
Tarefa 7.2
Estude a seguinte definição e apresente uma definição alternativa mais simples desta função, usandopadrões.
let opp z =if fst z = 1 thenfst (snd z) + snd (snd z)
elseif fst z = 2 thenfst (snd z) - snd (snd z)
else0
Tarefa 7.3: Comparação de frações
Considere um uma fração é representada por um par de números inteiros. Defina uma função compara_fracaoque recebe duas frações como argumentos e retorna -1, 0, ou 1 caso a primeira seja menor, igual, ou maiordo que a segunda, respectivamente.
7.4 Expressão de Seleção Múltipla
A expressão match é uma forma de expressão que permite selecionar um entre vários resultados alternativosbaseando-se em casamento de padrões. Uma expressão match é formada por:
• uma expressão de controle, cujo valor é usado para escolher uma das alternativas
• uma sequência de alternativas, onde cada alternativa é formada por:
7-7
– um padrão, usado para decidir se a alternativa será escolhida
– uma expressão, usada para dar o resultado caso a alternativa seja escolhida
Exemplo:
match calculo x (y / 2) with| 0 -> x*x + 5*x + 6;| 1 -> 4*y - 8;| n -> (x*x + y*y) / n
7.4.1 Forma e regras de tipo da expressão matchUma expressão match é da forma:
match exp with| padrão1 -> res1
|...
| padrãon -> resn
onde:
• a expressão de controle é exp
• os resultados alternativos são dados pelas expressões res1, . . . , resn , selecionados pelos respectivos pa-drões padrão1, . . . , padrãon
• a barra vertical | que precede o primeiro padrão é opcional.
Regras de tipo:
• a expressão de controle exp e os padrões padrão1, . . . , padrãon devem ser todos de um mesmo tipo
• os resultados res1, . . . , resn devem ser todos de um mesmo tipo, e este será o tipo da expressão match (ouseja, o tipo do resultado final)
7.4.2 Avaliação de expressões match
• É feito o casamento de padrão do valor de exp com os padrões, na sequência em que foram escritos, atéque se obtenha sucesso ou se esgotem os padrões
• O primeiro padrão cujo casamento suceder é escolhido
• O resultado final da expressão match é dado pela expressão associada ao padrão escolhido
• O resultado é avaliado em um ambiente estendido com as associações de variáveis construídas no casa-mento de padrão
• Se a expressão não casar com nenhum dos padrões, a avaliação da expressão match falha é a exceçãoMatch_failure é lançada.
7.4.3 Exemplos de expressões matchA expressão
match 3 - 2 + 1 with| 0 -> "zero"| 1 -> "um"| 2 -> "dois"| 3 -> "tres"
resulta em "dois", pois o valor da expressão 3-2+1 é 2, que casa com o terceiro padrão 2, selecionando "dois"como resultado.
A expressão
7-8
match 23 > 10 with| true -> "beleza!"| false -> "oops!"
resulta em "beleza!", pois o valor da expressão 23 > 10 é true, que casa com o primeiro padrão true,selecionando "beleza!" como resultado.
A expressão
match Char.uppercase (String.get "masculino" 0) with| ’F’ -> 10.2| ’M’ -> 20.0
resulta em 20.0, pois o valor da expressão Char.uppercase (String.get "masculino" 0) é ’M’, que casacom o segundo padrão ’M’, selecionando 20.0 como resultado.
A avaliação da expressão
match String.get "masculino" 0 with| ’F’ -> 10.2| ’M’ -> 20.0
falha, pois o valor da expressão String.get "masculino" 0 não casa com nenhum dos padrões, fazendo comque uma exceção Match_failure seja lançada.
A expressão
match Char.uppercase (String.get "masculino" 0) with| ’F’ -> "mulher"| ’M’ -> 20.0
está incorreta, pois os resultados "mulher" e 20.0 não são do mesmo tipo.A expressão
match String.get "Masculino" 0 = ’F’ with| true -> "mulher"| 1 -> "homem"
está incorreta, pois os padrões true e 1 não são do mesmo tipo.A expressão
match String.get "Masculino" 0 with| true -> "mulher"| false -> "homem"
está incorreta, pois a expressão String.get "Masculino" 0 e os padrões true e false não são do mesmotipo.
A expressão
match 3 - 2 + 1 with| x -> 11 * x
resulta em 22, pois o valor da expressão 3 - 2 + 1 é 2, que casa com o primeiro padrão x, associando a variávelx ao valor 2, e selecionando 11 * x como resultado
A expressão
match 256 mod 10 with| 7 -> 0| n -> n * 1000
resulta em 6000, pois o valor da expressão 256 mod 10 é 6, que casa com o segundo padrão n, associando avariável n ao valor 6, e selecionando n * 1000 como resultado
A expressão
7-9
match 257 mod 10 with| 7 -> 0| n -> n * 1000
resulta em 0, pois 7 é o primeiro padrão que casa com o valor da expressão 257 mod 10.Já a expressão
match 257 mod 10 with| n -> n * 1000| 7 -> 0
resulta em 7000, pois n é o primeiro padrão que casa com o valor da expressão 257 mod 10.Observe que quando os padrões não são mutuamente exclusivos a ordem em qua as alternativas são escritas
pode influenciar o resultado.A expressão
match 46 - 2*20 with| 0 -> "zero"| 1 -> "um"| 2 -> "dois"| 3 -> "tres"| 4 -> "quatro"| _ -> "maior que quatro"
resulta em "maior que quatro", pois _ é o primeiro padrão que casa com o valor da expressão 46 - 2*20.A expressão
match (3+2, 3-2) with| (0, 0) -> 10| (_, 1) -> 20| (x, 2) -> x*x| (x, y) -> x*y - 1
resulta em 20, pois (_, 1) é o primeiro padrão que casa com o valor da expressão (3+2, 3-2).A expressão
match List.tl [10] with| [] -> "vazia"| _ -> "nao vazia"
resulta em "vazia", pois o valor da expressão List.tl [10] casa com o padrão para lista vazia [].A expressão
match [10; 20; 30; 40] with| [] -> "lista vazia"| x::_ -> "cabeca: " ^ string_of_int x
resulta em "cabeca: 10", pois a lista [10; 20; 30; 40] casa com o padrão para lista não vazia x::_, asso-ciando x a 10.
A expressão
match [10; 11; 12; 13; 14; 15] with| x::y::z::_ -> x + y + z| _ -> 0
resulta em 33, pois a lista [10; 11; 12; 13; 14; 15] casa com o padrão x::y::z::_, associando x a 10, ycom 11 e z com 12.
A expressão
7-10
match [10; 20] with| x::y::z::_ -> x + y + z| _ -> 0
resulta em 0, pois a lista [10; 20] não casa com o primeiro padrão x::y::z::_, mas casa com o segundo _.Observe que o primeiro padrão casa somente com listas que tenham pelo menos três elementos.
A expressão
match [10; 20; 30] with| [x1; _; x3] -> x1 + x3| _ -> 0
resulta em 40, pois a lista [10; 20; 30] casa com o primeiro padrão [x1; _; x3]. Observe que este padrãocasa somente com listas que tenham exatamente três elementos.
7.4.4 Expressão match com guardas
Em uma expressão match cada padrão pode ser acompanhado de uma expressão condicional chamada guarda,introduzida pela palavra reservada when. Neste caso a alternativa somente é escolhida quando o casamento depadrão sucede e a expressão é verdadeira.
A expressão
match [100; 20; 3] with| a::b::xs when a > b -> b::a::xs| ys -> ys
resulta em [20; 100; 3], pois a lista [100; 20; 3] casa com o primeiro padrão a::b::xs e o primeiroelemento é maior do que o segundo.
No exemplo a seguir, a expressão
match ("Paulo Roberto", ’M’, 28, 69.3) with| (_, _, idade, peso) when idade < 18 -> 2. *. peso| (_, _, idade, peso) when idade < 21 -> 3. *. peso| (_, ’F’, _, peso) -> peso| (_, ’M’, idade, peso) when idade < 40 -> peso +. 10.| (_, _, _, peso) -> 0.9 *. peso
resulta em 79.3, pois a tupla ("Paulo Roberto", ’M’, 28, 69.3)
• casa com o primeiro padrão, porém a guarda não é satisfeita• casa com o segundo padrão, porém a guarda não é satisfeita• não casa com o terceiro padrão• casa com o quarto padrão, e a guarda é satisfeita, logo o resultado é dado por peso +. 10.
7.5 Exercícios
7-11
Tarefa 7.4: Avaliando expressões
Quais das seguintes expressões são legais em OCaml? Para aquelas que são legais, qual é o tipo e o valorda expressão?
1.
match 1 with1 -> 2
| _ -> 3
2.
match 2 with1 + 1 -> 2
| _ -> 3
3.let _ as s = "abc" in s ^ "def"
4.
let h (1 | 2) as i = i + 1 inh 2
Tarefa 7.5: Decomposição de tuplas
Um dos problemas com tuplas é que não há uma função geral para selecionar um de seus componentes.Suponha que tenhamos que tentar definir tal função para triplas.
let nth i (x, y, z) =match i with| 1 -> x| 2 -> y| 3 -> z| _ -> raise (Invalid_argument "nth")
1. Qual é o tipo da função nth?
2. Há alguma maneira de reescrever esta função de forma que ela permita que os elementos da tuplasejam de tipos diferentes?
Nos exercícios seguintes use casamento de padrão para definir as funções solicitadas.
Tarefa 7.6: Implicação lógica
A função implica a seguir, do tipo bool -> bool -> bool, implementa a operação de implicaçãológica de acordo com a tabela verdade que apendemos em Lógica.
let implica a b =match (a, b) with(true, true) -> true
| (true, false) -> false| (false, true) -> true| (false, false) -> true
Faça duas definições mais compactas de implica onde são usadas apenas duas alternativas no casa-mento de padrão.
7-12
Tarefa 7.7: Vogais
Defina uma função e_vogal do tipo char -> bool que verifica se um caracter é uma vogal. Usecasamento de padrão. Não use expressões condicionais.
Tarefa 7.8: Cabeça e cauda de uma lista não vazia
Defina as funções hd e tl dos tipos ’a list -> ’a e ’a list -> ’a list respectivamente, queselecionam a cabeça e a cauda respectivamente de uma lista não vazia.
Exemplos:
hd ["ivo"; "ana"; "maria"; "inês"] "ivo"tl ["ivo"; "ana"; "maria"; "inês"] ["ana"; "maria"; "inês"]hd [1] 1tl [1] []hd [] exceçãotl [] exceção
Observação: já existem as funções List.hd e List.tl na biblioteca padrão similares a estas funções.
Tarefa 7.9: Tamano de uma lista
Defina a função length do tipo ’a list -> int que recebe uma lista l e resulta no número de elemen-tos em l.
Exemplos:
length [] 0length [10; 20; 30; 40; 50] 5
Faça duas definições, uma sem recursividade de cauda e outra com recursividade de cauda.Observação: já existe a função List.length na biblioteca padrão similar a esta função.
Tarefa 7.10: Pertinência a uma lista
Defina a função mem do tipo ’a -> ’a list -> bool que recebe um valor e uma lista e verificam se ovalor é um elemento da lista.
Exemplos:
mem "ana" ["ivo"; "ana"; "maria"; "inês"] truemem 5 [1; 8; 10; 6; 48] falsemem 4.5 [] false
Observação: já existe a função List.mem na biblioteca padrão similar a esta função.
Tarefa 7.11: Todos positivos?
Defina uma função all_positive que recebe uma lista de inteiros e verifica se todos os elementos dalista são positivos.
val all_positive :: int list -> bool
Exemplos:
all_positive [1; 8; 10; 6; 48] trueall_positive [1; 8; -10; -6; 48] falseall_positive [] true
7-13
Tarefa 7.12: Seleção de um prefixo de uma lista
Defina a função prefixo do tipo int -> ’a list -> ’a list que recebe um número inteiro n e umalista l e resulta na lista dos n primeiros elementos de l.
Exemplos:
prefixo 0 [10; 20; 30; 40; 50] []prefixo 2 [10; 20; 30; 40; 50] [10; 20]prefixo 9 [10; 20; 30; 40; 50] [10; 20; 30; 40; 50]
Tarefa 7.13: Pesquisa em banco de dados
Suponha que você esteja implementando um banco de dados relacional sobre funcionários de uma em-presa onde o banco de dados é uma lista de tuplas formadas pelo nome, pela idade e pelo salário dosfuncionários.
let db =[ "Pedro", 23, 50.1;"Paulo", 40, 107.3;"Percival", 44, 100.0;"Maria", 32, 12.7;"Bruno", 29, 107.3;"Raul", 25, 88.5;"Manoel", 30, 107.3;"Vilma", 22, 71.0;
]
• Escreva uma função find_salary : string -> (string * int * float) list -> floatque retorna o salário de um funcionário, dado o seu nome e o banco de dados.
• Escreva uma função para calcular a idade média dos funcionários.
• Escreva uma função para determinar a porcentagem de funcionários que tem idade superior à idademédia de todos os funcionários.
• Escreva uma função para determinar o nome e o salário dos funcionários com idade inferior a umadada idade.
• Escreva uma função para determinar qual é o maior salário e os nomes dos funcionários que orecebem.
Tarefa 7.14: Concatenação de listas
A função append : ’a list -> ’a list -> ’a list concatena duas listas. Ela pode ser definidacomo
let rec append l1 l2 =match l1 with| [] -> l2| h :: t -> h :: append t l2
Escreva uma versão de append que apresente recursividade de cauda.
7-14
Tarefa 7.15: Invertendo uma lista
Escreva uma função rev para inverter os elementos de uma dada lista.Exemplos:
rev [] []rev [10; 1; 8; 6; -5] [-5; 6; 8; 1; 10]rev [’a’; ’e’; ’o’] [’o’; ’e’; ’a’]
Observação: já existe a função List.rev na biblioteca padrão similar a esta função.
Tarefa 7.16: Soma dos elementos de uma lista
Escreva uma função sum para somar todos os elementos de uma dada lista de números inteiros.Exemplos:
sum [] 0sum [10; 1; 8; 6; -5] 20
Tarefa 7.17: Soma cumulativa
Defina uma função que recebe uma list de números inteiros e resulta na lista da soma cumulativa de seuselementos, ito é, uma nova lista onde o i-ésimo elemento é a soma dos primeiros i elementos da listaoriginal. Por exemplo, a soma cumulativa de [1; 2; 10; 8; 4] é [1; 3; 13; 21; 25].
Tarefa 7.18: Lista ordenada?
Escreva uma função is_sorted que verifica se uma dada lista está ordenada em ordem crescente.Exemplos:
is_sorted [] trueis_sorted [10; 1; 8; 6; -5] falseis_sorted [-5; 1; 6; 8; 10] true
Tarefa 7.19: Convertendo entre strings e listas de caracteres
Escreva uma função que converte uma lista de caracteres em string e outra que converte uma string emuma lista de caracteres.
Tarefa 7.20: Remove elementos da uma lista
Defina a função strip : ’a list -> ’a list -> ’a list que, dadas duas listas, retira da segundatodos os elementos que ocorrem na primeira.
Exemplos:
strip [1; 5] [1; 2; 5; 5; 3; 5; 1] [2; 3]strip [’a’] [’b’; ’a’; ’t’; ’a’; ’t’; ’a’] [’b’; ’t’; ’t’]
7-15
Tarefa 7.21: Marcadores em listas
Uma lista pode ser dividida em sublistas, com base em elementos especiais chamados marcadores quedizem quando começa uma lista e quando acaba outra.
1. Defina a função splitToken : ’a -> ’a list -> ’a list list que recebe um valor e umalista e retorna uma lista de listas utilizando o valor dado como marcador.
Exemplos:
splitToken 2 [1; 2; 3; 4; 2; 5; 67; 8; 9; 0; 3] [[1]; [3; 4]; [5; 67; 8; 9; 0; 3]]
splitToken 3 [1; 2; 3; 4; 2; 5; 67; 8; 9; 0; 3] [[1; 2]; [4; 2; 5; 67; 8; 9; 0]; []]
splitToken 0 [0; 1; 2; 0; 3; 4; 0; 0] [[]; [1; 2]; [3; 4]; []; []]
splitToken ’ ’ [’O’; ’C’; ’a’; ’m’; ’l’; ’ ’; ’i’; ’s’; ’ ’; ’c’; ’o’; ’o’; ’l’] [[’O’; ’C’; ’a’; ’m’; ’l’]; [’i’; ’s’]; [’c’; ’o’; ’o’; ’l’]]
splitToken ’ ’ [’c’; ’o’; ’o’; ’l’] [[’c’; ’o’; ’o’; ’l’]]
2. Defina a função joinToken : ’a -> ’a list list -> ’a list que recebe um valor e umalista de listas e retorna a concatenação das sublistas usando o primeiro parâmetro como separador.
Exemplo:
joinToken ’ ’ [[’t’; ’h’; ’i’; ’s’]; [’i’; ’s’]; [’a’]; [’t’; ’e’; ’s’; ’t’]] [’t’; ’h’; ’i’; ’s’; ’ ’; ’i’; ’s’; ’ ’; ’a’; ’ ’; ’t’; ’e’; ’s’; ’t’]
Tarefa 7.22: Agrupamento
Defina a função group :: ’a list -> ’a list list que agrupa elementos semelhantes em sublis-tas.
Exemplo:
group [2; 3; 3; 2; 1; 4; 4; 4] [[2]; [3; 3]; [2]; [1]; [4; 4; 4]]
7-16
8 OcaIDE
ResumoO ambiente de desenvolvimento integrado OcaIE traz para você o poder do Eclipse para a sua
programação diária em OCaml.Nesta aula vamos usar esta IDE para o desenvolvimento de programas em OCaml.
Sumário8.1 OcaIDE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8-18.2 Desenvolvimento de projetos Ocaml . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8-2
8.1 OcaIDE
A home page do OcaIDE é http://www.algo-prog.info/ocaide.Instruções para instalação do ambiente encontram-se na seção1.3.4.Os principais recursos oferecidos por este ambiente de desenvolvimento integrado são:
• Editor de código fonte para módulos (arquivos ml), interfaces (arquivios mli), analisadores sintáticos (ar-quivios mly) e analisadores léxicos (arquivos mll).
• Marcação de sintaxe (cores e estilos são configuráveis).
• Indentação automática durante a digitação no editor (configurável nas preferências).
• Um formatador de código integrado personalizável, e uma interface para o formatador camlp4 (através deum impressor de AST).
• Possibilidade de completar nomes automaticamente no editor.
• Navegador de bibliotecas, tanto para as bibliotecas padrão como para as definidas pelo usuário.
• Depurador integrado (uma interface gráfica para o depurador em modo de texto do OCaml), com suporte adepuração remota e suporte de arquivo script.
• Destaque de delimitadores correspondentes, como por exemplo parênteses.
• Ambiente toplevel integrado.
• Criação de ambientes toplevels personalizados.
• Pré-processamento com Camlp4.
• Uma perspectiva OCaml dentro de Eclipse.
• Atalhos para os elementos OCaml no Eclipse.
• Construção de projetos OCaml (com ocamlbuild, com makefile escrito à mão, com OcamlMakefile ougeridos pelo IDE).
• Importação e exportação de projetos OCaml.
• Lançamento de executáveis OCaml com parâmetros e console interativo.
• Outline e Quick Outline.
• Mostra o tipo inferido de elementos no editor e outline.
• Menus de contexto descritivos sobre definições OCaml.
• Ajuda sobre parâmetros esperados para as funções, exceções e construtores de dados.
8-1
• Atalhos configuráveis.
• Caminhos configuráveis para todas as ferramentas (e os caminhos são automaticamente detectados).
• Geração de makefile sob demanda.
• Geração automática de interface.
• Hiperlinks para saltar para a definição de um elemento (variável, tipo de construtor ...).
• Marcadores de erro no editor, na margem do editor, na visão de navegador e na visão de problemas.
• Modelos de código editáveis.
• Detecção automática de caminhos do projeto.
• Comentando e descomentando blocos de código.
• Verificação ortográfica dos comentários e dos comentários de documentação.
• Alternar entre módulo e interface.
• Conversão de arquivos entre as sintaxes revista e padrão (com Camlp4).
8.2 Desenvolvimento de projetos Ocaml
Estude o tutorial disponível em http://www.algo-prog.info/ocaide/tutorials/3-projects/projects.htm para aprender a desenvolver projetos OCaml com o OcaIDE.
Tarefa 8.1: Hello, world!
Crie um projeto usando o EclipseFP para uma aplicação que simplesmente exibe uma mensagem deboas-vindas na saída padrão.
8-2
9 Programas Interativos
ResumoProgramas interativos se comunicam com o usuário recebendo dados e exibindo resultados. Nesta
aula vamos aprender como desenvolver programs funcionais que interagem com o uusuário.
Sumário9.1 Interação com o mundo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9-19.2 Expressão sequência . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9-1
9.2.1 Ignorando o resultado de uma expressão . . . . . . . . . . . . . . . . . . . . . . . . . . 9-29.2.2 Blocos de programa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9-2
9.3 Estrutura de um programa em OCaml . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9-29.4 Canais de entrada e saída . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9-59.5 Funções de saída na saída padrão . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9-59.6 Funções de saída na saída de erro padrão . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9-69.7 Funções de entrada na entrada padrão . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9-69.8 Exercícios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9-6
9.1 Interação com o mundo
Programas interativos podem exibir mensagens para o usuário e obter valores informados pelo usuário. Deforma geral um programa poderá trocar informações com o restante do sistema computacional para obter dadosdo sistema computacional e gravar dados no sistema computacional.
Em linguagens imperativas as operações de entrada e saída produzem efeitos colaterais, refletidos na atuali-zação de variáveis globais que representam o estado do sistema de computação.
Já em linguagens declarativas as operações de entrada e saída são puras e não produzem efeito colateralvisível diretamente no programa. Estas operações são integradas na linguagem usando mecanismos como açõesde entrada e saída que podem ser combinadas sequencialmente para formar novas ações, mas que somente sãoexecutadas quando passadas para o sistema operacional. Este é o modelo adotado pela linguagem Haskell. Aliguagem Clean já usa um outro modelo que integra ao sistema de tipos da linguagem o conceito de tipos únicospara acomadar a possibilidade atualização de variáveis como uma otimização do compilador.
Sendo uma linguagem multi-paradigma, OCaml suporta a programação imperativa. Em OCaml operações deentrada e saída são implementadas através de produção de efeito colateral. Uma expressão em OCaml, quandoavaliada, tem um valor e pode ter um efeito.
9.2 Expressão sequência
Uma expressão sequência é formada por uma sequência de expressões separadas por ponto-e-vírgula (;):
exp1 ; ...; expn
A sua avaliação é feita pela avaliação de cada uma das expressões expi na ordem em que foram escritas. O tipo e ovalor da expressão sequência são dados respectivamente pelo tipo e pelo valor da última expressão da sequência.
Os valores das expressões da sequência, exceto da última, são descartados. Logo estas expressões serão inte-ressantes somente se elas produzirem algum efeito. Para lembrar que seus valores são descartados, o compiladoremite um aviso caso o seu tipo não seja unit.
Exemplos:
# 2 * 3 ; 2 + 3 ;;Warning 10: this expression should have type unit.- : int = 5
# print_string "resultado: " ; print_int 10 ; print_newline () ; true ;;
9-1
resultado: 10- : bool = true
# print_int 1; 2 ; 3;;Warning 10: this expression should have type unit.1- : int = 3
9.2.1 Ignorando o resultado de uma expressãoval ignore : ’a -> unit
Descarta o valor de seu argumento e retorna (). Por exemplo, ignore (f x) descarta o resultado dafunção f, que espera-se produzir algum efeito colateral. É equivalente a f x; (), exceto que este podegerar um aviso do compilador; por outro lado escrevendo-se ignore (f x) evita-se o aviso.
Exemplos:
# ignore (2 * 3);;- : unit = ()
# ignore (2 * 3); 2 + 3;;- : int = 5
9.2.2 Blocos de programaPara delimitar um grupo de expressões podemos utilizar parênteses:
( expr )
ou as palavras reservadas begin e end:
begin expr end
Exemplos:
# ( print_int (2+3); 2-3 );;5- : int = -1
# begin print_int (2+3); 2-3 end;;5- : int = -1
9.3 Estrutura de um programa em OCaml
Código em OCaml pode ser compilado separadamente e executado de forma não interativa utilizando oscompildores ocamlc e ocamlopt.
O código-fonte deve ser colocado em um arquivo com extensão .ml. Ele consiste de uma seqüência de frases,que serão avaliadas em tempo de execução em sua ordem de aparição no arquivo de origem. Ao contrário nomodo interativo, tipos e valores não são impressos automaticamente; o programa deve chamar as funções deimpressão explicitamente para produzir alguma saída.
Aqui está um exemplo de programa autônomo para imprimir números de Fibonacci:
(* File fib.ml *)
let rec fib n =if n < 2 then 1 else fib (n-1) + fib (n-2)
let main () =let arg = int_of_string Sys.argv.(1) inprint_int (fib arg);print_newline ()
let _ = main ()
9-2
Sys.argv é um array de strings contendo os parâmetros de linha de comando. Sys.argv.(1) é, assim, oprimeiro parâmetro de linha de comando. O programa acima é compilado e executado com os seguintes comandosno shell:
$ ocamlc -o fib fib.ml
$ ./fib 1089
$ ./fib 2010946
Programas OCaml autônomos mais complexos são geralmente compostos de vários arquivos fonte, e podemligar com bibliotecas pré-compiladas. A recompilaçào de projetos OCaml multi-arquivos pode ser automatizadausando o gerenciador de compilação ocamlbuild.
9-3
Tarefa 9.1: Preparando e executando um programa no OcaIDE
1. Grave o código fonte do programa apresentado em um arquivo texto chamado fib.ml.
(* File fib.ml *)
let rec fib n =if n < 2 then 1 else fib (n-1) + fib (n-2)
let main () =let arg = int_of_string Sys.argv.(1) inprint_int (fib arg);print_newline ()
let _ = main ()
2. Compile o programa usando o compilador ocamlc em um terminal:
$ ocamlc -o fib fib.ml
3. Execute o programa já compilado:
$ $ ./fib 1089
4. Compile o programa usando o compilador ocamlopt em um terminal e execute o programa:
$ ocamlopt -o fib fib.ml
$ $ ./fib 1089
5. Compile o programa usando o gerenciador de compilação ocamlbuild em um terminal gerandobytecodes e execute o programa:
$ ocamlbuild fib.byte
$ $ ./fib.byte 1089
6. Compile o programa usando o gerenciador de compilação ocamlbuild em um terminal gerandocódigo nativo e execute o programa:
$ ocamlbuild fib.native
$ $ ./fib.ntive 1089
9-4
Tarefa 9.2: Preparando e executando um programa em OCaml no Eclipse
Use o ambiente de desenvolvimento integrado OcaIDE para preparar e executar o seguinte programa:
let _ =print_endline "Somando dois números:";print_endline "==========================================";print_string " digite um número inteiro.......: ";let x = read_int () inprint_string " digite outro número inteiro....: ";let y = read_int () inlet z = x + y inprint_string " soma calculada.................: ";print_int z;print_newline ()
9.4 Canais de entrada e saída
Os dispositivos de entrada e saída em OCaml são representados por canais de entrada e saída:
type in_channelTipo dos canais de entrada.
type out_channelTipo dos canais de saída.
Os dispositivos de entrada e saída padrão são representados pelas seguintes variáveis:
val stdin : in_channelDispositivo de entrada padrão.
val stdout : out_channelDispositivo de saída padrão.
val stderr : out_channelDispositivo de saída de erro padrão.
9.5 Funções de saída na saída padrão
val print_char : char -> unitImprime um caracter na saída padrão.
val print_string : string -> unitImprime uma string na saída padrão.
val print_bytes : bytes -> unitImprime uma seqüência de bytes na saída padrão.
val print_int : int -> unitImprime um inteiro, em notaçao decimal, na saída padrão.
val print_float : float -> unitImprime um número em ponto flutuante, em notaçào decimal, na saída padrão.
val print_endline : string -> unitImprime uma string, seguido de um caractere de nova linha, na saída padrão e descarrega1 a saída padrão.
val print_newline : unit -> unitImprime um caractere de nova linha na saída padrão, e descarrega a saída padrão. Isso pode ser usado parasimular bufferização de linha da saída padrão.
1Basicamente descarregar um canal de saída consiste em completar as operações de saída pendentes associadas ao canal.
9-5
9.6 Funções de saída na saída de erro padrão
val prerr_char : char -> unitImprime um caracter na saída de erro padrão.
val prerr_char : char -> unitImprime um caracter na saída de erro padrão.
val prerr_string : string -> unitImprime uma string na saída de erro padrão.
val prerr_bytes : bytes -> unitImprime uma seqüência de bytes na saída de erro padrão.
val prerr_int : int -> unitImprime um inteiro, em decimal, na saída de erro padrão.
val prerr_float : float -> unitImprime umnúmero em ponto flutuante na saída de erro padrão.
val prerr_endline : string -> unitImprime uma string, seguido de um caractere de nova linha na saída de erro padrão e descarrega a saída deerro padrão.
val prerr_newline : unit -> unitImprime um caractere de nova linha na saída de erro padrão, e descarrega a saída de erro padrão.
9.7 Funções de entrada na entrada padrão
val read_line : unit -> stringDescarrega a saída padrão, e então lê os caracteres da entrada padrão até que um caractere de nova linhaseja encontrado. Retorna a string de todos os caracteres lidos, sem o caractere de nova linha no final.
val read_int : unit -> intDescarrega a saída padrão, e em seguida lê uma linha da entrada padrão e converte-a para um númerointeiro. Lança a exceção Failure "int_of_string" se a linha lida não é uma representação válida deum inteiro.
val read_float : unit -> floatDescarrega a saída padrão, e em seguida lê uma linha da entrada padrão e converte-a para um númeroem ponto flutuante. O resultado não é especificado se a linha lida não é uma representação válida de umnúmero de ponto flutuante.
9.8 Exercícios
Tarefa 9.3: Produto de três números
Escreva um programa que solicita ao usuário três números em ponto flutuante, lê os números, e calcula eexibe o produto dos números.
Exemplo de execução da aplicação
Digite um número: 10.0Digite outro número: 2.3Digite outro número: 5.0Produto dos números digitados: 115.0
9-6
Tarefa 9.4: Produto de três números
Escreva um programa que solicita ao usuário três números em ponto flutuante, lê os números, e calcula eexibe o produto dos números.
Exemplo de execução da aplicação
Digite um número: 10.0Digite outro número: 2.3Digite outro número: 5.0Produto dos números digitados: 115.0
Tarefa 9.5: Linha de crédito
A prefeitura de Contagem abriu uma linha de crédito para os funcionários estatutários. O valor máximoda prestação não poderá ultrapassar 30% do salário bruto.
Fazer um programa que permita entrar com o salário bruto e o valor da prestação, e informar se oempréstimo pode ou não ser concedido.
Exemplo de execução da aplicação
Análise de crédito-------------------------------------------Salário bruto: 1000Valor da prestação: 20O empréstimo pode ser concedido
Exemplo de execução da aplicação
Análise de crédito-------------------------------------------Salário bruto: 1000Valor da prestação: 430.23O empréstimo não pode ser concedido
9-7
Tarefa 9.6: Classe eleitoral
Crie um programa que leia a idade de uma pessoa e informe a sua classe eleitoral:
não eleitor abaixo de 16 anos;
eleitor obrigatório entre 18 (inclusive) e 65 anos;
eleitor facultativo de 16 até 18 anos e acima de 65 anos (inclusive).
Exemplo de execução da aplicação
Classe eleitoral-------------------------------------------Digite a idade da pessoa: 11não eleitor
Exemplo de execução da aplicação
Classe eleitoral-------------------------------------------Digite a idade da pessoa: 17eleitor facultativo
Exemplo de execução da aplicação
Classe eleitoral-------------------------------------------Digite a idade da pessoa: 20eleitor obrigatório
Exemplo de execução da aplicação
Classe eleitoral-------------------------------------------Digite a idade da pessoa: 73eleitor facultativo
Tarefa 9.7: Situação de um aluno
Faça um programa que receba três notas de um aluno, e calcule e mostre a média aritmética das notas e asituação do aluno, dada pela tabela a seguir.
média das notas situaçãomenor que 3 reprovadoentre 3 (inclusive) e 7 exame especialacima de 7 (inclusive) aprovado
Exemplo de execução da aplicação
Digite as três notas do aluno:9.12.97.4Média: 6.46666666667
9-8
Tarefa 9.8: Peso ideal
Escreva um programa que solicita ao usuário a altura (em metros) e o sexo de uma pessoa, lê estes dados,calcula o peso ideal da pessoa segundo a tabela a seguir (onde h é a altura da pessoa), e exibe o resultado.
sexo peso idealmasculino 72.7 × h − 58feminino 62.1 × h − 44.7
Exemplo de execução da aplicação
Altura (em metros).....: 1.72Sexo (f/m).............: fPeso ideal.............: 62.112
Exemplo de execução da aplicação
Altura (em metros).....: 1.72Sexo (f/m).............: mPeso ideal.............: 67.044
Exemplo de execução da aplicação
Altura (em metros).....: 1.72Sexo (f/m).............: ?Sexo inválido
Exemplo de execução da aplicação
Altura (em metros).....: 1.72Sexo (f/m).............:Sexo inválido
Tarefa 9.9: Impostos
Faça um programa que apresente o menu a seguir, permita ao usuário escolher a opção desejada, recebaos dados necessários para executar a operação, e mostre o resultado.
--------------------------------Opções:--------------------------------1. Imposto2. Novo salário3. Classificação--------------------------------Digite a opção desejada:
Verifique a possibilidade de opção inválida.Na opção 1 receba o salário de um funcionário, calcule e mostre o valor do imposto sobre o salário
usando as regras a seguir:
salário taxa de impostoAbaixo de R$500,00 5%De R$500,00 a R$850,00 10%Acima de R$850,00 15%
Na opção 2 receba o salário de um funcionário, calcule e mostre o valor do novo salário, usando asregras a seguir:
salário aumentoAcima de R$1.500,00 R$25,00De R$750,00 (inclusive) a R$1.500,00 (inclusive) R$50,00De R$450,00 (inclusive) a R$750,00 R$75,00Abaixo de R$450,00 R$100,00
9-9
Na opção 3 receba o salário de um funcionário e mostre sua classificação usando a tabela a seguir:
salário classificaçãoAté R$750,00 (inclusive) mal remuneradoAcima de R$750,00 bem remunerado
Exemplo de execução da aplicação
Análise de salário--------------------------------Opções:--------------------------------1. Imposto2. Novo salário3. Classificação--------------------------------Digite a opção desejada: 1
Cálculo do impostoDigite o salário: 700Imposto calculado: 70.0
Exemplo de execução da aplicação
Análise de salário--------------------------------Opções:--------------------------------1. Imposto2. Novo salário3. Classificação--------------------------------Digite a opção desejada: 2
Cálculo do novo salárioDigite o salário: 700Novo salário: 775
Exemplo de execução da aplicação
Análise de salário--------------------------------Opções:--------------------------------1. Imposto2. Novo salário3. Classificação--------------------------------Digite a opção desejada: 3
Classificação do salárioDigite o salário: 700Classificação obtida: mal remunerado
9-10
Exemplo de execução da aplicação
Análise de salário--------------------------------Opções:--------------------------------1. Imposto2. Novo salário3. Classificação--------------------------------Digite a opção desejada: 4
Opção inválida!
Tarefa 9.10: Terno pitagórico
Em Matemática um terno pitagórico (ou trio pitagórico, ou ainda tripla pitagórica) é formado por trêsnúmeros a, b e c tais que a2+b2 = c2. O nome vem do teorema de Pitágoras que afirma que se as medidasdos lados de um triângulo retângulo são números inteiros, então elas formam um terno pitagórico.
Codifique um programa que leia três números positivos e verifique se eles formam um terno pitagó-rico.
Exemplo de execução da aplicação
Verificação de ternos pitagóricos-----------------------------------------Digite o primeiro número positivo .....: 3Digite o segundo número positivo ......: 4Digite o terceiro número positivo .....: 5Os números formam um terno pitagórico
Exemplo de execução da aplicação
Verificação de ternos pitagóricos-----------------------------------------Digite o primeiro número positivo .....: 6Digite o segundo número positivo ......: 5Digite o terceiro número positivo .....: 4Os números não formam um terno pitagórico
Exemplo de execução da aplicação
Verificação de ternos pitagóricos-----------------------------------------Digite o primeiro número positivo .....: 3Digite o segundo número positivo ......: -4Digite o terceiro número positivo .....: 0Números inválidos
9-11
Tarefa 9.11: Palíndromes
Escreva um programa que solicita ao usuário para digitar uma frase, lê a frase (uma linha) da entradapadrão e testa se a string lida é uma palíndrome, exibindo uma mensagem apropriada.
Exemplo de execução da aplicação
Digite uma frase:abcddcbaÉ uma palíndrome.
Exemplo de execução da aplicação
Digite uma frase:ABCdCBAÉ uma palíndrome.
Exemplo de execução da aplicação
Digite uma frase:ouro pretoNão é uma palíndrome.
Tarefa 9.12: Soma de uma sequência com sentinela
Escreva um programa que obtém uma sequência de números inteiros até encontrar um valor negativo, emostra a soma dos números lidos. O valor negativo é uma sentinela usada para indicar o final da entradae não faz parte da sequência.
Exemplo de execução da aplicação
Digite uma sequência de números (um por linha).Para terminar digite um número negativo.135017-3Soma: 26.000000
Tarefa 9.13: Soma de uma sequência
Faça um programa que leia um número natural n, e então leia outros n números e calcule e exiba a somadestes números.
Exemplo de execução da aplicação
Quantidade de números: 4Digite um número: 10Digite um número: -5Digite um número: 1Digite um número: 20Soma dos números digitados: 26.000000
Exemplo de execução da aplicação
Quantidade de números: -6Soma dos números digitados: 0.000000
9-12
Tarefa 9.14: Média aritmética de uma sequência de números
Faça um programa que leia uma seqüência de números não negativos e determine a média aritméticadestes números. A entrada dos números deve ser encerrada com um número inválido (negativo).
Exemplo de execução da aplicação
Cálculo da média aritmética---------------------------------------Digite uma sequência de números (um por linha)Para terminar digite um valor negativo10989.2-1A média dos números digitados é 9.171428571428573
Exemplo de execução da aplicação
Cálculo da média aritmética---------------------------------------Digite uma sequência de números (um por linha)Para terminar digite um valor negativo-5Sequência vazia
Tarefa 9.15: Perda de massa por radioatividade
Um elemento químico radioativo perde sua massa de acordo com a função
m(t) = m0e−kt
onde, t é o tempo (em segundos), m0 é a++ massa inicial (em gramas) e k é a constante 5 × 10−2.Faça uma aplicação que, dada a massa inicial desse elemento, calcule a perda de massa durante um
minuto, exibindo as massas resultantes em intervalos de 10 segundos.
Tarefa 9.16: Cálculo aproximado de π
A série abaixo converge para o número π quando n → ∞.
4n∑i=0
(−1)i
2i + 1
Codifique um programa que solicita ao usuário o número de parcelas da série e calcula e exibe o valoraproximado de π usando o número solicitado de parcelas.
Tarefa 9.17: Aumento salarial
Um funcionário de uma empresa recebe aumento salarial anualmente. O primeiro aumento é de 1,2%sobre seu salário inicial. Os aumentos subsequentes sempre correspondem ao dobro do percentual de au-mento do ano anterior. Faça uma aplicação onde o usuário deve informar o salário inicial do funcionário,o ano de contratação e o ano atual, e calcula e exibe o seu salário atual.
9-13
Tarefa 9.18: Fechamento de notas de uma disciplina
Faça uma aplicação para fechamento das notas de uma disciplina. Cada aluno recebe uma nota para cadauma das três atividades desenvolvidas. O usuário deverá informar a quantidade de alunos na turma, e emseguida as notas de cada aluno. Calcule e exiba:
• a média aritmética das três notas de cada aluno,
• a situação do aluno, dada pela tabela seguinte
média aritmética situaçãoaté 3 reprovadoentre 3 (inclusive) e 7 exame especialacima de 7 (inclusive) aprovado
• a média da turma
• o percentual de alunos aprovados
• o percentual de alunos em exame especial
• o percentual de alunos reprovados
Tarefa 9.19: Correção de provas de múltipla escolha
Faça um programa para corrigir provas de múltipla escolha que foram aplicadas em uma turma de alunos.O usuário deverá informar:
• o gabarito (as respostas corretas de cada questão) da prova
• a matrícula e as respostas de cada aluno da turma
As notas devem ser normalizadas na faixa de zero a dez. Assim para calcular a nota obtida em umaprova, divida a soma dos pontos obtidos (um ponto para cada resposta correta) pelo número de questõesna prova, e multiplique o resulado por dez.
Calcule e mostre:
1. a matrícula e a nota de cada aluno
2. a taxa (em porcentagem) de aprovação, sabendo-se que a nota mínima para aprovação é sete.
9-14
10 Valores Aleatórios
ResumoA geração de valores pseudo-aleatórios em aplicações em OCaml pode ser feita através da bibli-
oteca Random. Nesta aula vamos aprender a desenvolver aplicações que usam valores aleatórios.Estes tópicos serão usados na implementação do jogo adivinha o número.
Sumário10.1 Valores aleatórios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10-110.2 Jogo adivinha o número . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10-210.3 Jogo craps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10-610.4 Jogo nim . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10-7
10.1 Valores aleatórios
O módulo Random da biblioteca padrão do OCaml lida com a tarefa comum de geração de valores pseudo-aleatórios em OCaml.
As funções básicas para geração de números pseudo-aleatórios são:
val init : int -> unitInicializa o gerador, utilizando o argumento como uma semente. A mesma semente sempre produzirá amesma sequência de números.
val self_init : unit -> unitInicializa o gerador com uma semente aleatória escolhida de uma forma dependente do sistema. Se/dev/urandom está disponível no computador, ele é utilizada para fornecer uma semente inicial altamentealeatória. Caso contrário, uma semente menos aleatória é calculada a partir de parâmetros do sistema(tempo atual, processo de IDs).
val int : int -> intRandom.int bound retorna um inteiro aleatório entre 0 (inclusive) e bound (exclusive). bound deve sermaior do que 0 e menor do que 230.
val float : float -> floatRandom.float bound retorna um número aleatório de ponto flutuante entre 0 e bound (inclusive). Sebound é negativo, o resultado é negativo ou zero. Se bound é 0, o resultado é 0.
val bool : unit -> boolRandom.bool () retorna verdadeiro ou falso com probabilidade 0,5 cada.|
Exemplo: lançamento de dadoslancadados.ml
let _ =print_endline "Lançamento de dois dados";Random.self_init ();let x = Random.int 6 + 1 inlet y = Random.int 6 + 1 inPrintf.printf "Faces obtidas: %d e %d\n" x y
Exemplo de execução da aplicação
$ ./lancadadosLancamento de dois dadosFaces obtidas: 3 e 5
10-1
Exemplo de execução da aplicação
$ ./lancadadosLancamento de dois dadosFaces obtidas: 4 e 1
10.2 Jogo adivinha o número
Tarefa 10.1: Adivinha o número
Escreva uma aplicação para jogar o jogo adivinhe o número, como explicado a seguir.
• O programa escolhe um número a ser adivinhado pelo jogador (usuário) selecionando um númerointeiro aleatório no intervalo de 1 a 1000.
• O programa exibe a mensagem Adivinhe um número entre 1 e 1000.
• O jogador informa o seu palpite.
• Se o palpite do jogador estiver incorreto:
– o programa exibe a mensagem Muito alto ou Muito baixo convenientemente para ajudaro jogador a acertar o número nas próximas jogadas.
– o jogo continua com o programa solicitando o próximo palpite e analisando a resposta dousuário.
• Quando o jogador insere a resposta correta:
– o programa exibe a mensagem Parabéns, você adivinhou o número, e
– permite que o usuário escolha se quer jogar novamente, e joga novamente em caso afirmativo.
10-2
Exemplo de execução da aplicação
$ ./advinhaAdivinha o número v1.0=========================================Digite um número entre 1 e 1000: 444Muito grandeTente novamente
Digite um número entre 1 e 1000: 200Muito grandeTente novamente
Digite um número entre 1 e 1000: 111Muito pequenoTente novamente
Digite um número entre 1 e 1000: 157Muito grandeTente novamente
Digite um número entre 1 e 1000: 138Muito grandeTente novamente
Digite um número entre 1 e 1000: 123Muito pequenoTente novamente
Digite um número entre 1 e 1000: 130Muito grandeTente novamente
Digite um número entre 1 e 1000: 125Muito pequenoTente novamente
Digite um número entre 1 e 1000: 128Muito pequenoTente novamente
Digite um número entre 1 e 1000: 129Parabéns, você acertou
Deseja jogar novamente? n
1. Defina uma função sim_ou_nao que recebe uma string e interage com o usuário da seguinte forma:
• exibe a string na saída padrão (com o objetivo de fazer uma pergunta do tipo sim ou não aousuário)
• lê a resposta do usuário
• verifica se a resposta é
– s ou S, retornando verdadeiro– n ou N, retornando falso– qualquer outra coisa, chamando sim_ou_nao novamente para que o usuário responda
corretamente.
Use uma expressão match.
10-3
Exemplo de execução da aplicação
# sim_ou_nao "Quer jogar novamente?";;Quer jogar novamente? talvezQuer jogar novamente? kQuer jogar novamente? s- : bool = true
# sim_ou_nao "Você é inteligente?";;Você é inteligente? com certezaVocê é inteligente?Você é inteligente? acho que simVocê é inteligente? n- : bool = false
Esta função deve ser usada em jogar (item 3) para verificar se o usuário deseja continuar jogandoou não.
2. Defina uma função acertar que recebe um número a ser adivinhado e interage com o usuário daseguinte forma:
• exibe uma mensagem solicitando um número entre 1 e 1000
• lê o número informado pelo usuário
• compara o número informado com o número a ser adivinhado:
– se forem iguais, exibe uma mensagem parabenizando o usuário por ter adivinhado onúmero
– caso contrário
* exibe uma mensagem informando que o número é muito pequeno ou muito grande,adequadamente
* exibe uma mensagem solicitando ao usuário uma nova tentativa
* faz uma nova tentativa através de uma chamada recursiva de acertar
Exemplo de execução da aplicação
# acertar 119;;Digite um número entre 1 e 1000: 600Muito grande.Tente novamente.
Digite um número entre 1 e 1000: 23Muito pequeno.Tente novamente.
Digite um número entre 1 e 1000: 119Parabéns, você acertou!- : unit = ()
A função acertar deverá ser usada na definição de jogar (item 3).
3. O programa deve permitir ao usuário jogar várias vezes, o que nos leva à necessidade do uso derecursão.
Defina uma função jogar que recebe a tupla vazia como argumento e interage com o usuário daseguinte forma:
• gera um número inteiro aleatório entre 1 e 1000, inclusive
• interage com o usuário até que o usuário acerte o número (veja o item 2)
• verifica se o usuário deseja jogar novamente (veja o item 1)
– se sim, chama jogar recursivamente– se não, resulta na tupla vazia.
10-4
Exemplo de execução da aplicação
# jogar ();;Digite um número entre 1 e 1000: 509Muito pequeno.Tente novamente.
Digite um número entre 1 e 1000: 780Muito grande.Tente novamente.
Digite um número entre 1 e 1000: 640Muito grande.Tente novamente.
Digite um número entre 1 e 1000: 590Muito grande.Tente novamente.
Digite um número entre 1 e 1000: 544Muito pequeno.Tente novamente.
Digite um número entre 1 e 1000: 577Muito grande.Tente novamente.
Digite um número entre 1 e 1000: 550Muito pequeno.Tente novamente.
Digite um número entre 1 e 1000: 560Muito grande.Tente novamente.
Digite um número entre 1 e 1000: 555Muito grande.Tente novamente.
Digite um número entre 1 e 1000: 553Muito grande.Tente novamente.
Digite um número entre 1 e 1000: 551Muito pequeno.Tente novamente.
Digite um número entre 1 e 1000: 552Parabéns, você acertou!
Deseja jogar novamente? n- : unit = ()
A função jogar deve ser usada para que o usuário possa joagar o jogo (item 4).
4. Defina uma função main do tipo unit -> unit que interage com o usuário da seguinte forma:
• exibe uma mensagem identificando o programa e sua versão,
• inicializa o gerador de números aleatórios, e
• usa a função jogar (veja o item 3) para jogar o jogo adivinha o número.
Chame a função main como última ação no seu programa.
10-5
Tarefa 10.2: Adivinha o número com argumentos na linha de comando
Modifique o programa adivinha.ml (tarefa 10.1) de forma que o usuário possa especificar o intervalo aser utilizado para adivinhar o número através de dois argumentos na linha de comando.
Tarefa 10.3: Adivinha o número com contagem de tentativas
Modifique o programa adivinha.ml (tarefa 10.2) para que seja exibida o número de tentativas feitaspelo usuário toda vez que lhe é solicitado uma nova tentativa de adivinhar um número.
10.3 Jogo craps
Tarefa 10.4: Craps
Craps é um jogo de azar popular que é jogado em cassinos e nas ruas de todo o mundo. As regras do jogosão simples e diretas.
O jogador lança dois dados. Cada dado tem seis faces numeradas de um a seis. Depois que os dadosparam de rolar, a soma dos pontos nas faces viradas para cima é calculada. Se a soma for 7 ou 11 noprimeiro lance, o jogador ganha. Se a soma for 2, 3 ou 12 no primeiro lance (chamado craps), o jogadorperde (isto é, a casa ganha). Se a soma for 4, 5, 6, 8, 9 ou 10 no primeiro lance, essa soma torna-se apontuação alvo do jogador. Neste caso, para ganhar, o jogador deve continuar a lançar os dados até fazersua pontuação alvo (isto é, obter um valor igual à sua pontuação alvo, determinada no primeiro lance). Ojogador perde se obtiver um 7 antes de fazer sua pontuação alvo.
Escreva uma aplicação em OCaml para jogar o jogo craps com o usuário.
Dica 1 As únicas interaçoes com o usuáro (jogador) deverão ser para:
• solicitar que ele tecle ENTER para lançar os dados,
• exibir os pontos obtidos nas faces dos dados em cada lançamento juntamente com a pontuação(soma dos pontos nas faces dos dados), e
• exibir o resultado final (ganhou ou perdeu).
Dica 2 Exemplos de possíveis execuções do programa:
Craps v1.0-------------------------------------Tecle ENTER para lançar os dadosFaces dos dados: 1 e 6Pontuação: 7Você ganhou. Parabéns!
Craps v1.0-------------------------------------Tecle ENTER para lançar os dadosFaces dos dados: 6 e 6Pontuação: 12CRAPS!Você perdeu. Sinto muito!
Craps v1.0-------------------------------------Tecle ENTER para lançar os dadosFaces dos dados: 3 e 3Pontuação: 6
Tecle ENTER para lançar os dados novamenteFaces dos dados: 1 e 6
10-6
Pontuação: 7Você perdeu. Sinto muito!
Craps v1.0-------------------------------------Tecle ENTER para lançar os dadosFaces dos dados: 4 e 4Pontuação: 8
Tecle ENTER para lançar os dados novamenteFaces dos dados: 3 e 1Pontuação: 4
Tecle ENTER para lançar os dados novamenteFaces dos dados: 6 e 2Pontuação: 8Você ganhou. Parabéns!
10.4 Jogo nim
Tarefa 10.5: Nim
Nim é um jogo que é jogado em um tabuleiro composto por cinco linhas numeradas de estrelas, que éinicialmente definido como segue:1: * * * * *2: * * * *3: * * *4: * *5: *
Dois jogadores se alternam em remover uma ou mais estrelas do final de um única linha. O vencedor é ojogador que remove a última estrela, ou estrelas do tabuleiro.
Implementar o jogo do nim.Dica: Representar o tabuleiro como uma lista que inclui o número de estrelas restantes em cada linha.
O tabuleiro inicial é [5; 4; 3; 2; 1].
10-7
11 Expressões Lambda
ResumoExpressões lambdas são funções anônimas que podem ser usadas como qualquer outro valor de
primeira classe. Nesta aula vamos aprender sobre expressões lambda.
Sumário11.1 Valores de primeira classe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11-1
11.1.1 Valores de primeira classe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11-1
11.1.2 Valores de primeira classe: Literais . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11-1
11.1.3 Valores de primeira classe: Variáveis . . . . . . . . . . . . . . . . . . . . . . . . . . . 11-2
11.1.4 Valores de primeira classe: Argumentos . . . . . . . . . . . . . . . . . . . . . . . . . . 11-2
11.1.5 Valores de primeira classe: Resultado . . . . . . . . . . . . . . . . . . . . . . . . . . . 11-2
11.1.6 Valores de primeira classe: Componentes . . . . . . . . . . . . . . . . . . . . . . . . . 11-3
11.2 Expressão lambda . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11-311.2.1 Expressões lambda with fun . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11-3
11.2.2 Exemplos de expressões lambda . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11-3
11.2.3 Uso de expressões lambda . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11-4
11.2.4 Exercícios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11-4
11.2.5 Expressões lambda with function . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11-5
11.3 Aplicação parcial de funções . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11-511.3.1 Aplicação parcial de funções . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11-5
11.3.2 Aplicação parcial de funções: exemplos . . . . . . . . . . . . . . . . . . . . . . . . . . 11-6
11.4 Currying . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11-711.4.1 Funções curried . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11-7
11.4.2 Por que currying é útil? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11-8
11.4.3 Convenções sobre currying . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11-8
11.5 Utilidade de expressões lambda . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11-811.5.1 Exercícios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11-9
11.1 Valores de primeira classe
11.1.1 Valores de primeira classe
• Tipo de primeira classe: não há restrições sobre como os seus valores podem ser usados.
• São valores de primeira classe:
– números– caracteres– tuplas– listas– funções
entre outros
11.1.2 Valores de primeira classe: Literais
• Valores de vários tipos podem ser escritos literalmente, sem a necessidade de se dar um nome a eles:
11-1
valor tipo descriçãotrue bool o valor lógico verdadeiro’G’ char o caracter G456 int o número 4562.45 float o número em ponto flutuante 2.45"ocaml" String a cadeia de caracteres ocaml[1; 6; 4; 5] int list a lista dos inteiros 1, 6, 4, 5("Ana", false) string * bool o par formado por Ana e falso
• Funções também podem ser escritas sem a necessidade de receber um nome:
valor tipo descriçãofun x -> 3*x int -> int função que calcula o triplofun n -> n mod 2 = 0 int -> bool função que verifica se é parfun (p, q) -> p+q int * int -> int função que soma par
11.1.3 Valores de primeira classe: Variáveis• Valores de vários tipos podem ser nomeados:
let matricula = 456let sexo = ’M’let aluno = ("Jane Eyre", 101408, ’M’,"COM")let disciplinas = ["BCC222"; "BCC221"; "MTM153"; "PRO300"]let livroTexto = ("Programming in OCaml", "G. Hutton", 2007)
• Funções também podem ser nomeadas:
let triplo = fun x -> 3 * x
Esta equação define a variável triplo, associando-a a um valor que é uma função.
OCaml permite escrever esta definição de forma mais sucinta:
let triplo x = 3 * x
11.1.4 Valores de primeira classe: Argumentos• Valores de vários tipos podem ser argumentos de funções:
sqrt 2.45not trueList.length [1; 6; 4; 5]
• Funções também podem ser argumentos de outras funções:
List.map triplo [1; 2; 3] [3; 6; 9]
A função triplo é aplicada a cada elemento da lista [1; 2; 3], resultando na lista [3; 6; 9]
11.1.5 Valores de primeira classe: Resultado• Valores de vários tipos podem ser resultados de funções:
not false trueList.length [1; 6; 4; 5] 4snd ("Ana", ’F’) ’F’List.tl [1; 6; 4; 5] [6; 4; 5]
11-2
• Funções também podem ser resultados de outras funções. Considere a operação de composição de funçõesdefinida como
let (-|) f g = fun x -> f (g x)
Assim:
(abs_float -| sin) (3.0 *. 3.1415 /. 2.0) 0.999999990342226308(sqrt -| abs_float) (-9.0) 3.0
O operador binário infixo (-|) faz a composição de duas funções.
11.1.6 Valores de primeira classe: Componentes• Valores de vários tipos podem ser componentes de outros valores:
("Ana", ’F’, 18)["BCC222"; "BCC221"; "MTM153"; "PRO300"][("Ailton", 101408); ("Lidiane", 102408)]
• Funções também podem ser componentes de outros valores:
List.map (fun g -> g (-3.1415)) [abs_float; sin; cos] [3.1415; -9.26535896604902578e-05; -0.999999995707656186]
O segundo argumento de List.map é a lista das funções abs_float, sin e cos.
11.2 Expressão lambda
11.2.1 Expressões lambda with fun• Da mesma maneira que um número inteiro, uma string ou um par podem ser escritos sem ser nomeados,
uma função também pode ser escrita sem associá-la a um nome.
• Expressão lambda é uma função anônima (sem nome), formada por uma sequência de padrões represen-tando os argumentos da função, e um corpo que especifica como o resultado pode ser calculado usando osargumentos:
fun padrão1 . . . padrãon -> expressao
• O termo lambda provém do cálculo lambda (teoria de funções na qual as linguagens funcionais se baseiam),introduzido por Alonzo Church nos anos 1930 como parte de uma investigação sobre os fundamentos daMatemática.
• No cálculo lambda expressões lambdas são introduzidas usando a letra grega λ. Em OCaml usa-se apalavra reservada fun.
11.2.2 Exemplos de expressões lambdaFunção anônima que calcula o dobro de um número:
fun x -> x + x
O tipo desta expressão lambda é int -> int.Função anônima que mapeia um número x a 2x + 1:
fun x -> 2*x + 1
11-3
cujo tipo é int -> int.Função anônima que recebe três argumentos e calcula a sua soma:
fun a b c -> a + b + c
cujo tipo é int -> int -> int -> int.Definições de função usando expressão lambda:
let f = fun x -> 2*x + 1let somaPar = fun (x, y) -> x + y
é o mesmo que
let f x = 2*x + 1let somaPar (x, y) = x + y
11.2.3 Uso de expressões lambda• Apesar de não terem um nome, funções construídas usando expressões lambda podem ser usadas da mesma
maneira que outras funções.
• Exemplos de aplicações de função usando expressões lambda:
(fun x -> 2*x + 1) 8 17
(fun a -> (a, 2*a, 3*a)) 5 (5, 10, 15)
(fun x y -> sqrt (x*.x +. y*.y)) 3. 4. 5.
(fun (x1, y1) (x2, y2) -> sqrt ((x2 -. x1)**2. +. (y2 -. y1)**2.)) (6. ,7.) (9., 11.) 5.
11.2.4 Exercícios
Tarefa 11.1
Escreva uma função anônima que recebe uma tripla formada pelo nome, peso e altura de uma pessoa eresulta no seu índice de massa corporal, dado pela razão entre o peso e o quadrado da altura da pessoa.
Tarefa 11.2
Escreva uma expressão para selecionar (filtrar) os elementos múltiplos de 3 em uma lista de números.Utilize a função List.filter : (’a -> bool) -> ’a list -> ’a list. Especifique a funçãoque determina a propriedade a ser satisfeita pelos elementos selecionados usando uma expressão lambda.
Tarefa 11.3
Determine o tipo mais geral da seguinte expressão:
fun a (m, n) -> if a then (m+.n)**2. else (m+.n)**3.
11-4
Tarefa 11.4
Composição de funções é uma operação comum em Matemática, que a define como
( f ◦ g)(x) = f (g(x))
Em OCaml podemos definir uma função para compor duas outras funções dadas como argumentos.O resultado é uma função: a função composta.
Definia a função composta que recebe duas funções como argumentos e resulta na função compostadas mesmas. Use uma definição local para definir a função resultante:
let composta f g =let · · ·in· · ·
Tarefa 11.5
1. Escreva outra definição para a função composta usando uma expressão lambda para determinar oseu resultado. Nesta versão não use definições locais.
2. Determine o tipo mais geral da função composta.
3. Teste a função composta calculando o tipo e o valor da expressão
(composta (fun x -> x mod 2 = 0) String.length) "linguagens modernas"
11.2.5 Expressões lambda with functionExiste uma outra forma de escrever uma expressão lambda em OCaml onde é possível escolher entre várias
alternativas baseando-se no casamento de padrão. A função poderá ter um único argumento, porém pode-seespecificar o parâmetro formal usando vários padrões, cada um associado a uma alternativa, de maneira similar àexpressão match. Esta forma de expressão lambda é introduzida pela palavra reservada function.
function padrão1 -> res1
|...
| padrãon -> resn
Veja alguns exemplos de expressão lambda com múltiplas alternativas:Função anônima que calcula o dobro de um número:
function x -> x + x
O tipo desta expressão lambda é int -> int.Função anônima que recebe uma lista e calcula a soma de seus 2 primeiros elementos:
function [] -> 0| x::[] -> x| x::y::_ -> x + y
cujo tipo é int list -> int.
11.3 Aplicação parcial de funções
11.3.1 Aplicação parcial de funções• Uma função com múltiplos argumentos pode também ser considerada como uma função que retorna outra
função como resultado.
11-5
11.3.2 Aplicação parcial de funções: exemplos• Seja a seguinte função:
let f x y = 2*x + y
A função f recebe dois argumentos inteiros x e y e resulta na soma 2*x + y.
• Alternativamente esta função pode ser definida em duas etapas:
let f’ x =let h y = 2*x + yin h
A função f’ recebe um argumento inteiro x e resulta na função h, que por sua vez recebe um argumentointeiro y e calcula 2*x + y.
• Aplicando a função:
f’ 2 3 (f’ 2) 3 h 3 2*2 + 3 7
• As funções f e f’ produzem o mesmo resultado final, mas f foi definida de uma forma mais breve.
• Podemos ainda definir a função usando uma expressão lambda:
let f’’ x =fun y -> 2*x + y
Da mesma forma que f’, a função f’’ recebe um argumento inteiro x e resulta em uma função. Estafunção recebe um argumento inteiro y e calcula 2*x + y.
• Aplicando a função:
f’’ 2 3 (f’’ 2) 3 (fun y -> 2*2 + y) 3 2*2 + 3 7
• Podemos ainda definir a função usando duas expressões lambda:
f’’’ =fun x -> (fun y -> 2*x + y)
• Aplicando a função:
f’’’ 2 3 (fun x -> (fun y -> 2*x + y)) 2 3 (fun y -> 2*2 + y) 3 2*2 + 3 7
• Todas as versões apresentadas para a função f (f, f’, f’’ e f’’’) são equivalentes.
11-6
• Portanto a função f pode ser considerada como uma função que recebe um argumento e resulta em outrafunção que, por sua vez, recebe outro argumento e resulta na soma do dobro do primeiro argumento com osegundo argumento.
• Isto permite a aplicação parcial da função:
let g = f 5 in (g 8, g 1) (18,11)
List.map (f 2) [1; 8; 0; 19; 5] [5; 12; 4; 23; 9]
(f 2 -| String.length) "entendeu?" 13
List.filter (not -| even -| f 10) [1; 8; 0; 19; 5] [1; 19; 5]
• Outro exemplo: multiplicação de três números:
let mult x y z = x * y * z
A função mult recebe três argumentos e resulta no produto destes argumentos.
• Na verdade mult recebe um argumento de cada vez. Ou seja, mult recebe um inteiro x e resulta em umafunção que por sua vez recebe um inteiro y e resulta em outra função, que finalmente recebe um inteiro ze resulta no produto x * y * z.
• Este entendimetno fica claro quando usamos expressões lambda para definir a função de maneira alterna-tiva:
let mult’ =fun x -> fun y -> fun z -> x * y * z
11.4 Currying
11.4.1 Funções curried
• Outra opção para passar vários argumentos em uma aplicação de função é formar uma estrutura de dadoscom os dados desejados e passar a estrutura como argumento.
• Neste caso fica claro que haverá um único argumento, que é a estrutura de dados.
• Exemplo: usando uma tupla:
somaPar (x, y) = x + y
A função somaPar recebe um único argumento que é um par, e resulta na soma dos componentes do par.
• Evidentemente este mecanismo não permite a aplicação parcial da função.
• Funções que recebem os seus argumentos um por vez são chamadas de funções curried1, celebrando otrabalho de OCaml Curry no estudo de tais funções.
• Funções com mais de um argumento curried, resultando em funções aninhadas.
1Funções curried às vezes são chamadas de funções currificadas em português.
11-7
11.4.2 Por que currying é útil?• Funções curried são mais flexíveis do que as funções com tuplas, porque muitas vezes funções úteis podem
ser obtidas pela aplicação parcial de uma função curried.
• Por exemplo:
(/) 100 :: int -> int (* função que divide 100 pelo seu argumento *)
List.mem ’a’ :: string -> string (* função que verifica se ’a’ é elemento de uma lista *)
11.4.3 Convenções sobre currying• Para evitar excesso de parênteses ao usar funções curried, duas regras simples foram adotadas na linguagem
OCaml:
• A seta -> (construtor de tipos função) associa-se à direita.
• Exemplo:
int -> int -> int -> int
significa
int -> (int -> (int -> int))
• A aplicação de função tem associatividade à esquerda.
• Exemplo:
mult x y z
significa
((mult x) y) z
• A menos que seja explicitamente necessário o uso de tuplas, todas as funções em OCaml são normalmentedefinidas na forma curried.
11.5 Utilidade de expressões lambda
• Expressões lambda podem ser usadas para dar um sentido formal para as funções definidas usando curryinge para a aplicação parcial de funções.
• Exemplo:A função
let soma x y = x + y
pode ser entendida como
let soma = fun x -> (fun y -> x + y)
isto é, soma é uma função que recebe um argumento x e resulta em uma função que por sua vez recebe umargumento y e resulta em x+y.
11-8
soma fun x -> (fun y -> x + y)
soma 2 (fun x -> (fun y -> x + y)) 2 fun y -> 2 + y
soma 2 3 (fun x -> (fun y -> x + y)) 2 3 (fun y -> 2 + y) 3 2 + 3 5
• Expressões lambda também são úteis na definição de funções que retornam funções como resultados.
• Exemplo:A função const definida na biblioteca retorna como resultado uma função constante, que sempre resultaem um dado valor:
let const x _ = x
const 6 0 6const 6 1 6const 6 2 6const 6 9 6const 6 75 6
h = const 6 \_ -> 6
h 0 6h 4 6h 75 6
A função const pode ser definida de uma maneira mais natural usando expressão lambda, tornando explí-cito que o resultado é uma função:
const x =fun _ -> x
• Expressões lambda podem ser usadas para evitar a nomeação de funções que são referenciados apenas umavez.
11.5.1 Exercícios
Tarefa 11.6
Mostre como a definição de função curried
let mult x y z = x * y * z
pode ser entendida em termos de expressões lambda.Dica: Redefina a função usando expressões lambda.
11-9
12 Funções de Ordem Superior
ResumoUma função é conhecida como função de ordem superior quando ela tem uma função como
argumento ou resulta em uma função. Nesta aula vamos aprender sobre funções de ordem superior.
Sumário12.1 Funções de Ordem Superior . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12-1
12.2 Composição de funções . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12-1
12.3 A função List.filter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12-2
12.4 A função map . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12-3
12.5 fold_left . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12-3
12.6 fold_right . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12-4
12.7 Cupom fiscal do supermercado . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12-5
12.1 Funções de Ordem Superior
Uma função de ordem superior é uma função que
• tem outra função como argumento, ou
• produz uma função como resultado.
12.2 Composição de funções
Composição de funções é uma operação comum na Matemática. Dadas duas funções f e g, a função compostaf ◦ g é definida por
( f ◦ g)(x) = f (g(x))
Ou seja, quando a função composta f ◦ g é aplicada a um argumento x, primeiramente g é aplicada a x, e emseguida f é aplicada a este resultado gx.
Embora a operação de composição de funções seja muito utilizada na programação funcional, ela não édefinida na biblioteca padrão de OCaml. Porém ela pode ser facilmente definida, como pode ser visto a seguir.Chamaremos a função de compose.
A função compose recebe duas funções como argumento e resulta em uma terceira função que é a compo-sição das duas funções dadas.
Observe que a função compose é uma função de ordem superior, pois recebe duas funções como argumentoe resulta em outra função.
Exemplos de composição de funções
12-1
compose sqrt abs_float a função composta de sqrt e abs_float
(compose sqrt abs_float) 9. 3.
(compose sqrt abs_float) (16. -. 25.) 3.
(compose sqrt (compose abs_float sin)) (3. *. 3.1415 /. 2.) 0.999999995171113154
(compose not (function [] -> true | _ -> false)) [10; 20; 30] true
(compose sqrt (compose abs_float snd)) (’Z’, -36.0) 6.
Definição de compose
let compose f g =fun x -> f (g x)
O tipo de compose é:
(’a -> ’b) -> (’c -> ’a) -> ’c -> ’b
12.3 A função List.filter
A função List.filter da biblioteca padrão recebe uma função e uma lista como argumentos, e seleciona(filtra) os elementos da lista para os quais a função dada resulta verdadeiro.
Note que filter é uma função de ordem superior, pois recebe outra função como argumento.
Exemplos de aplicação de filter
List.filter (fun x -> x mod 2 = 0) [1; 8; 10; 48; 5; -3] [8; 10; 48]
List.filter (fun x -> x mod 2 <> 0) [1; 8; 10; 48; 5; -3] [1; 5; -3]
List.filter (function ’0’ .. ’9’ -> true | _ -> false) [’A’; ’1’; ’8’; ’6’; ’B’; ’7’; ’0’] [’1’; ’8’; ’6’; ’7’; ’0’]
List.filter (compose not (fun s -> String.length s = 0)) ["abc"; ""; "ok"; ""] ["abc"; "ok"]
Definição de filter
12-2
let rec filter lst =match lst with| [] -> []| h::t -> if f h then
x : filter f telsefilter f t
O tipo de filter é:
(’a -> bool) -> ’a list -> ’a list
12.4 A função map
A função List.map da biblioteca padrão recebe uma função e uma lista como argumentos, e aplica a funçãoa cada um dos elementos da lista, resultando na lista dos resultados. List.map é uma função de ordem superior,pois recebe outra função como argumento.
Exemplos de aplicação de map
List.map sqrt [0.0; 1.0; 4.0; 9.0] [0.0; 1.0; 2.0; 3.0]
List.map succ [1; 8; 6; 10; -49] [2; 9; 7; 11; -48]
List.map (fun n -> n mod 2 = 0) [8; 10; -3; 48; 5] [true; true; false; true; false]
List.map (fun x -> x >= ’0’ && x <= ’9’) [’A’; ’1’; ’8’; ’ ’; ’B’; ’7’] [false; true; true; false; false; true]
List.map String.length ["ciênca"; "da"; "computação"] [7; 2; 12]
List.map (compose sqrt (compose abs_float snd)) [(’A’, 100.0); (’Z’, -36.0)] [10.; 6.]
Definição de map
let rec map f lst =match lst with| [] -> []| h::t -> f h :: map f t
O tipo de map é:
(’a -> ’b) -> ’a list -> ’b list
12.5 fold_left
List.fold_left reduz uma lista, usando uma função binária e um valor inicial, de forma associativa àesquerda.
12-3
fold_left (⊕) e [x0,x1,...,xn−1]≡
(...((e ⊕ x0) ⊕ x1) ...) ⊕ xn−1
Exemplos de aplicação de List.fold_left
List.fold_left (+) 0 [] 0List.fold_left (+) 0 [1] 1List.fold_left (+) 0 [1; 2] 3List.fold_left (+) 0 [1; 2; 4] 7List.fold_left ( * ) 1 [5; 2; 4; 10] 400List.fold_left (&&) true [2>0; 6 mod 2 = 0; 5 mod 2 <> 0] trueList.fold_left (||) false [2>3; 6 mod 2 = 0; 5 mod 2 <> 0] true
Definição
let rec fold_left f z lst =match lst with| [] -> z| h::t -> fold_left f (f z h) t
O tipo de List.fold_left é:
(’a -> ’b -> ’a) -> ’a -> ’b list -> ’a
12.6 fold_right
List.fold_right reduz uma lista, usando uma função binária e um valor inicial, de forma associativa àdireita.
fold_right (⊕) [x0,...,xn−2,xn−1] e≡
x0 ⊕ (... (xn−2 ⊕ (xn−1 ⊕ e)) ...)
Exemplos de aplicação de fold_right
List.fold_right (+) [] 0 0List.fold_right (+) [1] 0 1List.fold_right (+) [1; 2] 0 3List.fold_right (+) [1; 2; 4] 0 7List.fold_right ( * ) [5; 2; 4; 10] 1 400List.fold_right (&&) [2>0; 6 mod 2 = 0; 5 mod 2 <> 0] true trueList.fold_right (||) [2>3; 6 mod 2 = 0; 5 mod 2 <> 0] false true
Definição
let rec fold_right f lst z =match lst with| [] -> z| h::t -> f h (fold_right f t z)
O tipo de List.fold_right é:
12-4
(’a -> ’b -> ’b) -> ’a list -> ’b -> ’b
12.7 Cupom fiscal do supermercado
Nas tarefas que se seguem temos por objetivo desenvolver uma aplicação em OCaml para automatizar ocaixa de um supermercado usando técnicas de manipulação de listas empregando funções de ordem superior.
Um leitor de código de barras é usado no caixa de um supermercado para produzir uma lista de códigos debarras a partir dos produtos que se encontram em um carrinho de compras contendo os produtos comprados.Usando os códigos de barra cria-se uma nota descritiva da compra. Considere por exemplo a seguinte lista decódigos de barra:
[1234; 4719; 3814; 1112; 1113; 1234]
Esta lista deve ser convertida para uma conta como mostra a figura a seguir:
OCaml Stores
Dry Sherry, 1lt...........5.40Fish Fingers..............1.21Orange Jelly..............0.56Hula Hoops (Giant)........1.36Unknown Item..............0.00Dry Sherry, 1lt...........5.40
Total....................13.90
Primeiro devemos decidir como modelar os objetos envolvidos. Códigos de barra e preços (em centavos)podem ser representados por números inteiros, e nomes de mercadorias podem ser representados por strings.Então usaremos os seguintes tipos:
type nome = stringtype preco = inttype codigo = int
A conversão dos códigos de barras será baseada em um banco de dados que relaciona códigos de barras,nomes de mercadorias, e preços. Usaremos uma lista para representar o banco de dados de mercadorias:
type mercadorias = (codigo * nome * preco) list
O banco de dados para o exemplo dado é:
let tabelaMercadorias :: mercadorias =[ (4719, "Fish Fingers", 121 ); (5643, "Nappies", 1010); (3814, "Orange Jelly", 56 ); (1111, "Hula Hoops", 21 ); (1112, "Hula Hoops (Giant)", 133 ); (1234, "Dry Sherry, 1lt", 540 )]
O objetivo do programa é primeiramente converter uma lista de códigos de barra em uma lista de pares dotipo nome * preco por meio de uma consulta à tabela de mercadorias. Em seguida esta lista de pares deve serconvertida em uma string para exibição na tela. Usaremos as seguintes definições de tipo:
type carrinho = codigo listtype conta = (nome * preco) list
para representar um carrinho de compras e uma conta (cupom fiscal) corresponde a uma compra.
12-5
Tarefa 12.1: Formatação do preço em reais
Defina uma função formata_centavos : preco -> string que recebe o preço em centavos e resultaem uma string representando o preço em reais.
Por exemplo:
formata_centavos 1023 "10.23"formata_centavos 56015 "560.15"formata_centavos 780 "7.80"formata_centavos 309 "3.09"formata_centavos 15 "0.15"formata_centavos 5 "0.05"
Use as funções (/), mod e string_of_int. Observe que ao dividir o preço em centavos por 100,o quociente corresponde à parte inteira do preço em reais, e o resto corresponde à parte fracionária dopreço em reais. Preste atenção no caso do resto menor do que 10: deve-se inserir um 0 à esquerdaexplicitamente.
Tarefa 12.2: Formatação de uma linha do cupom fiscal
Defina uma função formata_linha :: nome * preco -> string que recebe um par formado pelonome e preço de uma mercadoria e resulta em uma string representando uma linha da conta do supermer-cado.
Por exemplo:
formata_linha ("Dry Sherry, 1lt", 540) "Dry Sherry, 1lt...........5.40\n"formata_linha ("Nappies, 1lt", 1010) "Nappies..................10.10\n"
O tamanho de uma linha em uma conta deve ser 30. Use a variável abaixo para representar este valor.
let tamanhoLinha : int = 30
Use as funções (^), string_of_int, String.length e String.make da biblioteca padrão, e afunção formata_centavos da tarefa 12.1.
A função String.make : int -> char -> string recebe um número inteiro n e um caracter ce resulta em uma string de comprimento n onde todos os elementos são c. Por exemplo:
String.make 5 ’A’ "AAAAA"String.make 8 ’.’ "........"
12-6
Tarefa 12.3: Formatação de várias linhas do cupom fiscal
Defina a função formata_linhas : (nome * preco) list -> string que recebe uma lista de pa-res formados pelos nomes das mercadorias e seus respectivos preços em uma compra, e resulta na stringcorrespondente ao corpo da conta do supermercado.
Por exemplo:
formata_linhas [ ("Dry Sherry, 1lt", 540); ("Fish Fingers", 121); ("Orange Jelly", 056); ("Hula Hoops (Giant)", 136); ("Unknown Item", 000); ("Dry Sherry, 1lt", 540)]
"Dry Sherry, 1lt...........5.40Fish Fingers..............1.21Orange Jelly..............0.56Hula Hoops (Giant)........1.36Unknown Item..............0.00Dry Sherry, 1lt...........5.40"
Use a função formata_linha da tarefa 12.3 para obter as linhas correspondentes a cada produto, econcatene estas linhas usando a função (^) da biblioteca padrão. Não use recursividade explícita, masuse as funções List.map e List.fold_right ou List.fold_left da biblioteca padrão.
Tarefa 12.4: Formatação do total
Defina a função formata_total :: preco -> string que recebe o valor total da compra, e resultaem uma string representado a parte final da conta do supermercado.
Por exemplo:
formata_total 1390 "\nTotal....................13.90"
Use as dicas da tarefa 12.2.
12-7
Tarefa 12.5: Formatação do cupom fiscal
Defina a função formata_conta : conta -> string que recebe a lista dos itens comprados e resultana string representando a conta do supermercado, já formatada.
Por exemplo:
formata_conta [ ("Dry Sherry, 1lt", 540); ("Fish Fingers", 121); ("Orange Jelly", 056); ("Hula Hoops (Giant)", 136); ("Unknown Item", 000); ("Dry Sherry, 1lt", 540)]
resulta na string que é exibida pela função print_string como
OCaml Stores
Dry Sherry, 1lt...........5.40Fish Fingers..............1.21Orange Jelly..............0.56Hula Hoops (Giant)........1.36Unknown Item..............0.00Dry Sherry, 1lt...........5.40
Total....................13.90
Use as funções definadas nas tarefas 12.3 e 12.4.
Tarefa 12.6: Cálculo do valor total da compra
Defina a função calcula_total :: conta -> preco que recebe uma conta (lista de pares formadospelo nome e preço das mercadorias de uma compra), e resulta no preço total da compra.
Por exemplo:
calcula_total [("a",540);("b",121);("c",12)] 673calcula_total [("vinho",3540);("carne",7201)] 10741calcula_total [] 0
Não use recursividade explícita, mas use as funções List.map e List.fold_left da bibliotecapadrão.
Tarefa 12.7: Pesquisa do código de um produto
Defina uma função procura_codigo :: mercadorias -> codigo -> nome * preco que recebeo banco de dados com os nomes e preços das mercadorias disponíveis no supermercado e o código debarras da mercadoria comprada, e resulta no par formado pelo nome e pelo preço da mercadoria, deacordo com o banco de dados. Se o código de barras não constar no banco de dados, o resultado deve sero par ("Unknown Item",0).
Por exemplo:
procura_codigo tabelaMercadorias 5643 ("Nappies", 1010)procura_codigo tabelaMercadorias 9999 ("Unknown Item", 0)
12-8
Tarefa 12.8: Criação da conta da compra
Defina a função cria_conta :: mercadorias -> carrinho -> conta que recebe o banco de da-dos com os nomes e preços das mercadorias disponíveis no supermercado, e a lista de códigos de barracorrespondente a uma compra, e resulta na lista dos pares do tipo nome * preco para as mercadoriascompradas.
Por exemplo:
cria_conta tabelaMercadorias [3814; 5643] [("Orange Jelly", 56); ("Nappies", 1010)]
Use uma aplicação parcial da função procura_codigo definida na tarefa 12.7 e a função List.mapda biblioteca padrão. Não use recursão explícita.
Tarefa 12.9: Criação do cupom fiscal
Defina a função faz_compra :: mercadorias -> carrinho -> string que recebe o banco de da-dos com os nomes e preços das mercadorias disponíveis no supermercado, e a lista de códigos de barracorrespondente a uma compra, e resulta na string correspondente à nota da compra.
Use a função cria_conta (definida na tarefa 12.8) para criar a conta a partir dos argumentos, e afunção formata_conta (definida na tarefa 12.5) para converter a conta para string. Use composição defunções.
Tarefa 12.10: Ação main
Defina a variável main : () como uma expressão sequência cuja avaliação produz uma interação como usuário. Quando main for avaliada, o usuário deve digitar os códigos de barras das mercadorias com-pradas e em seguida a conta correspondente do supermercado deve ser exibida na tela.
Tarefa 12.11
Compile a aplicação gerando um programa executável. Teste a aplicação.
12-9
13 Tipos Algébricos
ResumoUm tipo algébrico é um tipo onde são especificados a forma de cada um dos seus elementos.
Algébrico se refere à propriedade de que um tipo algébrico é criado por operações algébricas. Aálgebra aqui é somas e produtods:
• soma é a alternância: A|B significa A ou B, mas não ambos, e
• produto é a combinação: AB significa A e B juntos.
Somas e produtos podem ser combinados repetidamente em estruturas arbitrariamente largas.Nesta aula vamos aprender como definir e usar tipos algébricos (ou seja, estruturas de dados), em
OCaml.
Sumário13.1 Novos tipos de dados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13-1
13.2 Tipos variantes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13-2
13.3 Exemplo: formas geométricas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13-2
13.1 Novos tipos de dados
• Tipos básicos:
– unit
– bool
– char
– int
– float
• Tipos Compostos:
– string
– tuplas: t1 * t2 * ... * tn
– listas: t list
– funções: t1 -> t2
• Novos tipos: como definir?
– dias da semana
– estações do ano
– figuras geométricas
– árvores
– tipos cujos elementos são inteiros ou strings
– . . .
13-1
13.2 Tipos variantes
Tipos variantes, também conhecidos como tipos algébricos, são um dos recursos mais úteis de OCaml etambém um dos mais incomuns. Eles permitem a representação de dados que podem assumir várias formasdiferentes, onde cada forma é marcada por um rótulo (tag) explícito. Como veremos , quando combinado como casamento de padrão, as variantes constituem uma maneira poderosa de representar dados complexos e deorganizar a análise de casos destes dados.
A sintaxe básica de uma declaração de tipo de variante é a seguinte :
type tipo =| variante1...| varianten
As variantes são separadas por uma barra vertical. Opcionalmente pode-se usar uma barra vertical antes daprimeira variante.
tipo o nome do construtor de tipo- sendo definido, opcionalmente precedido de uma variável de tipo ou deuma lista de variáveis de tipo separadas por vírgula e delimitada por parênteses:
nome_tipou nome_tipo( u1, · · · , uk) nome_tipo
Nomes de construtores de tipo devem começar com letra minúscula e variáveis de tipo devem começar comapóstrofo.
variante1 é uma variante formada por um construtor de dados (também chamado de rótulo ou tag), opcio-nalmente seguido da palavra reservada of e da lista de tipos dos campos que compõem a variante, separados porasterisco:
tagtag of t1 * · · · * tm
Nomes de construtores de dados devem começar com letra maiúscula.Um construtor de dados é utilizado para
• construir valores do tipo definido, funcionando como uma função (eventualmente, constante) que recebeargumentos (do tipo indicado para o construtor), e constrói um valor do novo tipo de dados;
• decompor um valor do tipo em seus componentes, através de casamento de padrão.
Construtores de dados são semelhantes a funções, porém não tem nenhuma definição (algoritmo) associada.Apenas constroem um valor do tipo associado a partir dos seus componentes.
13.3 Exemplo: formas geométricas
• Definição de um novo tipo para representar formas geométricas:
type figura =| Circulo of float| Retangulo of float * float
• O construtor de tipo é figura.
• Os construtores de dados deste tipo são:
– Circulo, que constrói uma figura a partir de um float, e
– Retangulo, que constrói uma figura a partir de dois floats.
Com eles é possível construir todo e qualquer valor do tipo figura:
13-2
# let a = Circulo 2.3;; (* um círculo de raio 2.3 *)val a : figura = Circulo 2.3
# let b = Retangulo (2.8, 3.1);; (* um retângulo de base 2.8 e altura 3.1 *)val b : figura = Retangulo (2.8, 3.1)
# let lfig = [Retangulo (5., 3.); Circulo 5.7; Retangulo (2., 2.)];;val lfig : figura list =[Retangulo (5., 3.); Circulo 5.7; Retangulo (2., 2.)]
• Expressões como Circulo 2.3 ou Retangulo (2.8, 3.1) não podem ser reduzidas, pois já estãoem sua forma mais simples.
• Os construtores são utilizados em casamento de padrões para selecionar os componentes de um valor dotipo algébrico.
• Podemos definir funções envolvendo os tipos algébricos.
let e_redondo fig =match fig with| Circulo _ -> true| Retangulo _ -> false
e_redondo (Circulo 3.2) truee_redondo (Retangulo (2.0, 5.1)) false
let area = function| Circulo r -> let pi = acos (-1.0) in pi *. r**2.0| Retangulo (b, a) -> b *. a
area (Circulo 2.5) 19.6349540849362079area (Retangulo (2.0, 5.1)) 10.2
let quadrado lado =Retangulo (lado, lado)
area (quadrado 2.5) 6.25
13-3
