Linguagens e Ambientes de Programação (2017/2018)



Teórica 03 (13/mar/2018)

O método indutivo (redução de problemas a problemas mais simples).
Muitas funções sobre listas programadas usando o método indutivo.
Nomes locais. Funções mutuamente recursivas.



Método indutivo

Revisitando a a recursividade

A programação de funções recursivas não é novidade pois já foi abordada em cadeiras anteriores, por exemplo POO e AED. Contudo, o estudo duma linguagem funcional é uma excelente oportunidade para revisitar o tema, com os seguintes objetivos: aprofundar a análise do mecanismo; estudar diversos padrões de utilização; passar a encarar a recursividade como uma técnica que ajuda a descobrir soluções para certos problemas complicados.

Numa linguagem funcional, a recursividade está na base da programação de todas as atividades repetitivas, já que não existe o mecanismo da iteração, típico das linguagens de base imperativa.

Além disso, nós queremos usar a recursividade duma forma que enfatize as propriedades lógicas do problema a resolver em vez de questões operacionais. O objetivo é programar a mais alto nível, a um nível mais humano, evitando ter de pensar como uma máquina.

Redução de problemas a problemas mais simples

Considere as seguintes duas funções recursivas, escritas em OCaml: Analisando estas duas funções recursivas verificamos que quando lidam com o caso não-trivial - o chamado caso geral - ambas efetuam a redução do problema original a uma instância mais simples do mesmo problema. Concretamente, a função len reduz o problema len (x::xs) ao problema mais simples len xs, e a função fact reduz o problema fact n ao problema mais simples fact (n-1).

Além de efetuarem redução de problemas no caso geral, as duas funções lidam também, separadamente, com o caso trivial de cada problema - o chamado caso base. Concretamente, a função len trata separadamente o caso base len [] e a função fact trata separadamente o caso base fact 0.

Repare que quando uma destas duas funções é aplicada a um argumento, inicia-se uma sucessão de reduções a problemas mais simples que só termina quando o caso base é alcançado. Por exemplo, a sequência de reduções produzida pela aplicação len [7;6;5;4] é a seguinte:

As funções recursivas len e fact são representativas do que é programar usando o núcleo funcional do OCaml. Em OCaml programa-se essencialmente reduzindo problemas a problemas mais simples.


Técnica do método indutivo

O método indutivo (também conhecido como técnica da divisão e conquista) serve para ajudar a programar funções recursivas que efetuam reduções de problemas a problemas mais simples.

O método indutivo consiste na seguinte técnica:

Exemplo de utilização do método indutivo

Problema: Programar uma função len que determine o comprimento de listas.

Resolução: Para começar, a função len recebe uma lista, a qual terá de ser processada usando emparelhamento de padrões. Aplicando o método indutivo ao caso geral G=len (x::xs), vamos começar por assumir que já temos o problema resolvido para o caso mais simples S=len xs.

Desde já podemos ir escrevendo a seguinte estrutura incompleta:

O problema que temos para resolver é o seguinte: Como é que se obtém o valor de G=len (x::xs) a partir do valor de S=len xs? Mas este problema é simples! De facto, basta adicionar uma unidade a S para se obter G!

Preenchendo o que falta no esquema anterior, surge a solução final:

NOTA1: Neste exemplo, reduzimos o problema G=len (x::xs) ao problema S=len xs. Mas esta não é a única redução possível... Existem muitas outras... Voltaremos a este assunto noutra aula.

NOTA2: A função len é tão simples que faz o método indutivo parecer óbvio e desinteressante. No entanto, este método de resolver problemas tem imensas virtualidades:


Mais funções sobre listas programadas usando o método indutivo

Estude-as todas de forma muito atenta. Depois tente programá-las todas "sem espreitar".

Comprimento de lista:

Soma dos elementos de lista: Concatenação de listas: Acrescentar elemento no final de lista: Inversão de lista: Máximo duma lista (tratamento implícito do erro): Máximo duma lista (tratamento explícito do erro): Aplicação de função a todos os elementos de lista: Seleção dos elementos duma lista que verificam uma dada propriedade: Concatenação de todas as listas contidas numa lista de listas: Concatenação de todos os resultados gerados por uma função de mapping que produz listas: Ordenação de listas: Fusão de listas ordenadas sem repetições (aqui dá jeito usar matching duplo):

Exemplos de avaliações


A função @

A função append está predefinida em OCaml, sendo denotada pelo operador binário @. Assim, podemos escrever: No entanto, a função @ é pouco eficiente e deve ser usada com critério. Por exemplo, para acrescentar um zero à cabeça duma lista list é má ideia escrever [0]@list; escreve-se sempre 0::list. No entanto, para acrescentar um zero ao final duma lista list não temos alternativa e escreve-se mesmo list@[0].



Nomes locais

Agora, um novo assunto...

Construção let-in

A construção let-in:
    let n = exp in
        exp1
associa o nome n ao valor da expressão exp no contexto da expressão exp1. O nome n passa a definir uma constante local à expressão exp1.

O nome n também pode ser parametrizado, passando a denotar uma função local, assim

    let n x = exp in
        exp1
Esta forma é equivalente a
    let n = (fun x -> exp) in
        exp1

A palavra reservada and pode ser usada para definir simultaneamente vários nomes no mesmo let-in. Por exemplo:

ou Exercício: Procure no manual da linguagem a forma sintática geral da construção let-in.

Vamos ver de seguida que a construção let-in permite:

  1. Aumentar a legibilidade de certas funções;
  2. Aumentar a eficiência de certas funções;
  3. Definir funções mutuamente recursivas.

1. Legibilidade

Considere o seguinte problema: Escreva em OCaml uma função chamada parque que calcule o preço a pagar no parque de estacionamento subterrâneo dos Restauradores, em Lisboa. A função parque recebe 2 pares ordenados de inteiros como argumentos: hora e minuto de entrada, hora e minuto de saída. Os tempos de permanência são arredondados para horas completas e sempre para cima. Assuma que o carro nunca está no parque mais do que 24:00. Em Março de 1999, a tabela de preços era a seguinte: Apresentam-se a seguir duas versões equivalentes da função parque, a segunda programada usando let-in. A escolha entre elas é, em grande medida, uma questão de gosto, mas pode argumentar-se que a segunda versão, apesar de mais longa, é mais fácil de perceber porque torna explícita a ordem de avaliação das sub-expressões dentro duma expressão que é demasiado grande e complexa. Exercício: As funções auxiliares não foram ainda programadas. Tente escrevê-las.

2. Eficiência

A construção let-in também pode ser usada para aumentar a eficiência de certas funções. Por exemplo a segunda função é mais eficiente do que a primeira (porquê?):

3. Funções mutuamente recursivas

A forma geral da construção let-in inclui a possibilidade de utilização simultânea de rec e and. Isso permite definir 2 ou mais funções mutuamente recursivas. Eis um exemplo curioso com duas funções: O que fazem estas funções?

Tradução do let-in

A construção let-in é internamente traduzida para a seguinte representação: As duas formas são equivalentes (medite um pouco nisso!), mas a primeira é mais fácil de perceber.

Tradução do let simples

A já nossa conhecida construção let-simples, que permite definir nomes globais, é internamente traduzida para a construção let-in - os nomes globais são habilidosamente traduzidos para nomes locais.

Por exemplo, a seguinte sequência de definições e expressões:

é internamente traduzida para um conjunto de let aninhados:

#120