Marcelo Parrela

2013-11-05

TENHO UM NOVO BLOG

ATENÇÃO:

Este blog será descontinuado em detrimento de marceloparrela.wordpress.com

Assim, por favor, acessem marceloparrela.wordpress.com para continuarem a ler meus artigos.

Grato pela compreensão,
Marcelo Parrela

2013-10-29

Transformações de Dados - em Haskell

by Marcelo Parrela - marcelo.parrela@gmail.com

Ideia Inicial

Deparei-me com uma ideia interessante: representar os elementos químicos, da tabela periódica, em Haskell. Pensei em fazer uma aplicação que carregue os dados de um arquivo CSV (com campos separados por ';'), que converta os dados para uma estrutura de dados do tipo tupla e, finalmente, que processe os dados dessas tuplas.
Não me prenderei aos tipos de processamentos que serão possíveis - até mesmo porque não tenho isso claro, em mente, ainda. Mas, gostaria de falar sobre a carga do arquivo e de como serão feitas as transformações dos dados.
Linguagens funcionais trabalham a transformação de dados de uma maneira muito direta; chega a ser impressionante a facilidade de se lidar com esse tipo de problema - usando Haskell (também, Lisp). Nota: Não conheço outras linguagens funcionais, mas, acredito que em Scala e em Clojure teremos resultados muito interessantes também.

Estrutura de Dados

Consegui informações básicas sobre todos os elementos da tabela periódica - em sites, na Intenet. São elas: sigla, nome, número atômico, massa atômica, número do grupo e número do período. Reuní tudo e montei um arquivo CSV, com os campos sendo separados por ';'. Veja o modelo abaixo:

Dado:
    sigla;nome;número atômico;massa atômica;grupo;período

Onde:
    Sigla e Nome são do tipo String; 
    Número atômico, Grupo e Período são do tipo Int; 
    Massa atômica é do tipo Double.

Decidi utilizar apenas uma tupla para representar um elemento químico. Os dados do arquivo CSV serão mapeados para uma lista cujos elementos são desse tipo de tupla. É importante salientar que existem outras formas de representar dados em Haskell.
Nota: Para quem não está acostumado com programação funcional, tupla é uma estrutura de dados muito simples, assemelhando-se ao record do Pascal ou à struct de C.
Essa tupla possuirá a seguinte estrutura:

( String, String, Int, Double, Int, Int )

O Processamento

Observações:

Caro leitor, procurei descrever a carga e o processamento do CSV de forma didática - para que as pessoas que não possuem familiaridade com a Linguagem Haskell consigam compreender a solução proposta.
Não me preocupei com tratamento de exceção. O processamento é feito levando-se em consideração que tudo irá bem.
Você poderá baixar os códigos e o CSV na sessão Downloads, ao final do artigo.

Primeiramente, a leitura do arquivo será feita pela função readFile - que executa uma leitura não bufferizada do arquivo. Esta função retorna o conteúdo do arquivo carregado em uma única String. Exemplo:

# rodando em shell - criando o arquivo de exemplo
echo "Ac;Actínio;89;227;3;7" > linhas.txt
echo "Ag;Prata;47;107.8682;11;5" >> linhas.txt
echo "Al;Alumínio;13;26.9815386;13;3" >> linhas.txt

-- em Haskell - lendo o arquivo de exemplo
a <- readFile "linhas.txt"
print a
"Ac;Actínio;89;227;3;7\nAg;Prata;47;107.8682;11;5\nAl;Alumínio;13;26.9815386;13;3\n"

Nesse ponto, nota-se que os dados estão separados pelo caractere de quebra de linha '\n'. Para separar os dados, utilizaremos função lines que quebra uma String em uma lista de Strings usando o caractere de quebra de linha como delimitador. Veja o exemplo:

a <- readFile "linhas.txt"
let linhas = lines a
print linhas 
["Ac;Actínio;89;227;3;7","Ag;Prata;47;107.8682;11;5","Al;Alumínio;13;26.9815386;13;3"]

Agora, iteramos cada elemento da lista usando a função map e aplicamos - a cada elemento - uma função de transformação. Esta função, por sua vez, separará os campos do CSV e os aplicará à tupla.

A função map recebe - como parâmetro - uma lista e uma função transformadora que processará os elementos dessa lista. Daí, ela itera os elementos da lista e executa a função para cada um deles. O resultado final é uma lista que resultou do processamento da original. Exemplo:

-- A função 'odd' recebe um número e retorna True se for ímpar e False se for par.
let lista = map (odd) [1,2,3,4,5,6,7,8,9,10] 
print lista
[True,False,True,False,True,False,True,False,True,False]

Observação: Note que a função map é usada exclusivamente para transformar uma lista. E, no exemplo acima, foi usada para transformar uma lista de números inteiros em uma outra lista de valores booleanos - resultantes da aplicação da função odd.

Retornando ao problema proposto neste artigo: para cada elemento da lista de Strings, devemos separar os campos (delimitados por ';') e convertê-los para a nova estrutura. Porém, não conheço, em Haskell, uma função que faça o split pelo caractere ';'. Ou seja, que seja parametrizável. E, sinto muita vergonha em ter que reconhecer isso! Eu já pesquisei em várias fontes, porém, não encontrei a tal função.
Curiosamente, em Haskell, existem diversas funções que executam algum tipo de split. Tais como lines, que já foi cidada. Outra função é a words - que recebe uma String e retorna uma lista cujos elementos são as palavras da String original (obs.: esta função não é adequada ao nosso problema). Mas, uma bendita função split que seja parametrizável, eu ainda não achei não! :-(
Foi exatamente por esse motivo que tive de escrever minha própria função split. Veja o código abaixo:

-- by Marcelo Parrela - marcelo.parrela@gmail.com
split :: (Eq a) => a -> [a] -> [[a]]
split _ [] = []
split c as = w : split c r
    where 
        (w,r) = split' c as []

        split' _ [] l1 = (l1,[])
        split' c (a:as) l1
            | a /= c = split' c as (l1++[a])
            | otherwise = (l1,as)

Com a função split, poderemos testar a separação dos campos CSV. Exemplo:

split ';' "Ac;Actínio;89;227;3;7"
["Ac","Actínio","89","227","3","7"]

Veja o resultado da função split em conjunto com a função map:

map (split ';') [ "Ac;Actínio;89;227;3;7" , "Ag;Prata;47;107.8682;11;5" , "Al;Alumínio;13;26.9815386;13;3" ]
[ ["Ac","Actínio","89","227","3","7"], ["Ag","Prata","47","107.8682","11","5"], ["Al","Aluminio","13","26.9815386","13","3"] ]

Bem, já possuímos os dados dos elementos químicos em um formato muito mais amigável para se trabalhar. Basta-nos, agora, aplicar uma segunda função de transformação para converter os elementos em tuplas.

let lista = [ ["Ac","Actínio","89","227","3","7"], ["Ag","Prata","47","107.8682","11","5"], ["Al","Aluminio","13","26.9815386","13","3"] ]
    
let toTupla = (\[si,no,nu,ma,gr,pe] -> (si, no, read nu :: Int, read ma :: Double, read gr :: Int, read pe :: Int) )
    
let listaFinal = map toTupla lista 
print listaFinal
[ ("Ac","Actínio",89,227.0,3,7) , ("Ag","Prata",47,107.8682,11,5) , ("Al","Aluminio",13,26.9815386,13,3) ]

Para deixar mais claro, o código, informo que a função read converte um valor de String para outro tipo de dado. E, a aplicação do cast usando :: Int e ::Double apenas especifica o tipo de dado de destino dessa conversão.
A partir daqui, possuímos os dados em formatos de fácil processamento e poderemos elaborar cálculos diversos.

Montando o Quebra-Cabeças

Agora, vamos ver como fica tudo junto:

toTupla [si,no,nu,ma,gr,pe] = (si, no, read nu ::Int, read ma ::Double, read gr ::Int, read pe ::Int)

main = do
    dados <- readFile "./elementos-quimicos.csv"

    let elementos = map toTupla $ map (split ';') $ lines dados
    
    print elementos
    ...

Acredito que é possível notar a simplicidade e a clareza de código. Ficou um código limpo, pequeno e de fácil manutenção.

Downloads

2013-10-11

Haskell - A História!

1930 – O Cálculo Lambda (λ-Calculus)

As teorias e fundamentos matemáticos por trás da Programação Funcional tiveram início na década de 1930 com o Cálculo Lambda – criado por Alonzo Church.

É considerado a primeira linguagem programação funcional – porém, não foi projetada para ser executada em computadores, sendo apenas um modelo matemático que descreve relações entre funções.

O Cálculo Lambda é tão importante que algumas linguagens imperativas o estão incorporando. É o caso da versão 8 da linguagem Java.

Alonzo Church consegui criar um modelo que permitia construir funções mais complexas através de relações entre funções mais simples.

1956 – As Primeiras Linguagens Funcionais

Lisp foi a primeira linguagem de programação funcional; foi criada em 1956 por John McCarthy, logo após a criação do FORTRAN. Isso faz de Lisp a segunda linguagem de programação do mundo.

Muitas outras linguagens funcionais foram criadas desde então – várias delas foram derivadas de Lisp (os também chamados dialetos do Lisp). Entre as quais cito Scheme (do MIT) e Clojure (que roda na JVM).

Em 1996, Lisp foi padronizada e passou a chamar-se Common Lisp.

Infelizmente, Lisp nunca foi uma linguagem puramente funcional, pois agregava componentes de linguagens imperativas (mudanças de estado, efeitos colaterais, comandos de controle, etc.).

1978 – A Grande Crítica!

Em 1978, John Backus (pai do FORTRAN, do BFN, etc.) publicou o artigo “Can Programming Be Liberated from the vonNeumann Style?” (A programação pode ser livre do estilo von Neumann?) no Turing Award. Este artigo atacava severamente a arquitetura de hardware baseada no modelo de von Neumann e seus efeitos negativos sobre as linguagens de programação que seguiam esse estilo. Ou seja, ele criticou o hardware atual e as linguagens de programação do Paradigma Imperativo.

Ele demostrou que as novas gerações de linguagens herdavam falhas de projeto das linguagens antigas e adicionavam novas falhas; estas, por sua vez, seriam herdadas pelas próximas gerações. Assim, essas linguagens apenas cresciam de tamanho (ou, engordavam), porém, não aumentavam seu poder.

Backus afirmava que as pesquisas envolvendo novas linguagens de programação não focavam novas ideias, mas sim, a criação de linguagens acomodadas a um modelo já existente.

Porém, Backus exaltou a Programação Funcional! Neste artigo, apresentou a Programação Funcional como uma prática ferramenta de programação, deixando claro que não se tratava de uma curiosidade matemática – que é um estigma até os dias de hoje.

1980 – Acensão da Programação Funcional

Já na metade da década de 1980, a comunidade de Programação Funcional estava em plena movimentação – entre pesquisas, reuniões e conferências.

Várias técnicas enovadoras foram propostas, como por exemplo: avaliação preguiçosa (lazy evaluation).

Em meio a tantas ideias e teorias, diversos cientistas individualmente propuseram e implementaram suas próprias soluções computacionais; o que gerou uma avalanche de linguagens de programação e de documentação científica. Somente para exemplificar, segue a lista de algumas linguagens funcionais que surgiram nesse período: Miranda, LML (Lazy ML), Orwell, Alfl, Id, Clean, Ponder e Daisy.

1987 – Só uma Linguagem!

Das linguagens criadas nesse período, somente a linguagem Miranda era comercial, madura, tinha um bom projeto e era usada em produção. As demais, eram esforços individuais dos cientistas – e não possuíam um bom projeto de linguagem. Porém, de uma forma geral, todas possuíam ideias muito interessantes – não era fácil provar que uma linguagem era melhor que outra.

Muito bem, havia um número enorme de linguagens e isso gerou desconforto na comunidade de Programação Funcional. Então, surgiu a ideia de se criar uma única linguagem que englobasse todas as melhores práticas de projeto de linguagem, além de implementar as técnicas funcionais que estavam sendo discutidas na época. Esperava-se que isso trouxesse benefícios para toda a comunidade.

Em Setembro de 1987, houve uma reunião, na conferência de Linguagens de Programação Funcionais e Arquitetura de Computadores, em Portland - Oregon, para discutir essa questão. Assim, foi decidido que uma comissão deveria ser formada para projetar tal linguagem, com a finalidade de:

Proporcionar comunicação mais rápida de novas idéias;
Ser uma fundação estável para o desenvolvimento de aplicações reais;
Ser um meio, através do qual, a Programação Funcional seria encorajada.

Essa comissão decidiu não começar do zero e elegeu uma linguagem como base para o projeto. Bem, a linguagem Miranda era a mais amadurecida e bem projetada – entre as demais. Sendo assim, ela foi escolhida como ponto de partida.

A nova linguagem foi batizada de Haskell. Isso foi uma homenagem ao matemático Haskell Brooks Curry – que contribuir com teorias fundamentais para a Programação Funcional.

A versão 1.0 de Haskell foi liberada em 1990. Em 1999, a linguagem e as bibliotecas básicas foram padronizadas sob o nome Haskell 98.

Por Marcelo Parrela (marcelo.parrela@gmail.com)

2013-10-08

QuickSort em Haskell - Outra Implementação

Estou estudando Haskell faz algum tempo. Existem duas funções que acredito serem o "Hello World!' do Haskell: fatorial e quicksort. Essas duas funções fornecem uma boa idéia do que ganhamos quando descrevemos um problema (forma descritiva) ao invés de tentarmos resolvê-lo (forma imperativa). Quando vi o quicksort (em Haskell) pela primeira vez, percebi que a lista sofria duas leituras: uma para os elementos menores ou iguais ao pivot; outra para os elementos maiores que o pivot.

-- Tradicional: lê a lista duas vezes
quicksort []  = []
quicksort (a:as) = quicksort ( [x | x <- as, x <= a] ) ++   -- primeira leitura
                   [ a ]                               ++  
                   quicksort ( [x | x <- as, x > a] )       -- segunda leitura

Desde essa primeira vez, fiquei incomodado com isso - pois, eu acreditava que seria melhor se fizesse apenas uma leitura na lista. Demorou muito tempo, desde então... :-) Pois, não estudei tão rapidamente quanto poderia. Mas, finalmente, produzi a tal função. Segue o quicksort:

-- Com separador: lê a lista uma vez
-- by Marcelo Parrela (marcelo.parrela@gmail.com)
quicksort' []  = []
quicksort' (a:as) = quicksort' l1 ++ a : quicksort' l2 
    where
        (l1,l2) = separate as a [] []
        -- lê a lista e a separa em duas: l1 para os elementos
        -- menores ou iguais ao pivot e l2 para os demais
        separate [] _ a b = (a,b)
        separate (l:ls) a l1 l2
            | l <= a    = separate ls a l1' l2
            | otherwise = separate ls a l1 l2'
            where 
                l1' = l1++[l] --montando lista de elementos menores
                l2' = l2++[l] --montando lista para os demais elementos

Essa primeira solução ainda não é muito boa - por causa da aplicação da função (++). Esta função, neste contexto, prejudica a performance. Sendo assim, produzi uma segunda solução, corrigindo apenas esse ponto. Segue o código abaixo:

-- Com separador: lê a lista uma vez
-- Com performance melhorada
-- by Marcelo Parrela (marcelo.parrela@gmail.com)
quicksort' []  = []
quicksort' (a:as) = quicksort' l1 ++ a : quicksort' l2 
    where
        (l1,l2) = separate as a [] []
        -- lê a lista e a separa em duas: l1 para os elementos
        -- menores ou iguais ao pivot e l2 para os demais
        separate [] _ a b = (a,b)
        separate (l:ls) a l1 l2
            | l <= a    = separate ls a l1' l2
            | otherwise = separate ls a l1 l2'
            where 
                l1' = l:l1 --montando lista de elementos menores
                l2' = l:l2 --montando lista para os demais elementos

Outro benefício interessante é que esta função é polimórfica. Note que não há declaração de tipos, na definição da função. Isso que dizer que ela pode ser utilizada para ordenar qualquer tipo de dado que seja ordenável. Veja o exemplo abaixo:

    quicksort' "Teste de Ordenacao"
    "  OTaacddeeeenorst"

    quicksort' [3,4,1,0,12,0,(-1),10]
    [-1,0,0,1,3,4,10,12]

    quicksort' [3.25 , 4.0 , 1.2, 0.5 , 12.1 , 0.2 , (-1) , 10 ]
    [-1.0,0.2,0.5,1.2,3.25,4.0,10.0,12.1]

    quicksort' [True, False, True, False, False ]
    [False,False,False,True,True]