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

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