Continuação do Exemplo Simples – Programa completo

Resolvi continuar aquele exemplo com que estava brincando neste post. Nele, basicamente criei uma função extenso que recebia uma String com um número de quatro dígitos e retornava este número por extenso. Agora, porque não fazermos um programa completo, ao invés de apenas umas função?

Bom, para isso vamos organizar um pouco as coisas: coloquei a função extenso em um arquivo “Exercicio.hs” e declarei, no topo do documento, o módulo Exercicio:

module Exercicio
    where

Depois, criei outro arquivo, “Main.hs”, que possuia o seguinte código:

module Main where
import IO
import Exercicio
main = do
    hSetBuffering stdin LineBuffering
    putStrLn "Numero"
    numero <- getLine
    putStrLn("" ++ extenso(numero)++"")

Vamos às explicações.

A primeira linha declara o módulo Main. Para compilar um código em Haskell, é preciso que ele possua obrigatoriamente um módulo Main.

A segunda e a terceira linha contêm imports. IO é um módulo que possui funções de entrada e saída. Exercicio é o módulo que foi criado anteriormente e possui a função extenso.

Na linha seguinte, a função main também é obrigatória na compilação de um programa. É onde a execução inicia-se.

Esta função recebe um bloco do. Este bloco é uma das estruturas mais “misteriosas” do Haskell: Monads. Há muito sobre Monads na Internet, basicamente é um bloco em que as linhas são executadas na ordem, o que é
essencial para programas de entrada e saída. Com isso em mente, vamos em frente.

hSetBuffering stdin LineBuffering indica que vamos trabalhar com a linha de comando.

putStrLn "Numero" imprime “Número” na tela e pula uma linha.

numero <- getLine captura o valor que o usuário digitar.

putStrLn("" ++ extenso(numero)++"") imprime o valor da função extenso(numero).

Teste o módulo Main no interpretador. Se estiver funcionando, pode passar para o próximo passo: a compilação.

Na linha de comando, vá até o diretório em que os dois arquivos estiverem e digite

ghc --make Main.hs -o Extenso.exe

Basicamente, o “Extenso.exe” é o nome do arquivo gerado no final pelo GHC, no Linux, o “.exe” não é necessário.

Depois de compilado, é só executar o Exetenso.exe e se divertir.

Blogged with the Flock Browser

Tags: iniciantes, Haskell, exemplo, compilação

Calcular uma integral

Não sei se eu (finalmente) passei em cálculo, mas enfim…

Estava eu vendo uns programinhas em D passados quando achei um que calculava uma integral definida, então resolvi portá-lo para Haskell.

Primeiro algum embasamento teórico:

Basicamente, uma integral é utilizada para se calcular a área sob uma função (não importando sua forma). Basicamente, a idéia é dividir a função f(x) em vários retângulos de comprimendo dx e altura f(n), onde n é o ponto atual. Vale frisar que é a área até o eixo x.

Observe que quanto menor o valor de dx, maior a precisão.

Neste exemplo, utilizaremos retângulos com base de 0,00001 unidades.

A rotina principal para este cálculo é:

area ini fim fn =
    let
        alturas = map fn [ini,ini+dx .. fim]
        areas = map (dx *) alturas
    in
        foldl (+) 0 areas
    where
        dx = 0.00001

Onde ini e fim delimitam o intervalo que se está calculando. fn é a função.

As funções utilizadas para isso foram:

• map = recebe uma função e uma lista. Retorna uma nova lista, com os valores da função aplicada a cada elemento da lista original. Por exemplo: map (0-) [1,2,3] aplica a função “0-n”, onde n será cada elemento da lista, retornando uma lista [-1,-2,-3].
• foldl = recebe uma função, um valor e uma lista. Aplica a função ao valor e ao primeiro elemento da lista, então  ao valor resultante e ao segundo elemento,  e por aí vai. Por exemplo: foldl (+) 0 [1,2,3] retorna a soma  aplicaria (((0+1)+2)+3), retornando 6. Vale lembrar que essa função avalia a lista da esquerda para a direita (sim, existe uma foldr)

Basicamente o que é feito é:

• Crio a lista com todos os valores no intervalo: [ini,ini+dx .. fim];
• Acho as alturas de cada retângulo, aplicando a função passada à essa lista: alturas = map fn [ini,ini+dx .. fim];
• Acho a área de cada retângulo, multiplicando cada altura pela base (dx): areas = map (dx *) alturas;
• Somo todas as áreas, começando com 0: foldl (+) 0 areas.

Um uso disse seria:

main = do
    (putStrLn.show) (area 0 1 (\x -> x + 3))

Aqui eu calculo a área aproximada da reta x + 3, de x=0 até x=1.

A sintaxe \x -> x + 3 é chamada expressão lambda, e é utilizada para definir uma função anônima inline, que recebe um argumento x e retorna esse argumento + 3.

Listas e Strings – Exemplo Simples

Há alguns meses (em Maio, para ser mais exato), recebi uma mensagem de um estudante com um problema interessante para ser resolvido em Haskell. Dizia ele que o programa deveria receber como entrada um número de quatro dígitos e retorná-lo por extenso. Por exemplo, a entrada “0123″ deveria ter como resposta: “cento e vinte e três”.  Como estou com tempo sobrando (já fechei quase todas as matérias do semestre), resolvi brincar um pouco com esse problema, o que gerou este post.

Resolvi então fazer uma função extenso, que recebe uma string com quatro caracteres e retorna uma string:

extenso ([x,y,z,w]) = mil(x) ++ cen([x, y,z,w]) ++ dec([y,z,w]) ++ if(z == '1')then "" else uni(w)

A linha acima diz que extenso é a concatenação de mil(x), cen([x, y,z,w]), dec([y,z,w]) e if(z == '1')then "" else uni(w), que basicamente seria a concatenação da parte dos milhares, das centenas, das dezenas e das unidades. O “if” no final é para que a parte das unidades só fosse processada quando o valor das dezenas fosse diferente de ‘1′ (quando a dezena vale 1, a unidade é tratada junto com a dezena).
Vamos ver as outras funções:

mil(x):

mil(x) = (case x of
    '0' -> ""
    '1' -> "mil"
    '2' -> "dois mil"
    '3' -> "tres mil"
    '4' -> "quatro mil"
    '5' -> "cinco mil"
    '6' -> "seis mil"
    '7' -> "sete mil"
    '8' -> "oito mil"
    '9' -> "nove mil")

A função acima retorna a parte dos milhares. é bem simples, apenas retorna a parte dos milhares por extenso (e “” para  quando o valor dos milhares for zero).

cen([x, y,z,w]):

cen([x, y,z,w]) =  (if(not(x=='0') && ((y=='0' && (not(z=='0') || not(w=='0'))) || not(y=='0') && z=='0' && w == '0'))then " e " else "") ++ (case y of   
    '0' -> ""
    '1' -> (if (z == '0' && w == '0') then "cem" else "cento")
    '2' -> " duzentos"
    '3' -> " trezentos"
    '4' -> " quatrocentos"
    '5' -> " quinhentos"
    '6' -> " seiscentos"
    '7' -> " setecentos"
    '8' -> " oitocentos"
    '9' -> " novecentos") ++ if ((y=='0') || (z == '0' && w == '0')) then "" else " e "

Retorna a parte das centenas. o if inicial e o final tratam o aparecimento do “e” entre as palavras. Repare também no tratamento do ‘1′, que às vezes aparece como “cem” e outras como “cento”.

dec([y,z,w]):

dec([y,z,w]) = (case z of
    '0' -> ""
    '1' -> decDez(w)
    '2' -> "vinte"
    '3' -> "trinta"
    '4' -> "quarenta"
    '5' -> "cinquenta"
    '6' -> "sessenta"
    '7' -> "setenta"
    '8' -> "oitenta"
    '9' -> "noventa" ) ++ if(z == '0' || z== '1' || w == '0') then "" else " e "

decDez(w) = case w of
    '0' -> "dez"
    '1' -> "onze"
    '2' -> "doze"
    '3' -> "treze"
    '4' -> "quatorze"
    '5' -> "quinze"
    '6' -> "dezesseis"
    '7' -> "dezesete"
    '8' -> "dezoito"
    '9' -> "dezenove"

Aqui tratamos a parte das dezenas. Quando o valor for ‘1′, temos que fazer um tratamento especial, então usamos a função decDez(w). No final temos um if para tratar o uso do “e”.

uni(x):

uni(x) = case x of
    '0' -> ""
    '1' -> "um"
    '2' -> "dois"
    '3' -> "tres"
    '4' -> "quatro"
    '5' -> "cinco"
    '6' -> "seis"
    '7' -> "sete"
    '8' -> "oito"
    '9' -> "nove"

Finalmente, a função uni(x) cuida da parte das unidades.

Este problema é de fácil resolução, deixo como exercício para quem quiser brincar um pouco com listas. Bug do meu código: o valor “0000″ retorna “” (faltou tratar isso =P).

Blogged with the Flock Browser

Tags: haskell, iniciantes, lista

Google Treasure Hunt: robot

Hoje comecei a resolver o segundo “desafio” do Google Treasure Hunt (eu estava fazendo em D), e resolvi tentar o “desafio” anterior.

Basicamente, o desafio era:

Dada uma grid de tamanho L x C, o objetivo era ver o número de caminhos possíveis entre [0,0] e (L,C), realizando apenas movimentos para baixo e para a direita. Como os números que estavam dando eram “meio” grandes, resolvi fazer em Haskell (lembrando que esse conceito de inteiro de 32bits em Haskell não é necessariamente existente. Os números são tão grandes quanto for necessário).

Então, vamos à explicação do método:

Sabemos que para chegar da origem ao destino, são necessários L – 1 + C – 1 (número de linhas + número de colunas, desconsiderando a célula de origem – você precisa se movimentar até ela) movimentos. Então vamos definir essas constantes:

c = C - 1 :: Integer
l = L - 1 :: Integer

(lembre-se de substituir o C e o L pelos valores que foram passados no seu desafio).

Agora, vamos supor que o caminho seja formado pelas letras D (direita) e B (baixo). O número total de caminhos possíveis seria o número de combinações de D e B, no caso c * B e l * D. Por exemplo: supondo c = 3 e l = 2, teríamos que fazer todas as combinações possíveis com DDBBB, ou seja:

BBBDD
BBDDB
BDDBB
DDBBB
BDBBD
BDBDB
...

Para isso, (você deve se lembrar de suas aulas de estatística), basta pegar o fatorial do número total de elementos (C – 1 + L – 1). Então nossa função para fatorial será novamente necessária:

fac :: Integer -> Integer
fac n = product [1..n]

E vamos aproveitar para definir o total:

facT = fac(c + l) :: Integer

Com isso será obtido o número total de caminhos, mas o desafio pede apenas os caminhos únicos (sim, há caminhos repetidos se parar por aqui, pois, apesar de serem iguais, haverão duas combinações BBDDB, por exemplo).

Então, como os R podem ser combinados para formar caminhos iguais, teremos que remover alguns destes. Para isso, vamos começar vendo quantas combinações de Rs e Bs são possíveis:

facC = fac (C - 1) :: Integer
facL = fac (L - 1) :: Integer

Com isso, teremos o número de duplicatas por caminho encontrado.

Agora basta dividir o total de caminhos possíveis pelos números de caminhos duplicados:

resultado = facT  `div` facC `div` facL :: Integer

Ou seja, basta aplicar a “equação”:

(C - 1 + L - 1)! / (C - 1)! / (L - 1)!

O programa completo (no meu caso, foi uma grid de 42 x 50):

module Main where

fac :: Integer -> Integer
fac n = product [1..n]

c = 42 - 1 :: Integer
l = 50 - 1 :: Integer

facT = fac (c + l) :: Integer
facC = fac (42 - 1) :: Integer
facL = fac (50 - 1) :: Integer

resultado = facT  `div` facC `div` facL :: Integer

main :: IO()
main = do
	(putStrLn.show) resultado

blogblogs tags:haskell, programacao, funcional

Programação Funcional – Parte III – Mais sobre Funções

No último post você viu um exemplo de uma função para calcular o fatorial de um número.

Agora, continuando no tópico de funções, veremos mais alguns conceitos.

Primeiramente, você viu que foi especificado o tipo da função fatorial, que era Int -> Int, ou seja, uma função que recebe um inteiro e retorna um inteiro.

Agora, vejamos outra função:

soma :: Int -> Int -> Int
soma a b = a + b

Como o nome nos diz, essa função retorna a soma de seus dois argumentos.

Vamos começar a ver alguns de seus detalhes.

A primeira coisa que deve ser notada é que esta é uma função pura. ou seja, ela não faz alteração de nenhum estado e seu valor de retorno depende unicamente de seus valores de entrada.

“Mas você não havia dito que linguagens funcionais não guardam estado? Então todas as funções são puras?”

Não exatamente. Para conflitar com isso, vejamos, por exemplo, uma função que retorne um número aleatório. Normalmente estas não recebem nenhum parâmetro, mas retornam resultados variados. Então esse tipo de função não é pura.
Outro exemplo de funções impuras são funções que realizam operações de entrada e saída.

Outra coisa que deve ser notada é a declaração do tipo da função: Int -> Int -> Int. Isso não parece com algo que receba dois inteiros e retorne outro. E realmente não é isso.

Se você olhar a origem das linguagens funcionais, verá que são uma evolução do Cálculo Lambda, e uma de suas características é que as funções são unárias, ou seja, recebem apenas um argumento.

Voltemos ao fato de que funções são tipos de “alta ordem” em linguagens funcionais. Isso quer dizer que funções podem ser passadas como argumentos, ou podem ser retornadas de outros funções.

Na verdade, o que acontece é exatamente isso, em uma técnica chamada currying. O que ocorre realmente é que a função soma recebe apenas um argumento, retorna uma função que recebe mais um argumento e que, aí sim, retorna o resultado: Int -> (Int -> Int).

Listas e Strings – Parte I

Hora de iniciarmos um estudo sobre Listas, uma estrutura bastante poderosa na linguagem Haskell.

Uma das vantagens das listas é que elas podem ser infinitas (o que é realmente útil), porém elas devem ser homogêneas, ou seja, todos os elementos dela devem ser de um mesmo tipo.

NOTA: Onde eu achar necessário, colocarei a resposta do interpretador, que estará em verde.

Criar uma lista é bem simples, basta colocar seus elementos entre colchetes:

[1, 2, 3]

Listas também podem ser criadas sem nenhum elemento:

[ ]

Para adicionar novos elementos ao início da lista, basta usar o operador cons (“:”):

0 : [1, 2, 3]
[0, 1, 2, 3]

0 : 1 : 2 : 3 : [ ]
[0, 1, 2, 3]

Para concatenar duas listas, use o operador “++”

[0, 1, 2] ++ [3]
[0, 1, 2, 3]

Outras duas funções simples para listas são head e tail. A função head retorna o primeiro elemento da lista, enquanto tail retorna uma lista com todos os elementos exceto o primeiro:

head [0, 1, 2, 3]
0

tail [0, 1, 2, 3]
[1, 2, 3]

O número de elementos da lista se consegue usando a função length:

length [1, 2, 3]
3

Strings são apenas listas de caracteres, portanto todas as funções de lista valem para Strings:

['a','b','c']
"abc"

'a' : "bc"
"abc"

"ab" ++ "c"
"abc"

head "abc"
'a'

tail "abc"
"bc"

length "abc"
3

Blogged with the Flock Browser

Tags: listas, strings, Haskell

Haskell – Pares, trios, quádruplas…

Vamos começar hoje a ver algumas estruturas do Haskell, começando com as tuplas.

Em Haskell, é possível declarar pares de elementos, bastando apenas colocá-los entre parenteses, dessa forma:

(1, 7)

Para pegar o primeiro elemento da tupla, use fst:

fst (1, 7)

E para pegar segundo, use o snd:

snd (1, 7)

É possível generalizar esta estrutura e criar trios, quádruplas… Esta estrutura é chamada de tupla.

Tuplas não exigem que os seus elementos sejam todos do mesmo tipo, é possível juntar Strings, inteiros, o que você quiser (até mesmo outras tuplas):

(1, "String", (2, 'a'))

NOTA: fst e snd funcionam apenas com pares, se tentar utilizá-las com tuplas maiores, um erro é retornado.

Uma desvantagem das tuplas é que elas guardam um número finito de elementos, não podendo ter o número de elementos alterado, enquanto as listas (assunto para outro(s) post(s)) podem ser infinitas.

Blogged with the Flock Browser

Tags: haskell, tuplas

Programando em Haskell – Onde começar?

1. Onde aprender?
No site da linguagem Haskell há uma  boa coleção de livros e material on-line para se aprender Haskell, tanto para quem nunca programou, para quem tem experiência com linguagens imperativas e para quem já trabalhou com outras linguagens funcionais.

Eu estou seguindo o Haskell Tutorial for C Programmers, um tutorial muito bom para aqueles que, como eu, já está acostumado com linguagens imperativas. O autor faz comparações entre as linguagens funcionais e as imperativas, demonstrando as funcionalidades específicas da Haskell, com muitos exemplos bem explicados.

Outro tutorial é o Yet Another Haskell Tutorial, que estou vendo agora e também parece ser muito bom (o prório site da Haskell o indica como “o melhor”^[1]).

2. O que baixar?

Existem várias implementações de Haskell (compiladores/interpretadores) na Internet, disponibilizadas gratuitamente. Mas apenas duas são largamente usadas: GHC e Hugs.
Ambas as implementações funcionam tanto como compiladores quanto interpretadores.
A primeira, mais utilizada, é considerada por muitos a implementação padrão do Haskell: é a que possui maior número de ferramentas e extensões e o código possui uma melhor performance, mas é a mais pesada das implementações (~33 Mb). O GHC possui também um interpretador (GHCi), que pode ser utilizado durante seus estudos.

Para quem está começando, e não precisa de todas as ferramentas que o GHC oferece, existe o  Hugs. Além de ser bem menor do que o GHC (existe até uma versão mini, de 1.4 Mb),  sua compilação rápida é boa para quem quer estudar a linguagem e vai recompilar código várias vezes.

3. Onde encontro mais material?

Em haskell.org há grande disponibilidade de livros e material on-line para aprender Haskell. Tem também links para mailing lists, artigos diversos sobre a linguagem, implementações da linguagem e informações diversas sobre a comunidade Haskell.

4. Links:

• Haskell
• Haskell Tutorial for C Programmers
• Yet Another Haskell Tutorial
• GHC
• Hugs

^[1] http://haskell.org/haskellwiki/Learning_Haskell

Blogged with the Flock Browser

Tags: Haskell, programar, iniciantes

Programação Funcional – Parte II – Funções

No último post (que ficou meio incompleto, confesso), comecei a falar um pouco sobre o paradigma da programação funcional.

Uma das coisas citadas é o fato de o programa ser tratado como um conjunto de funções matemáticas. O que isso quer dizer?

Para visualizar isso, vamos ao clássico exemplo do fatorial.

Matematicamente falando, n! (n fatorial) é o produto de todos os números menores ou iguais a n. Ou seja, o produto entre todos os números de 1 até n. Por exemplo: 5! = 1 * 2 * 3 * 4 * 5.

Observe que 0! = 1 já que o resultado de não se multiplicar nenhum número (identidade multiplicativa) é 1 (mais informações em http://en.wikipedia.org/wiki/Empty_product).

Normalmente existem 2 formas de se fazer isso: recursiva e interativa:

Recursiva:

int fatorial(int n)
{
    if(n <= 1)
        return 1;
    return n * fatorial(n - 1);
}

 
Interativa:

int fatorial(int n)
{
    int r = 1;

    while(n > 1)
        r *= n--;
    return r;
}

Isso em uma linguagem funcional (no caso, Haskell), ficaria como:

fatorial :: Int -> Int
fatorial 0 = 1
fatorial n = n * fatorial (n - 1)

Muito parecido com a versão recursiva em linguagens não-funcionais.

E, de fato, muito do que se faz em uma linguagem funcional é recursivo.

Porém, uma linguagem funcional normalmente oferece vários “artifícios matemáticos” para se trabalhar.

Em Haskell, por exemplo, isso poderia ser escrito como

fatorial :: Int -> Int
fatorial n = product [1..n]

ou seja, literalmente o que diz a definição: o produto entre todos os números de 1 até n.

Uma das principais vantagens disso é a redução da quantidade de código. Considerando que a declaração do tipo não é necessáriamente obrigatória (apesar de uma boa prática) a função pode ser implementada em apenas uma ou duas linhas, respeitando os padrões de identação e tudo mais.

Programação Funcional – Parte I – Definição

Como o título do post sugere, começarei a abordar Programação Funcional. Ainda olhando para o título, pode-se perceber que essa é apenas a primeira de uma série de artigos. E olhando mais para o final do título, você poderá perceber que esta é apenas uma definição, ou simples explanação do que é o paradigma de programação funcional.

Então, vamos lá…

Programação funcional é o estilo de programação que trata as partes de um programa como funções matemáticas. Isso quer dizer que o programa não guarda estado, não possui variáveis, enfim, não tem nada que altere o valor. Tudo (ou quase) são funções.

Linguagens que seguem este estilo (como Haskell, por exemplo) tem as funções como tipos de “primeira classe”, isto é, você pode declarar funções, passá-las como parâmetros para outras funções, enfim, são tipos de dados como qualquer outro.

Outra característica da programação funcional é que normalmente as funções são puras, ou seja, não dependem de nenhum “efeito colateral”, como variáveis globais, passagem por referência, enfim, seu resultado depende apenas dos parâmetros de entrada.

Agora você deve estar se perguntando: “Por que eu iria querer usar uma linguagem que não tem variáveis?”.

Algumas das vantagens da programação funcional:

• Não guardando o estado de nada, o compilador pode fazer otimizações normalmente inseguras em outro tipo de linguagem;
• Normalmente as linguagens funcionais usam Lazy Evaluation, ou seja, só avaliam uma coisa se ela for realmente usada;
• É eficiente em aplicativos multi-threaded, já que não há risco de que algo indesejado seja alterado.