Inferência de tipos e método indutivo sobre listas. Exercícios de 13 a 15.
let f1 x = x + 1 ;; let f2 x = f1 x ;; let f3 x = 1 + x 5 ;; let f4 x y = x < y x ;; (* Procure o tipo de "<" aqui *)
Nota: Na resolução de problemas de inferência, o primeiro passo é sempre ver quantos argumentos tem a função - o tipo duma função com n argumentos tem sempre n setas no nível exterior. O segundo passo é descobrir o tipo de cada argumento com base na sua utilização do lado direito da função. O tipo do resultado pode ser descoberto no final do processo, ou misturado com a descoberta do tipo dos argumentos. Exemplos.
Para cada um dos tipos abaixo, dê também um exemplo duma função:
(int->int) -> int bool -> float -> string
Existe um curto vídeo de demonstração, mesmo no final desta página.
Durante a aula, mantenha duas janelas abertas:
O processo de criação dum projeto novo para OCaml é o seguinte:
Depois da criação do Project "LAP", nas execuções seguintes o Eclipse arranca com esse Project já aberto. Se desejar que os exercícios das diversas aulas não fiquem misturados no mesmo módulo, crie um módulo novo no início de cada aula.
Estas regras ensinam a usar apenas o interpretador. Na aula prática 4 veremos como gerar programas standalone executáteis.
Instalação do plugin para OCaml: Já está instalado nos laboratórios. Para instalar no seu computador pessoal, primeiro instala-se o sistema OCaml, que pode ser obtido na página da bibliografia (confirme numa consola se ficou a funcionar). Depois instala-se o Eclipse (pode ser, por exemplo, o Eclipse para Java). Finalmente instala-se o plugin. Na página WEB do plugin há regras de instalação fáceis de seguir - veja o item "Install". [Se instalar por uma ordem diferente, não vai funcionar. Nesse caso, desinstale o Eclipse e recomece do princípio. Esta forma de instalar foi testada apenas no Linux, mas talvez funcione igualmente bem noutros sistemas operativos.]
Questões de compatibilidade: O plugin para OCaml é um pouco antigo e parece só funcionar com determinadas versões específicas do Eclipse, por exemplo 2018-12 e 2020-03.
succAll : int list -> int listque produza a lista dos sucessores duma lista de inteiros.
Exemplos: succAll [] = [] succAll [3; 6; 1; 0; -4] = [4; 7; 2; 1; -3]
belongs: 'a -> 'a list -> bool (* teste de pertença *) (* para ser resolvido no quadro *) union: 'a list -> 'a list -> 'a list (* união de conjuntos *) inter: 'a list -> 'a list -> 'a list (* intersecção de conjuntos *) diff: 'a list -> 'a list -> 'a list (* diferença de conjuntos *) power: 'a list -> 'a list list (* conjunto potência: conjunto dos subconjuntos - difícil *)
Exemplos: belongs 4 [1;2;3;4;5;6] = true belongs 4 [1;2] = false union [7;3;9] [2;1;9] = [7;3;2;1;9] inter [7;3;9] [2;1;9] = [9] diff [7;3;9] [2;1;9] = [7;3] power [] = [[]] power [2;3] = [[]; [2]; [3]; [2;3]] power [1;2;3] = [[]; [2]; [3]; [2;3]; [1]; [1;2]; [1;3]; [1;2;3]] (* não interessa a ordem dos elementos *)
Nota: Nas funções que recebem duas listas pode surgir a dúvida: faz-se a redução a problemas mais simples no primeiro ou no segundo argumento da função? Geralmente tenta fazer-se a redução usando o primeiro argumento e chega-se a uma solução satisfatória. Apenas em casos raros é necessário fazer a redução no segundo argumento, ou até nos dois argumentos ao mesmo tempo.
nat : int -> int listque, dado um inteiro n, gere a lista dos n primeiros números naturais, ordenada decrescentemente.
Exemplos: nat 0 = [] nat 1 = [0] nat 2 = [1;0] nat 5 = [4;3;2;1;0]
Nota: Este exercício tem a ver com listas, mas repare que o que determina a estrutura duma função são os seus argumentos. Como o argumento desta função é um inteiro, é provável que esta função tenha uma estrutura parecida com a da função fatorial, do exercício 6.
Mas a temperatura ambiente varia lentamente. Assim é de esperar que uma lista de temperaturas contenha muitos valores repetidos consecutivos. Analisemos a parte inicial duma tal lista:
[10.1; 10.1; 10.1; 10.1; 10.1; 10.1; 10.1; 10.1; 10.1; 10.1; 10.1; 10.1; 10.1; 10.1; 10.1; 10.1; 10.1; 10.1; 10.1; 10.1; 10.1; 10.1; 10.1; 10.1; 10.1; 10.1; 10.0; 10.0; 10.0; 10.0; 10.0; ...]Esta lista indica que à meia-noite a temperatura era de 10.1 graus centígrados. Depois, a temperatura não sofreu alteração sensível durante mais 24 segundos, mas ao 26º segundo baixou para os 10.0 graus centígrados [Excitante, não é?!].
O que nos interessa aqui é a questão do armazenamento destas listas de temperaturas no computador. A verdade é que não vale a pena guardar listas tão longas. É preferível guardá-las numa forma compactada para aproveitar melhor a memória.
pack : 'a list -> ('a * int) listpara compactar listas, substituindo cada subsequência de valores repetidos por um par ordenado que indica qual o valor que se repete e qual o comprimento da subsequência. Dois exemplos:
pack [] = [] pack [10.1; 10.1; 10.1; 10.1; 10.1; 10.1; 10.1; 10.0; 10.0; 10.1; 10.0] = [(10.1, 7); (10.0, 2); (10.1, 1); (10.0,1)]
unpack : ('a * int) list -> 'a listDois exemplos:
unpack [] = [] unpack [(10.1, 7); (10.0, 2); (10.1, 1); (10.0,1)] = [10.1; 10.1; 10.1; 10.1; 10.1; 10.1; 10.1; 10.0; 10.0; 10.1; 10.0]
combinations : 'a list -> int -> 'a list list
Exemplos: combinations [1;2;3;4;5] 0 = [[]] combinations [1;2;3;4;5] 1 = [[1]; [2]; [3]; [4]; [5]] combinations [1;2;3;4;5] 3 = [[1; 2; 3]; [1; 2; 4]; [1; 2; 5]; [1; 3; 4]; [1; 3; 5]; [1; 4; 5]; [2; 3; 4]; [2; 3; 5]; [2; 4; 5]; [3; 4; 5]] combinations [1;2;3;4;5] 5 = [[1; 2; 3; 4; 5]]
('a -> 'b) -> ('c -> 'a) -> 'c -> 'b