Mostrando postagens com marcador Haskell. Mostrar todas as postagens
Mostrando postagens com marcador Haskell. Mostrar todas as postagens

domingo, 24 de agosto de 2014

Combinador de ponto fixo

Glider A beleza da matemática e do cálculo é que algo não precisa ter uma aplicação prática imediata para ser estudado em profundidade. A aplicabilidade pode surgir 150, 200 anos após sua concepção.

Um dos tópicos mais magníficos do cálculo-λ é o combinador de ponto fixo, apesar de ser de interesse mais acadêmico do que diretamente prático.

Ainda assim, seu entendimento engrandece em tamanha proporção o conhecimento do programador, que vale a pela dedicar-lhe algum tempo.

Conceitos básicos

Há alguns pré-requisitos que você precisa conhecer para começar nosso estudo:

Cálculo-λ

Cálculo-λ é uma parte da lógica matemática criada da década de 1930 como parte da investigação dos fundamentos da matemática. No cálculo-λ, todos os elementos são funções de primeira classe, inclusive os números.

Por exemplo, o número 2 é uma função que aplica uma outra função duas vezes, e é representado como λsz.s(sz).

O sinal + (ou S em alguns textos) significa incremento, e é descrito como λwyx.y(wyx). Ou seja, +3 é 3 incrementado, que é igual a 4. 2+3 é a função 2 recebendo como parâmetros + e 3, ou seja, incrementa duas vezes o número 3, +(+3), o que resulta em 5.

A multiplicação é prefixal, não mesoclítica, ou seja, 2x escreve-se como *2x (ou M2x) e sua definição é λab.a(b+)0 ou λxyz.x(yz).

O cálculo-λ é o princípio de onde deriva a programação funcional.

[update 2014-08-25]
A definição de decremento é (caso eu não tenha copiado errado):
DEC = λnfx.n (λgh.h(gf)) (λu.x) I
[/update]

Ponto fixo

Impossível entender combinador de ponto fixo sem saber o que significa ponto fixo. Ponto fixo é o ponto de uma função onde o valor retornado é igual ao valor fornecido.

Por exemplo, dada a função f(x) = 2x-1, o que em notação cálculo-λ fica f = λx.DEC(*2x), o ponto fixo é aquele onde fx = x, ou seja, o resultado é igual ao parâmetro.

Usando aritmética básica:
f(x) = 2x - 1
x = 2x - 1
2x - 1 = x
2x - 1 - x = 0
x - 1 = 0
x = 1

Portanto o ponto fixo de λx.DEC(*2x) é 1.

Repare que a recursão sobre o ponto fixo resulta sempre no mesmo resultado. Se:
x = fx

Podemos substituir x por fx:
x = fx = f(fx) = f(f(fx))) = ...


Variáveis livres e vinculadas

Em cálculo-λ, no corpo de uma função, todas as variáveis que vêm de sua assinatura são vinculadas e as que vêm de fora são livres.

Por exemplo, na função:
λfx.Δxf


As variáveis x e f são vinculadas e a variável Δ é livre.

Combinadores

Combinadores são funções que não possuem variáveis livres. Por exemplo:
λx.xx
λx.y

A primeira linha é um combinador, já a segunda não.

Veja que, a rigor, números e operadores aritméticos são variáveis livres, porém, como são valores constantes e bem definidos, tratam-se de exceções aceitáveis em um combinador.

Construção let

A construção let é uma construção clássica em cálculo-λ e em linguagens funcionais de programação.

Darei um exemplo: seja fx igual a *2x em f4, o resultado é 8 – fx é o dobro e x e o caso é f4. Isso é descrito assim:
let fx = *2x in f4

Podemos construir uma função assim, por exemplo, dado o parâmetro x, sendo fa igual a *2a em fx-1:
λx.let fa = *2a in DEC(fx)

É o mesmo que:
λx.DEC(*2x)

Em Haskell isso pode ser escrito assim:
func x = let f a = 2 * a in f x - 1

Em Racket fica assim:
(describe func
  (λ (x)
    (let ((f (λ (a) (* 2 a)))
      (- (f x) 1))))

A forma genérica da construção let é:
let fx = y in z

E sua abertura é:
(λf.z)(λx.y)


Finalmente: o combinador de ponto fixo

Combinador de ponto fixo é uma função que retorna o ponto fixo da função fornecida como parâmetro. Em cálculo e mesmo em programação isso é muito útil na implementação de funções recursivas.

Função recursiva é aquela que faz chamada a ela mesma, por exemplo, fatorial:
FACT = λn.(ISZERO n) 1 (*n (FACT (DEC n)))

Olhando para o corpo da função, mesmo desconsiderando números e operadores (ISZERO, 1, * e DEC), ainda há a variável livre FACT, que não é definida na assinatura da função.

[update 2014-08-25]
A definição de ISZERO é:
TRUE = λxy.x
FALSE = λxy.y
ISZERO = λn.n(λx.FALSE)TRUE
[/update]

A forma de resolver isso é criar uma função que recebe a si mesma na assinatura:
ALMOST-FACT = λfn.(ISZERO n) 1 (*n (f (DEC n)))

Quando esse combinador recebe como parâmetro o fatorial, ele retorna o próprio fatorial, assim a função fatorial é o ponto fixo dele!

O combinador de ponto fixo é aquele que, ao receber a função como parâmetro, retorna seu ponto fixo – e quando a função recebe o ponto fixo, retorna o próprio ponto fixo, segundo o seguinte comportamento:
yf = f(yf)

Só aqui já seria possível implementar uma função que calcule o ponto fixo. Em Haskell:
fix f = f (fix f)

E em Lazy Racket:
(define fix
  (λ (f)
    (f (fix f))))

Porém seria sem sentido, pois essa mesma função que resolve o problema, é parte do problema, já que ela própria possui variável livre.

Resolver este problema não é difícil: basta pegarmos a definição: dada uma função f, queremos o ponto x onde fx seja igual a x… é uma construção let!

Data uma função que recebe f (λf.), seja x igual a fx (let x = fx) em x (in x):
λf.let x = fx in x

De fato isso já funciona em Haskell:
fix :: (a -> a) -> a
fix f = let x = f x in x


Combinador Y

Para Scheme (Lazy Racket), precisamos destrinchar um pouco mais, abrindo o let.

Precisamos de dois parâmetros na primeira posição, portanto dobraremos o x:
λf.let x = fx in x
λf.let xx = f(xx) in xx
λf.(λx.xx)(λx.f(xx))

Mais um passo e chegamos ao famoso combinador Y de Curry!

Aplicando o parâmetro λx.f(xx) à função λx.xx, temos (λx.f(xx))(λx.f(xx)), exatamente o combinador Y de Curry:
Y = λf.(λx.f(xx))(λx.f(xx))

Em Lazy Racket:
(define Y
  (λ (f)
    ((λ (x) (f (x x))) (λ (x) (f (x x))))))


Linguagens estritas

A maioria das linguagens não suporta lazy evaluation, então é preciso fazer um truque para que a definição do combinador não entre em loop infinito.

O truque é aplicar a função λsv.sv (que é o número 1, equivalente à identidade: I = λx.x). Por exemplo:
g = 1g
g = (λsv.sv) g
g = (λv.gv)

Por exemplo, o combinador Y em Python:
Y = lambda f: (lambda x: x(x))(lambda x: f(x(x)))

Esse código entra em loop infinito! Mas se substituirmos xx por λv.xxv, tudo se resolve:
Y = lambda f: (lambda x: x(x))(lambda x: f(lambda *args: x(x)(*args)))


Outros combinadores de ponto fixo

Curry foi o que obteve a solução mais simples para o combinador de ponto fixo, mas não foi o único. Há outras soluções possíveis.

Combinador de Turing:
Θ = (λx.xx)(λab.b(aab))


Combinador de ponto fixo estrito (vimos acima):
Z = λf.(λx.xx)(λx.f(λv.xxv))

Combinador de ponto fixo não padrão:
B = λwyx.w(yx)
∆ = λx.xx
N = B∆(B(B ∆)B)

[]’s

sábado, 12 de outubro de 2013

Encadeamento de funções

Poliedro Encadeamento de função é o pattern onde um grupo de funções é encadeado.

Em uma cadeia, sempre a saída de uma função é a entrada da seguinte, o parâmetro inicial é fornecido à primeira função da cadeia, que segue executando as funções, e o resultado da última função é retornado como resultado da cadeia.

Vejamos como criar cadeia.

Python

A forma mais simples simples de encadear funções é simplesmente efetuar a chamada, como o código Python a seguir:
f1 = lambda x: x * 2
f2 = lambda x: x - 1
f3 = lambda x: x // 3

print(f3(f2(f1(8))))

Porém esse código é visualmente confuso e difícil de ser depurado. É conveniente criar uma fábrica (factory) de cadeias:
chain = lambda *funcs: \
    reduce(lambda acc, func: (lambda x: func(acc(x))),
    funcs or [lambda x: x])

the_chain = chain(
    lambda x: x * 2,
    lambda x: x - 1,
    lambda x: x // 3,
)
print(the_chain(8))

Repare que as funções agora estão na ordem em que são executadas:
  1. O número é dobrado;
  2. O resultado da primeira função é decrementado;
  3. O resultado da terceira função é triplicado e retornado.

A função reduce() de Python executa a redução de um map/reduce: o primeiro parâmetro é uma função que recebe o acumulador e o próximo valor, retornando o resultado parcial.

O segundo parâmetro de reduce() é a lista a ser reduzida, no caso, a lista de funções ou, caso nenhuma função tenha sido informada, um função vazia que retorna o próprio parâmetro fornecido.

Com este procedimento, é possível reduzir a lista de funções a uma função representando o encadeamento das funções fornecidas.

Erlang

Em Erlang as coisas também podem ser interessantes.

Criaremos duas funções, uma fábrica a ser exportado (chain/1) e uma função de redução (chain/2) que não deve ser exportada:
-module(chain).
-export([chain/1]).

chain(Funs) when is_list(Funs) ->
    chain(Funs, fun(X) -> X).

chain([], Acc) -> Acc;

chain([Fun|Rest], Acc) when is_function(Fun) ->
    chain(Rest, fun(X) -> Fun(Acc(X)) end).

Você pode então executar no shell:
1> c(chain).
{ok,chain}
2> Fun = chain:chain([
2> fun(X) -> X * 2 end,
2> fun(X) -> X - 1 end,
2> fun(X) -> X div 3 end
2> ]).
#Fun<chain.1.134034448>
3> Fun(8).
5
4> 

Haskell

Haskell por outro lado já possui uma fábrica de cadeias, usando o carácter $, infelizmente na ordem inversa: primeiro as últimas funções a serem executadas, e por último as primeiras.

Então, por exemplo: f1 $ f2 $ f3 x é executado como f1 (f2 (f3 x)).

Crie um módulo:
module Chain where

the_chain :: Int -> Int
the_chain n = (`div` 3) $ (\x -> x - 1) $ (* 2) n

No prompt do ghci execute:
Prelude> :load chain.hs
[1 of 1] Compiling Chain            ( chain.hs, interpreted )
Ok, modules loaded: Chain.
*Chain> the_chain 8
5
*Chain> 

[]’s
Cacilhας, La Batalema

quinta-feira, 14 de janeiro de 2010

FizzBuzz (No Stairway to Heaven)

Glider Hoje um amigo meu veio falar comigo de uma brincadeira velha – e que eu não conhecia – chamada FizzBuzz.

[update 2010-01-15]
Sugestão de apontador do Cesar Barros: If something is worth doing….

A propósito, atualizei o código Lisp.
[/update]

A brincadeira consiste em imprimir uma sequência de números, tradicionalmente de 1 a 100. Porém os números múltiplos de 3 devem ser substituídos por fizz e os números múltiplos de 5 por buzz. Os números que são divisíveis por 3 e por 5 devem ser substituídos por fizzbuzz.

No Stackoverflow você pode encontrar as versões mais loucas, como LOLCODE, Brainf*ck, Ook, assembly de 8051, 6502 e Linux IA-32, Hebreu Estruturado, Cobol e Forth, como destaque para o poético código em Perl.

Aqui quero postar algumas soluções que achei interessantes.

**

Em Haskell:
putStr (concat [if (mod x 15)==0 then "fizzbuzz\n" else if (mod x 3)==0 then "fizz\n" else if (mod x 5)==0 then "buzz\n" else (show x) ++ "\n" | x <- [1..100]])


Em Python:
print "\n".join('fizzbuzz' if x%15==0 else 'fizz' if x%3==0 else 'buzz' if x%5==0 else str(x) for x in xrange(1, 101))


Em Perl:
print +(fizz)[$_%3] . (buzz)[$_%5] || $_, $/ for 1..100;


Em Common Lisp:
(format t "~{~A~%~}" (loop for x from 1 to 100 collect (if (zerop (mod x 15)) "fizzbuzz" (if (zerop (mod x 3)) "fizz" (if (zerop (mod x 5)) "buzz" x)))))


[]’s
Cacilhas, La Batalema

quarta-feira, 21 de outubro de 2009

Mais sobre programação funcional

Paradigma funcional

Aproveitando o ensejo do artigo anterior sobre programação funcional, gostaria de puxar mais este artigo sobre três algoritmos tradicionais: sequência de Fibonacci, fatorial e quick sort.


Fatorial


Fatorial é um dos algoritmos recursivos mais tradicionais da Matemática. É também um dos algoritmos mais simples:
0!=1 n!=n*(n-1)!


Sua implementação tanto em Haskell quanto em Common Lisp descreve exatamente esse algoritmo.

Em Haskell:
factorial :: Integer -> Integer
factorial 0 = 1
factorial n = n * (factorial (n - 1))


Em Common Lisp:
(defun factorial ((n integer))
(if (zerop n)
n
(* n (factorial (- n 1)))))


Já em Scheme a coisa pode complicar… se o interpretador (uso guile) tiver sido compilado com suporte a bignum, tudo bem, se não, é preciso fazer uma pequena mágica, multiplicando os resultados do maior para o menor:
(define (factorial n)
(define (loop k l)
(if (zero? k)
l
(loop (- k 1) (* k l))))
(loop n 1))


Sequência de Fibonacci


A Sequência de Fibonacci é uma progressão natural iniciando por 1, 1 e progredindo ao passo de que cada elemento é a soma dos dois anteriores:
a0=1 a1=1 an=a(n-2)+a(n-1)


É uma sequência recursiva em árvore binária, o pesadelo dos programadores. =D

Mas como já foi muito estudada, há diversas formas de implementá-la sem usar código recursivo, como algoritmo reiterativo, potência de matrizes e função fechada.

A seguinte implementação em Haskell utiliza recursão e lista infinita:
fib :: [Integer]
fib = 1 : 1 : zipWith (+) fib (tail fib)


Já em Common Lisp foi uma boa ideia usar reiteração, muito mais elegante do que seria possível em qualquer linguagem imperativa:
(defun fib (index)
(check-type index (integer 0 *))
(loop
for a = 1 then b
and b = 1 then (+ a b)
repeat index
finally (return a)))


Quick sort


O algoritmo de ordenação quick sort é a exceção das exceções: um algoritmo de ordenação recursivo em árvore binária, o que deveria ser o pior dos casos, no entanto é um dos métodos de ordenação mais rápidos e eficientes que conhecemos.

O princípio é o seguinte: toma-se um elemento qualquer da lista, tradicionalmente o primeiro, então separa-se a lista em duas, uma de elementos menores que o tomado e outra de elementos maiores. Aplica-se a mesma ordenação quick sort a cada uma das novas listas e concatena-as com o elemento tomado no meio.

Em Haskell isso pode ser descrito assim:
qsort :: Ord a => [a] -> [a]
qsort [] = []
qsort (x:xs) = qsort lesser ++ [x] ++ qsort greater
where
lesser = [e | e <- xs, e < x]
greater = [e | e <- xs, e >= x]


Em Common Lisp o princípio é o mesmo, mas com aquele monte de parêntesis característicos de Lisp:
(defun qsort ((a-list list))
(if (< (length a-list) 2)
a-list
(let ((x (pop a-list)))
(concatenate 'list
(qsort
(loop for e in a-list
if (< e x)
collect e))
(list x)
(qsort
(loop for e in a-list
if (>= e x)
collect e))))))



**

Espero que este artigo tenha sido interessante e cause curiosidade aos leitores sobre programação funcional.

[]'s
Cacilhas, La Batalema

sexta-feira, 16 de outubro de 2009

Oddwording de novo

Poliedro Em maio de 2007 publiquei um artigo sobre a implementação do algoritmo oddwording em diversas linguagens de programação.

Para relembrar, segue o código em Haskell:

module Main where

import IO


main = mainloop


mainloop :: IO ()
mainloop = do
ph <- readString
if ph == ""
then
return ()
else do
let nph = oddword ph
putStrLn nph
mainloop


readString :: IO String
readString = do
putStrLn "Digite uma frase: "
putStr "> "
hFlush stdout
s <- getLine
return s


oddword :: String -> String
oddword s = listToStr $ invodd $ strToList s


strToList :: String -> [String]
strToList "" = []
strToList s = (take spi s) : (strToList (drop (incr spi) s))
where spi = nextspace s


incr :: Int -> Int
incr = (+ 1)


nextspace :: String -> Int
nextspace "" = 0
nextspace (x:xs) =
if x == ' '
then
0
else
1 + (nextspace xs)


listToStr :: [String] -> String
listToStr [] = ""
listToStr (x:xs) = x ++ " " ++ (listToStr xs)


invodd :: Ord a => [[a]] -> [[a]]
invodd [] = []
invodd (x:xs) = x : (inveven xs)


inveven :: Ord a => [[a]] -> [[a]]
inveven [] = []
inveven (x:xs) = (inv x) : (invodd xs)


inv :: Ord a => [a] -> [a]
inv [] = []
inv (x:xs) = (inv xs) ++ [x]

<update ressaca>
Havia esquecido de forçar o flush de STOUT na função readString. Corrigido!
</update>

No entanto ficou faltando uma linguagem excepcionalmente importante, Lisp.

Lisp (LISt Processing) é uma família de linguagens funcionais concebida por John McCarthy em 1958, baseada no cálculo lambda. As principais linguagens da família Lisp são Common Lisp, Scheme e Emacs Lisp.

O código acima será reimplementado abaixo em Common Lisp.

Observação: os blocos de código deverão ser escritos em arquivo na ordem inversa em que aparecem aqui, ou seja, digite cada bloco no arquivo em linhas acima do bloco digitado anteriormente.

Ciclo principal


O ciclo principal será a função mainloop. Sua lógica de funcionamento é a seguinte:
  1. Pegar uma string digitada na entrada padrão;
  2. Se a string for vazia, sair do programa;
  3. Aplicar o algoritmo oddwording;
  4. Exibir na tela o resultado;
  5. Recomeçar o ciclo.


A função fica assim:
(defun mainloop ()
(loop do
(format t "~&~a~%"
(oddword (*exit-if-empty* (*read-string*))))))


Lendo uma linha da entrada padrão


Para ler uma linha da entrada padrão, devemos exibir um prompt, ler a entrada digitada pelo usuário e remover os espaços em branco do começo e do fim:
(defun *read-string* ()
(format t "~&Digite uma frase:~%> ")
(string-trim " " (read-line)))


Saindo caso a string esteja vazia


Caso nada tenha sido digitado, o programa encerra. Para isso é preciso avaliar a string, encerrando o processo se apropriado, caso contrário retornar a string:
(defun *exit-if-empty* ((a-string string))
(if (string= a-string "")
(exit)
a-string))


Descrição do algoritmo em alto nível


Podemos agora definir em alto nível o algoritmo oddwording:
  1. Transformar a string em uma lista de palavras;
  2. Inverter somente o conteúdo dos elementos de índice ímpar da lista;
  3. Transformar novamente a lista de palavras em uma string.

(defun oddword ((a-string string))
(list-to-str (invodd (str-to-list a-string))))


String para lista


Para transformar uma string em uma lista, basta quebrada em cada ocorrência de espaço (#\Space):
(defun str-to-list ((a-string string))
(loop
for i = 0 then (1+ j)
as j = (position #\Space a-string :start i)
collect (subseq a-string i j)
while j))


Lista para string


Para transformar uma lista de palavras em uma string única, é preciso concatenar todos os elementos da lista, sem esquecer de acrescentar espaços entre eles:
(defun list-to-str ((a-list list))
(string-trim " "
(apply #'concatenate 'string
(loop for e in a-list
collect (concatenate 'string e " ")))))


Inversão dos elementos ímpares


Só faltou inverter os elementos de índice ímpar da lista. Nada mais simples: pegar cada elemento, se o índice for ímpar, inverter:
(defun invodd ((a-list list))
(loop
for x in a-list
and i from 0
collect (if (oddp i)
(reverse x)
x)))


Fazendo funcionar


Para que tudo aconteça, no final do arquivo acrescente uma chamada à função principal:
(mainloop)


E execute o arquivo com o comando clisp (aconselho o uso dos parâmetros -K full e -q).


**

Lisp tem uma abordagem extremamente elegante e clara, aproveita o paradigma funcional perfeitamente e seus programas podem ser retroalimentados recursivamente para obter-se um comportamento de aprendizado, apreciado no desenvolvimento de IA.

[]'s
Cacilhas, La Batalema

<update 2009-10-20>
Adicionada tipagem aos argumentos das funções e removido código redundante.
</update>

quinta-feira, 10 de maio de 2007

Oddwording

Poliedro Tem corrido por aí uma brincadeira chamada oddwording (do inglês odd words, «palavras ímpares»).

A idéia é pegar uma frase, indexar as palavras a partir de zero e inverter as palavras de índice ímpar.

Fiz três códigos: Python, Lua e Haskell.

Python


Dos três é o menor. Precisei criar apenas uma função oddword(). Essa função gera um reiterador.

Para começar, vamos ao cabeçalho Python padrão:
# -*- coding: UTF-8 -*-

import re
import os, sys


O módulo re (expressões regulares) será usado para quebrar a frase em palavras.

A idéia da função é partir a frase em uma lista de palavras. Será usada uma variável odd, que marca verdadeiro quando o índice for ímpar. Quando for par, retorna a palavra, quando for ímpar, retorna a inversão da palavra:
def oddword(phr):
odd = False
for w in re.findall(r'\S+', phr):
if odd:
yield w[::-1] + " "
odd = False
else:
yield w + " "
odd = True
yield "\n"


Essa função já faz tudo. Vamos a uma «main» que demonstre seu funcionamento:
if __name__ == "__main__":
print("Digite uma frase:")
sys.stdout.write("> ")
ph = sys.stdin.readline().strip()

while ph:
wordproc = oddword(ph)
while True:
try:
word = wordproc.next()
sys.stdout.write(word)
except StopIteration:
break

print("Digite uma frase:")
sys.stdout.write("> ")
ph = sys.stdin.readline().strip()


[update 2007-05-11]
O Carlos Eduardo sugeriu nos comentários o uso de list comprehension.

Então o código Python fica assim:
import re
import os, sys

oddword = lambda fr: " ".join([
(i%2 and e[::-1] or e)
for i, e in enumerate(re.findall(r'\S+', fr))
])

print("Digite uma frase:")
sys.stdout.write("> ")
ph = sys.stdin.readline().strip()

while ph:
print(oddword(ph))

print("Digite uma frase:")
sys.stdout.write("> ")
ph = sys.stdin.readline().strip()


[/update]



Lua


Na verdade comecei fazendo em Lua.

A primeira coisa que fiz foi a função para inverter cada palavra. Comecei com um algoritmo reiterativo estilo C:
function inv(s)
local ns = ""
local i
for i = 1, #s do
ns = s:sub(i, i) .. ns
end
return ns
end


Mas esse código é pouco inteligível. Então, depois de fazer em Haskell, pensei que eu poderia implementar o algoritmo recursivo de Haskell em Lua.

Antes que alguém venha me dizer que recursividade é menos eficiente do que reiteratividade, isso é válido para algoritmos em árvore. Para recursões lineares, o algoritmo recursivo é quase tão eficiente quanto o reiterativo, só que mais claro. Aliás, pretendo escrever outro artigo sobre eficiência de algoritmos.

A função reiterativa ficou assim:
function inv(s)
if #s == 0 then
return ""
else
return inv(s:sub(2)) .. s:sub(1, 1)
end
end


A função oddword() em Lua funciona da mesma forma que em Python, mas usando corrotina.

Em Python, a função para «picotar» a string em palavras é re.findall(), em Lua é string.gmatch() (que retorna um reiterador em vez de um lista):
function oddword(phr)
local co = coroutine.wrap(function ()
local w
local odd = false
for w in phr:gmatch "%S+" do
if odd then
coroutine.yield(inv(w) .. " ")
odd = false
else
coroutine.yield(w .. " ")
odd = true
end
end
coroutine.yield "\n"
end)

return co
end


A variável odd funciona da mesma forma que em Python.

O código exemplo:
local ph
print "Digite uma frase:"
io.write "> "
ph = io.read()

while #ph > 0 do
local word
local wordproc = oddword(ph)

word = wordproc()
while word do
io.write(word)
word = wordproc()
end

print "Digite uma frase:"
io.write "> "
ph = io.read()
end


Haskell


Programação funcional é uma coisa maravilhosa. Certa vez estava conversando com o Torcato, e ele me disse que seu código melhorou muito depois que ele começou a estudar Haskell com mais seriedade. Então me toquei que o meu também.

A programação funcional força o programador a ter bons hábitos de programação, como estruturar o código em funções simples, top-down, usar reiteração de forma eficiente e memoização.

Em função disso infelizmente o código em Haskell é o mais longo. =(

O código começa com o cabeçalho padrão:
module Main where

import IO


Poderia ter feito diferente… poderia ter criado um módulo OddWord e importá-lo no programa principal. Mas preferi fazer assim para ficar mais simples.

Como há um ciclo que se repete, foi criada uma função para tanto, deixando a «main» muito pequeninha:
main = mainloop


Onde mainloop é a função que faz o ciclo. O que essa função faz? Chama outra (readString) que lê a frase. Se a frase for vazia, sai, se não, faz oddwording na frase, exibe o resultado e volta ao princípio.

Ah! Essa função não recebe nem retorna dados (IO ()).
mainloop :: IO ()
mainloop = do
ph <- readString
if ph == ""
then
return ()
else do
let nph = oddword ph
putStrLn nph
mainloop


A função para ler uma string é simples:
readString :: IO String
readString = do
putStrLn "Digite uma frase:"
putStr "> "
s <- getLine
return s


A função oddword precisa:
  1. Converter a frase para uma lista de palavras (strToList);
  2. Inverter as palavras de índice ímpar (invodd);
  3. Converter a lista de palavras de volta para uma string única (listToStr).


Há um pipe simples para concatenar as funções em Haskell: $.

Portanto, a função oddword será simplesmente:
oddword :: String -> String
oddword s = listToStr $ invodd $ strToList s


Agora precisamos definir as funções usadas.

A primeira, strToList, precisa receber uma string, percorrer ela procurando por ocorrências de espaço, retornando uma lista das strings entre os espaços:
strToList :: String -> [String]
strToList "" = []
strToList s = (take spi s) : (strToList (drop (incr spi) s))
where spi = nextspace s


Ops…! Chamamos duas funções que não existem (incr e nextspace)… então vamos precisar defini-las.

A função para retornar um valor incrementado é estupidamente simples, e há duas formas.

Uma é usando lambda:
incr :: Int -> Int
incr = \x = x + 1


A outra é usando preenchimento parcial de parâmetros ([update 2007-05-11]acho que é construção parcial ou algo assim[/update]):
incr :: Int -> Int
incr = (+ 1)


Ambos funcionam igualmente. Tanto faz usar uma ou outra.

A função para identificar o próximo espaço deve retornar zero se encontrar um espaço, se não, 1 mais o retorno da mesma função para a string começando na próxima posição:
nextspace :: String -> Int
nextspace "" = 0
nextspace (x:xs) =
if x == ' '
then
0
else
1 + (nextspace xs)


A próxima função a ser avaliada é listToStr, que é mais simples: deve apenas concatenar os elementos usando espaço como separador:
listToStr :: [String] -> String
listToStr [] = ""
listToStr (x:xs) = x ++ " " ++ (listToStr xs)


Falta apenas uma função… que na verdade vai virar três. =P

A idéia da invodd é inverter só os índices ímpares. Como o índice inicial é considerado par, ela não pode inverter o elemento, e deve chamar uma função que inverta o próximo elemento (cujo índice é ímpar).

Essa nova função (inveven) deve inverter o elemento atual e chamar invodd para o próximo elemento (par):
invodd :: Ord a => [[a]] -> [[a]]
invodd [] = []
invodd (x:xs) = x : (inveven xs)

inveven :: Ord a => [[a]] -> [[a]]
inveven [] = []
inveven (x:xs) = (inv x) : (invodd xs)


Faltou só a função de inversão! Ela é extremamente simples e funciona da mesma forma que a função de inversão em Lua (aliás, lembrando, fiz a função em Lua a partir da função em Haskell):
inv :: Ord a => [a] -> [a]
inv [] = []
inv (x:xs) = (inv xs) ++ [x]


Está feita!!! É só compilar e ver funcionando.


Terminei a brincadeira.

Ah sim! É bom citar que o Walter me disse que a brincadeira começou no Dr. Dobbs.

[]'s
Rodrigo Cacilhas

segunda-feira, 2 de abril de 2007

Instalando Haskell no Slackware

haskell Se você é usuário de Slackware e, como eu, sofreu para tentar instalar o ghc sem sucesso, aqui segue o passo-a-passo para sair da miséria!

Estes procedimentos foram testados no Slackware 11.0.

Primeiro vamos baixar o maldito RPM. Se quiser procurar por outros pacotes, veja aqui.

Baixado o monstro, vamos convertê-lo em algo mais decente com rpm2tgz:
bash$ rpm2tgz ghc66-6.6-1.i386.rpm


Agora é possível manipular este pacote. Vamos descompactá-lo:
bash$ mkdir raiz
bash$ tar xzvf ghc66-6.6-1.i386.tgz -C raiz/


Pronto! Já podemos criar uma descrição do pacote:
bash$ cd raiz/
bash$ mkdir install/
bash$ vim install/slack-desc


Eu uso o Vim, mas use o editor que lhe convier. Escreva o seguinte conteúdo:
ghc: The Glasgow Haskell Compiler v. 6.6
ghc:
ghc: GHC is a state-of-the-art, open source, compiler and interactive
ghc: environment for the functional language Haskell.
ghc:
ghc: This package was generated by rpm2tgz
ghc:
ghc: http://haskell.org/ghc/
ghc:


Salve e já temos nossa apresentação! Agora vamos criar um instalador que publique as bibliotecas no sistema e crie alguns links simbólicos amigos do peito:
bash$ vim install/doinst.sh


O conteúdo do arquivo:
#!/bin/sh

sed -i '/\/ghc/ d' /etc/ld.so.conf
echo '/usr/lib/ghc-6.6' >> /etc/ld.so.conf

( cd /usr/bin/ ; rm -rf ghc )
( cd /usr/bin/ ; ln -sf ghc-6.6 ghc )
( cd /usr/bin/ ; rm -rf ghci )
( cd /usr/bin/ ; ln -sf ghci-6.6 ghci )

ldconfig


Não é necessário, mas gosto de ter este arquivo executável:
bash$ chmod +x install/doinst.sh


O pacote RPM tem umas maluquices, como chamar o diretório de documentação de ghc66-6.6/ (versão 6.6 da versão 6.6? Redundâncias de Fedora Core…). Vamos acertar isso:
bash$ mv usr/share/doc/ghc{66,}-6.6


Para terminar vamos criar e instalar o pacote!

Para evitar possíveis dores de cabeça, vamos fazer isso como superusuário:
bash$ su -l
bash# chown -R root:root .
bash# makepkg -c y -l y ../ghc-6.6-i386-1.tgz
bash# cd ../
bash# installpkg ghc-6.6-i386-1.tgz


E pronto! Já é possível executar ghci e testar os exemplos do Torcato.

Ah! Não esqueça de guardar bem o pacote (ghc-6.6-i386-1.tgz) e limpar a sujeira (ghc66-6.6-1.i386.rpm, ghc66-6.6-1.i386.tgz e raiz/) que deixamos para trás!

[]'s
Rodrigo Cacilhas

PS: Veja este artigo também nas Reflexões de Monte Gasppa e Giulia C..

quinta-feira, 29 de março de 2007

A Linguagem Haskell: Listas - Parte 2

haskell Listas

As listas são parecidas com as tuplas mas diferente destas você pode ter quantidades variadas de elementos, em contra-partida homogêneos (de mesmo tipo). Uma lista é representada por elementos separados por vírgulas todos eles cercados por colchetes.

Prelude> [5,2]
[5,2]
Prelude> [1,2,3]
[1,2,3]
Prelude> [] -- uma lista vazia
[]


Como as listas são mutáveis, podemos com facilidade acrescentar elementos a elas. O operador para fazer isso chama-se cons, representado por dois pontos. A sintaxe para isso é mostrada nos exemplos abaixo:

Prelude> 3 : [2,2]
[3,2,2]
Prelude> 3 : []
[3]
Prelude> 1 : 6 : [7, 5]
[1,6,7,5]
Prelude> 3: [] == [3]
True
Prelude> 'c' : 'a' : 's' : 'a' : []
"casa"
Prelude> "casa" == 'c' : 'a' : 's' : 'a' : []
True

A sintaxe de [5,2] é um açucar sintático de 5 : 2 : []. Relembrando que as listas somente aceitam elementos homogêneos. Para não esquecermos, vejamos mais exemplos:

Prelude> ['c','a','s','a']
"casa"
Prelude> [ (1,1), (1,2), (1,3)]
[ (1,1), (1,2), (1,3)]
Prelude> [ [2], [7], [-1] ]
[ [2], [7], [-1] ]


Podemos concatenar listas com o operador '++'.

Prelude> [1] ++ [3,4]
[1,3,4]
Prelude> [1] ++ [3] ++ [4]
[1,3,4]
Prelude> "ca" ++ "sa" -- claro que vale para strings
"casa"


Se desejamos realizar operações aritméticas com números que são strings, usamos a função read para converter. Já quando queremos tratar um número como uma string, convertemos o mesmo com a função show. Os exemplos demonstram isso:


Prelude> read ('3' : []) + 5
8
Prelude> read "20" * read "5"
100
Prelude> tail "came' ++ show 32
"ame32"

Existem duas funções em Python que foram herdadas de Haskell, penso eu. É a map e a filter. Map toma uma função e uma lista como argumentos, e retorna uma lista do resultado da operação da função sobre cada elemento da lista-argumento. Já filter somente adiciona na nova lista os elementos que operados com a função retorne True. Exemplos são melhores que minha explicação:

Prelude> map Char.toUpper "escola"
"ESCOLA"
Prelude> filter Char.isUpper "Kodumaro"
"K"



Com isso terminamos mais um post sobre Haskell. No tutorial anterior esqueci de colocar os links para os materiais de referência. Eles podem ser encontrados no site oficial da linguagem. No entanto, minha leitura principal é Yet Another Haskell Tutorial.

Exercício: Use map para converter uma string em uma lista de booleanos, cada elemento na nova lista representando se o elemento original estava em maiúsculas ou não. Exemplo: “teSte” produzirá [False, False, True, False, False]

Prelude> :quit

quarta-feira, 21 de março de 2007

A Linguagem Haskell

haskell (Publicação original:
http://claudiotorcato.wordpress.com/2007/03/21/a-linguagem-haskell/)

O blog comunitário Kodumaro é voltado para linguagens de programação. Pensei então em escolher uma linguagem a mais para comentar. As linguagens que programei durante a minha vida foram: Pascal, C, Object Pascal, Haskell, Prolog, LISP, Java, Python, PHP e VB, nessa ordem. Talvez hajam outras mas como não lembrei foram fracamente utilizadas. Então acabei escolhendo Haskell por ser uma linguagem diferente das demais.

Haskell é uma linguagem de propósito geral, puramente funcional com características diversas tais como, tipagem estática, funções de alta ordem, polimorfismo, classes de tipo e efeitos monádicos. Existem vários compiladores disponíveis livremente para diferentes plataformas.

Poderia dizer que é uma linguagem que irá surpreendê-los, assim como ocorreu comigo no tempo da faculdade. Aos interessados em acompanhar este tutorial recomendo baixar imediatamente alguma implementação de Haskell. Sugiro duas: Hugs e GHC (Vejam nesse site). Para usuários do Windows, eu diria que seria interessante usar a primeira. Já para os geeks do Linux, por favor procurem por GHC. Puxando um pouco para meu lado de usuário Linux da distribuição Ubuntu baixem com esse comando:
sudo aptitude install haskell-compiler


Antes de chegar nos exemplos, gostaria de explicar meu modo de operação para que acompanhem com comodidade. Um jeito cômodo – inclusive primeiramente conheci estudando Haskell – é o uso de um interpretador interativo. Esta ferramenta permite que você interaja com o programa em tempo real. Ou seja, ao inserir uma expressão na linha de comando e clicar no Enter, o interpretador processa a expressão retornando seu valor. A comodidade está no fato de você testar um algoritmo como mais rapidez para integrá-lo ao fonte de uma aplicação em desenvolvimento, ou estudar o funcionamento de alguma biblioteca.

O ghci é o interpretador do GHC. Num terminal de comandos do Linux (ou usando o Hugs no Windows) executemos:
chackero@lain:~$ ghci


Haskell é um resolvedor de expressões. Ele computaciona uma expressão até deixá-la no seu modo mais simples. Assim sendo, o modo mais simples da expressão 2 + 3 é 5. O que funciona para expressões aritméticas funciona para a resolução de funções. Por isso, a explicação. Vejamos no ghci:
Prelude> 2 + 4
6
Prelude> 2 * 4
8


Haskell possui infixação de operadores. É possível colocar o símbolo dos operadores antes dos operandos. Senão, vejamos:

Prelude> (+) 2 4
6
Prelude> (*) 2 4
8
Prelude> (*) 2.0 4
8.0


Para infixação é necessário o uso dos parênteses. No exemplo, vemos polimorfismo quando o operador de multiplicação aceita inteiros e reais como argumentos. Haskell possui funções embutidas. Na verdade, os operadores são açucares sintáticos de funções. Isso é percebido pela forma como se comportam. Alguns exemplos a seguir incluem funções que tratam também de strings.
Prelude> div 10 3
3
Prelude> abs (-23) -- parênteses necessários para que -23 seja tratado como argumento
23
Prelude> negate 10
-10
Prelude> reverse "Kodumaro"
"oramudoK"
Prelude> "Kodumaro" ++ " é legal" -- exemplo de concatenação de strings
"Kodumaro é legal"
Prelude> length "Teste"
5
Prelude> 'a' < 'z' -- operação entre tipo Char
True
Prelude> True && False -- &&: operador booleano E
False
Prelude> True || False -- ||: operador booleano OU
True


Dois sinais de menos iniciam um comentário. Comentários em Haskell só existem para uma linha, não para um conjunto delas.

Funções podem ser tratadas como operadores. Isso é visto no exemplo abaixo:
Prelude> 10 `div` 3
3


Além dos números, booleanos e strings, Haskell possui outros tipos de dados, como as tuplas e as listas. São tipos muito usados na linguagem.

Tupla é uma seqüência fixa de elementos. Esses elementos podem ser de tipos diferentes. Tuplas são representadas por elementos entre parênteses:
Prelude> ("Cláudio",29)
("Cláudio", 29)
Prelude> fst ("Cláudio", 29) -- fst retorna o primeiro elemento da tupla
"Cláudio"
Prelude> snd ("Cláudio", 29, "Computação") -- snd retorna o segundo
29
Prelude> () -- Uma tupla vazia
()


Acredito que exemplos explicam melhor que palavras. Exposto isso vamos às listas, tão importantes para Haskell.

Listas são seqüências de elementos de um mesmo tipo.
Prelude> [2,3,4]
[2,3,4]
Prelude> ['c','a','s','a']
['c','a','s','a']
Prelude> length [2,3,4] -- olha o exemplo de polimorfismo!
3
Prelude> [1..4] -- uma particularidade das listas.
[1,2,3,4]
Prelude> head [1..4] -- a cabeça da lista
[1]
Prelude> tail [1..4] -- a cauda da lista
[2,3,4]
Prelude> "Kodumaro" == ['k','o','d','u','m','a','r','o'] -- Uma string é uma lista de Char!
True
Prelude> head "Kodumaro" -- então isso funciona!
"K"
Prelude> elem 'm' "Kodumaro" -- existe 'm' na string "Koduramo"?
True
Prelude> elem 5 [1..4]
False


Esse primeiro post serve para dar uma amostra do que é Haskell. Ainda veremos muitas coisas daqui em diante. Estou revisando novamente a linguagem e sei que há muitas coisas que não consegui estudar na faculdade, como as tais mônadas, conceito complicado por sinal. Espero que tenham gostado. Obrigado!

Prelude> :quit