Em cursos de algoritmos é comum trabalharmos com dois tipos de dados recursivo, listas e árvores. Tipos de dados recursivos são aqueles que são definidos em termos de si mesmo. Entretanto, o tipo de dados recursivo mais comum não é nenhum destes dois, e sim os números naturais. Os números naturais são descritos por Giuseppe Peano, é um autor italiano, cujo nome é lembrado até hoje em conexão com os axiomas por ele introduzidos, dos quais dependem tantas construções rigorosas da álgebra e da análise. Segue seus axiomas (Obs: a Definição original parte do UM)
- Zero é um número.
- Se a é um número, o sucessor de a é um número.
- Zero não é o sucessor de um número.
- Dois números cujos sucessores são iguais são eles próprios iguais.
- Se um conjunto S de números contém o zero e também o sucessor de todo número de S, então todo número está em S.
É possível encontra a definição destes axiomas em linguagens funcionais, como Haskell. Neste post eu demonstro a implementação usando uma linguagem imperativa, no caso C. Nesta linguagem, tipos recursivos são implementados a partir de ponteiros.
Por exemplo, a seguinte definição em Haskell:
data Nat = Zero | Succ NatPode ser mapeado para C:
typedef struct Nat { struct Nat* succ; }* Nat;
Nat Zero () {
return NULL;
}
Nat Succ (Nat a) {
Nat n = malloc (sizeof (Nat));
n->succ = a;
return n;
}Operação de soma em Haskell:
soma Zero n = n
soma (Succ m) n = Succ (soma m n)Operação de soma em C:
Nat sum (Nat a, Nat b) {
if (a == Zero () )
return b;
else
return Succ ( sum (a->succ,b) );
}Operação de multiplicação em Haskell
mult Zero m = Zero
mult (Succ m) n = soma n (mult n m)Operação de multiplicação em C
Nat mult (Nat a, Nat b) {
if (a == Zero () )
return Zero ();
else
return sum (b, (mult (b, a->succ)));
}No exemplo acima destaco um dos recursos mais importantes do Haskell. Casamento de padrões. Este recurso permite construir e “deconstruir” (não é destruir) um objeto a partir do seu construtor. Mais sobre Haskell:http://www.haskell.org/
Advertisement
