Haskell aula 06

Prévia do material em texto

*
Haskell aula 06
Indução matemática
Prof. Msc Aurélio Andrade de Menezes Júnior.
*
Uma visão funcional da indução
A indução matemática é uma definição generalizada para um conjunto de objetos que tenham em comum uma propriedade.
Para se demonstrar que este conjunto exibe tal propriedade, deve-se conhecer o caso trivial.
Tal caso corresponde normalmente a n=0, n=1 e etc, que são os valores base ou triviais.
O passo seguinte é demonstrar que para um n genérico, a propriedade indutiva mantém-se a partir de n-1.
*
Uma visão funcional da indução
Assim o termo n dessa propriedade indutiva á validade, considerando que o caso anterior n-1, também era verdadeiro.
O conceito dessa idéia indutiva é a base de toda a programação em Haskell, mas, esses passos matemáticos, são deixados a cargo do computador.
Para tais cálculos, uma escadaria de um caso n que se deseja demonstrar é construída, do fim para o início, até o caso trivial ou conhecido dessa regra recursiva.
*
Recursão
O clássico exemplo da recursão, por meio de uma idéia indutiva,é a soma dos n primeiros inteiros.
Isto é somar 1+2+3+4+...+(n-1) + n, representado por soma(n).
Exemplificando: soma(5)=1+2+3+4+5=15.
*
Recursão
Assim para resolver o problema da soma de 1 até n é utilizado o seguinte raciocínio:
 1 + 2 + 3 + 4 +...+n
Soma 1 = 1
Soma 2 = (soma 1) + 2
Soma 3 = (soma 2) + 3
Soma 4 = (soma 3) + 4
 .
 .
Soma n = (soma (n-1)) + n
*
Recursão
Sob uma definição matemática desta soma de inteiros entre 1 e n, é dada por:
 1 : n=1
 soma(n) = soma(n-1)+n : n>1
Como se observa há uma soma repetitiva entre o último número com a soma acumulada até o número sucessor.
Tendo o problema generalizado, basta descrever o aterramento, ou seja, a última ação da função soma, que no caso é a soma 1.
*
Recursão
O código fica dascrito como:
soma 1 = 1
soma n = soma (n-1) + n
A execução deste programa é dada por:
Main> soma 4
10
*
Recursão
Mas como o interpretador Haskell executa tal código?
Resposta: Deve-se fazer a escadaria recursiva que representa as sucessivas chamadas recursivas que a linguagem Haskell faz:
soma 4 =(((1) + 2) + 3) + 4
=(soma 3) + 4 =((3) + 3) + 4
=((soma 2) + 3) + 4 = (6) + 4
=(((soma 1) + 2) + 3) + 4 = 10
*
Dúvidas