Particionando dados: implementação em Haskell

Em uma postagem anterior, que pode ser vista aqui, abordamos indutivamente a construção de um algoritmo que realiza a separação de dados em um vetor. Agora apresentamos uma implementação em Haskell para solucionar o mesmo problema. 

Por se tratar de uma linguagem funcional, Haskell possibilita uma implementação clara e enxuta na maioria dos casos.

Vamos a descrição indutiva do problema:

• Caso Base: Uma lista vazia está particionada em pares e ímpares por definição.
• Hipótese de Indução: Vamos assumir que uma lista com n-1 elementos já está particionada em pares e ímpares.
• Caso Geral: Basta verificar a paridade do elemento que ficou de fora, se ele for par então basta colocá-lo no início da lista com n-1 elementos obtida por hipótese de indução, caso contrário ele será colocado no final da lista obtida por hipótese de indução.

E mais uma vez derivaremos o algoritmo a partir da descrição indutiva. A boa notícia é que o algoritmo decorre imediatamente da descrição indutiva e podemos chegar até ele sem esforço. A seguir apresentamos a solução para a descrição indutiva implementada em Haskell.

• Implementação em Haskell

partition :: [Int] -> [Int]
partition [] = []
partition (x:xs)
  | x `mod` 2 == 0 = x : (partition xs)
  | otherwise      = (partition xs) ++ [x]

Complexidade do algoritmo:

Apesar de simples, a implementação apresentada em Haskell não é eficiente. Em nosso editorial, discutiremos uma implementação mais eficiente também em Haskell.

@inductioncode