Definição indutiva de Listas

Conhecer a definição indutiva de uma estrutura de dados, facilita a implementação dos algoritmos que à manipulam. Uma lista pode ser definida como sendo

• uma lista vazia (caso base).
• ou uma lista L do tipo <T>, concatenada com um elemento a do mesmo tipo.

Podemos perceber a indução facilmente quando analisamos a concatenação L::a, que segundo a definição, nos diz que se L for uma lista, então L::a também será.

Agora vamos usar a mesma idéia para construir alguns programas que manipulam listas em Haskell.

• Soma dos elementos de uma lista

somaList :: [Int] -> Int
somaList [] = 0
somaList (x:xs) = x + somaList xs  -- Hipótese de indução: somaList xs

• Inversão de uma lista

reverse :: [Int] -> [Int]
reverse [] = []
reverse (x:xs) = reverse xs ++ [x]   -- Hipótese de indução: reverse xs

• Seleção do menor valor em uma lista

menor :: [Int] -> Int
menor [x] = x
menor (x:xs)
    | x <= (menor xs) = x
    | otherwise = (menor xs)   -- Hipótese de indução: menor xs

• Tamanho de uma lista

length :: [Int] -> Int
length [] = 0
length (x:xs) = 1 + length xs  -- Hipótese de indução: length xs

Nas implementações acima, podemos perceber que a utilização da hipótese de indução facilitou a construção dos algoritmos, pois nós assumimos que o problema já estava resolvido para listas com n - 1 elementos e simplesmente estendemos a solução para uma lista com n elementos.

É importante lembrar que a indução é uma ferramenta que facilita a construção dos algoritmos e não depende da linguagem ou do paradigma de programação específico que será utilizado. A implementação a seguir foi alcançada através da indução e foi escrita na linguagem C.

• Tamanho de uma string

int length(char *s)
{
 if(!*s)
      return 0;  
   else
      return 1 + length(++a); // Hipótese de indução: length(++a)
}