Paul Graham e Combinatores em Haskell

Agosto 5, 2012

Paul Graham é um ensaísta, programador e investidor. É graduado em Cornell e possui doutorado por Harvard [1].

Como ensaísta, escreveu diversos artigos sendo o mais famosos deles o “A plan for spam” sobre o uso de um filtro Bayesiano para combater spam.

Como programador, Graham é conhecido por seu trabalho com Lisp, tendo escrito livros sobre esta linguagem e vem desenvolvendo um dialeto chamado Arc. Também desenvolveu a primeira aplicação web chamada Viaweb, posteriormente adquirida pela Yahoo!

Como investidor, fundou em 2005 a empresa Y Combinator que faz investimentos em start-ups. Algumas das empresas financiadas pela Y-Combinator são: Dropbox, Airbnb, reddit e Posterous.

Sobre o nome da empresa, eis uma tradução livre do FAQ deles:

Porque vocês escolheram o nome “Y Combinator?”

O combinador Y é uma das ideias mais legais em ciência da computação e é também uma metáfora para o que nós fazemos. É um programa que roda programas; é uma empresa que ajuda a abrir empresas.

Neste post gostaria de apresentar algumas notas de estudos sobre combinadores em Haskell, descrevendo os principais tipos de combinadores incluindo o tipo Y.


Combinadores em Haskell

Esse post teve origem durante os estudos do Capítulo 9 do Real World Haskell.

Em certo ponto do capítulo o autor menciona o termo de combinadores, não deixando muito claro o que são e para que servem. Fui pesquisar um pouco sobre o assunto e decidi escrever um post.

Um combinador pode ser definido como uma função lambda que não tem variáveis livres. Uma variável livre é uma variável que não foi passada como parâmetro na função lambda. Alguns exemplos de funções lambda em Haskell:

1) A função abaixo é um combinador pois a variável x está no parâmetro

\x -> x

2) No exemplo a seguir y é uma variável livre e portanto não é um combinador.

\x -> x y

3) Aqui ambos x e y foram passadas por parâmetro, então temos um combinador.

\x y -> x y

4) O exemplo abaixo não é um combinador porque f não foi passado como parâmetro

\x y -> f (x y)

5) A seguir temos uma pegadinha. Observe que o operador + é na verdade uma função que recebe dois argumentos, como no exemplo (4). Porém como o operador não foi passado como parâmetro, também não é um combinador.

\x y -> x + y 

Simplificadamente, podemos pensar em um combinador como uma função que recebe funções e retorna outra função resultado da combinação das funções de entrada.

Tipos de combinadores

Nas próximas seções, vamos apresentar alguns dos combinadores mais conhecidos. Esses combinadores têm como nome uma única letra maiúscula. Porém, no livro To Mock a Mocking Bird [2], Raymond Smullyman apelida os diferentes tipos de combinadores com nomes de pássaros. Por isso, cada seção terá o nome do combinador e entre parênteses o apelido dado por Smullyman.

Combinador I (Identity Bird ou Idiot Bird)

Este é o combinador mais simples, a identidade. É uma função que retorna o seu próprio parâmetro. Em Haskell podemos escrever:

i x = x

Essa é justamente a definição da função id da biblioteca Prelude.

Combinador K (Kestrel)

Esse é o combinador constante, ele recebe dois argumentos e ignora o segundo. Em Haskell podemos escrever:

k x y = x

Essa é justamente a definição da função const da biblioteca Prelude.

Combinador S (Starling)

O combinador S é uma função que pode ser definida da seguinte maneira em Haskell:

s x y z = x z (y z)

Podemos escrever o combinador I usando apenas os combinadores S e K como

i = s k k

A demonstração é a seguinte:

Aplicando a função (s k k) sobre um argumento x temos

(s k k) x = s k k x

Substituindo s por sua definição,

(s k k x) = k x (k x)

Agora seja f = (k x) uma função qualquer. Temos que k x f = x por definição, então

k x (k x) = k x f = x = i x

É possível mostrar que qualquer combinador pode ser escrito como função dos combinadores S e K!

Combinador B (Bluebird)

O combinador B pode ser escrito em função de S e K como

b = s (k s) k

Vamos ver a cara dessa função aplicada a alguns argumentos. Seja f1 = (k s). Usando currying vemos que essa é uma função que recebe um argumento e sempre retorna s. Aplicando b sobre um argumento x, temos

b x = s f1 k x = f1 x (k x) = s (k x)

Seja f2 = (k x). Temos que f2 é uma função que recebe um argumento qualquer e sempre retorna x. Assim, temos b x = s f2. Vamos aplicá-la sobre mais dois parâmetros y e z:

(s f2) y z = s f2 y z = f2 z (y z) = x (y z)

Ou seja

b x y z = x (y z)

O que esta função faz é a composição das funções x e y e é justamente a definição do operador (.) do Haskell.

Combinador C (Cardinal)

Esse combinador pode ser escrito em função dos combinadores K, S e B como

c = s (b b s) (k k)

Pode-se mostrar que esse combinador equivale a

c f x y = f y x

Essa é justamente a definição do operador flip do Prelude, que retorna uma função com a ordem dos parâmetros trocada.

Combinador Y (Sage Bird)

Simplificadamente o combinator Y é um combinador que transforma uma função não recursiva em uma função recursiva!

Antes de descrevê-lo, vamos analisar como faríamos isso sem o combinador Y. Para isso, vamos usar como exemplo uma função que calcula o fatorial [8]. Fazendo uso de recursão, podemos escrever:

fat = \n -> if n == 0 then 1 else n * fat (n - 1)
fat 5 -- imprime 120

A expressão lambda acima não é um combinador porque depende de fat, que não foi passado como parâmetro.

Vamos tentar passar a função por parâmetro então

fat' = \f n -> if n == 0 then 1 else n * f (n - 1)

Observe que fat’ não é uma função recursiva. Agora fazemos o seguinte:

fat = fat' fat
fat 5 -- imprime 120

Estamos definindo fat como sendo o resultado de fat' quando passamos fat como parâmetro. Parece mágica, mas em linguagens com avaliação preguiçosa isso vai funcionar. Por quê?

Vamos analisar alguns exemplos. A função fat pode ser desmembrada em

fat = 
  fat' fat = 
      \n -> if n == 0 then 1 else return n * fat (n - 1)

Para n = 0, a função retornará 1 e não se dará ao trabalho de calcular fat(-1).

Vamos agora desmembrar a função duas vezes:

fat = 
  fat' fat = 
      fat' (fat' fat) = if n == 0 then 1 else return n * 
      (if (n - 1) == 0 then 1 ele return (n-1)* fat (n - 2))

Para n = 1, é possível ver que uma avaliação preguiçosa não precisa desmembramentos do que isso.

Ok, conseguimos transformar uma função não recursiva fat' em uma função recursiva. Vamos criar uma função auxiliar para que a função fat' seja passada como parâmetro

aux f = f (aux f)
fat = aux fat'
fat 5 -- imprime 120

A função aux faz o que queremos que o combinador Y faça: recebe uma função não recursiva (por exemplo fat') e retorna uma recursiva (nesse caso fat). Entretanto, aux não é um combinador porque o aux que é chamado recursivamente é uma variável livre.

Vamos apresentar então o combinador Y. Sua definição teórica é dada por

y = \f -> (\x -> f (x x)) (\x -> f (x x))

Ainda não consegui entender essa definição de maneira clara o suficiente para arriscar uma explicação aqui. Minha sugestão é ler [8], onde Mike Vaniel deriva a função acima em Scheme.

De qualquer maneira, se formos implementá-lo em Haskell, teremos um erro de compilação devido a tipo infinito [3]. Para resolver esse problema, [4] apresenta a seguinte solução:

newtype Rec a = In { out :: Rec a -> a }

y :: (a -> a) -> a
y = \f -> (\x -> f (out x x)) (In (\x -> f (out x x)))

Para evitar problemas com tipo infinito, encapsulamos o segundo termo (\x -> f (x x)) em um novo tipo, o Rec a, através do construtor In. As funções lambda recebem x que é do tipo Rec a e por isso não podemos aplicar x sobre x diretamente. Antes devemos “desencapsular” a função contida nele usando out.

Lembrando, o newtype define uma estrutura semelhante a um tipo de dado algébrico, com a diferença que só se permite um construtor, no caso definido pelo In, e um “getter”, especificado pelo out.

Por exemplo, vamos definir um tipo chamado NovoTipo que encapsula uma função que recebe um tipo genérico e retorna esse mesmo tipo genérico, ou seja, com tipo a -> a.

newtype NovoTipo a = Construtor { getter :: a -> a }

Podemos encapsular uma função que recebe e retorna um inteiro. Por exemplo:

somaUm::Int -> Int
somaUm v = v + 1
let x = Construtor somaUm

Podemos verificar o tipo dessa variável no ghci:

> :type x
x :: NovoTipo Int

O getter extrai a função que foi encapsulada, ou seja, podemos fazer:

> (getter x) 9
10

Outros combinadores

Este site [5] tem uma lista mais extensa de combinadores. Existe um pacote do Haskell chamado data-aviary [6] contendo a implementação de diversos desses combinadores.

Reg Braithwaite discute alguns combinadores na prática usando Ruby no seu blog/projeto homoiconic [7].

Conclusão

Fiquei satisfeito em desviar um pouco da leitura do livro Real World Haskell para aprender mais sobre combinadores. Graças a isso acabei descobrindo coisas interessantes como a origem do nome da empresa do Graham e que algumas funções muito usadas em Haskell são combinadores.

Além disso, embrora o combinador Y não seja tão útil na prática, as ideias por trás dele são muito interessantes (e, na minha opinião, complicadas!).

Referências

[1] Paul Graham – Biografia
[2] How to Mock a Mocking Bird – Smullyman
[3] StackOverflow – Y Combinator in Haskell
[4] [Haskell] How to define Y combinator in Haskell
[5] Combinator Birds
[6] Hackage – The data-aviary package
[7] Github – Homoiconic
[8] Mike’s World-O-Programming – The Y Combinator
[9] Y-Combinator em Javascript


Leitura e escrita de dados em Haskell

Junho 17, 2012

Hoje vamos comentar sobre leitura e escrita de dados em Haskell. A minha principal referência é o Capítulo 7 do livro “Real World Haskell“.

Começamos com um exemplo bem simples que lê e escreve na saída padrão:

-- hello.hs
main = do
     putStrLn "Entre com seu nome:"
     inpStr <- getLine
     putStrLn ("Ola " ++ inpStr)

Para rodá-la podemos fazer :load hello.hs seguido de main no ghci ou runghc hello.hs no próprio terminal ou gerar um executável com ghc hello.hs.

Aqui já temos diversos conceitos novos. Primeiramente temos as funções de leitura e escrita, respectivamente getLine e putStrLn.

Vamos analisar a assinatura de tipos dessas funções:

putStrLn :: String -> IO ()
getLine :: IO String

Os tipos IO () e IO String representam uma ação de IO. Um jeito de interpretá-los é como sendo um invólucro (wrapper) para um tipo. Assim, IO String é um invólucro para o tipo String e IO () é um invólucro para um vazio.

Entrada e saída de dados são tarefas intrinsecamente não-puras, pois em uma chamada para leitura de dados (p.e. usando getLine) nem sempre retornará o mesmo resultado e uma escrita dos dados (p.e. usando putStrLn) possui efeitos colaterais externos.

Haskell sendo uma linguagem puramente funcional, faz uso de ações para poder lidar com tarefas não-puras. Futuramente, quando for falar sobre Mónades, pretendo explicar melhor sobre isso.

Seguindo com a interpretação do exemplo, temos o operador “<-“. Ele é uma maneira de executar uma ação, “extraindo” o seu conteúdo. Nesse caso, estamos “extraindo” a String lida com o getLine e atribuindo à variável inpStr.

Temos também o operador return, que encapsula um tipo em uma action, sendo o oposto do operador “<-” e não deve ser confundido com a palavra-chave de mesmo nome em linguagens imperativas.

O seguinte exemplo demonstra o encapsulamento de uma String em uma action, seguida da extração da mesma.

main = do
     inpStr <- return "Encapsulando e extraindo mensagem"
     putStrLn inpStr

O bloco definido pela palavra-chave do pode ser reescrito como uma sequência de operações ligadas por operadores do tipo “>>” e “>>=“. Analisando as assinaturas de tipos desses operadores temos:

(>>) :: (Monad m) => m a -> m b -> m b
(>>=) :: (Monad m) => m a -> (a -> m b) -> m b

Aqui Monad é uma typeclass. IO é uma instância de Monad. O operador “>>” serve para conectar duas ações, descartando o resultado da primeira e retornando a segunda.

main = 
     putStr "Ola" >> putStrLn " Mundo"

O operador “>>=” executa uma ação e alimenta uma função com o valor retornado. Essa função gera uma nova ação. Um exemplo:

main = 
     getLine >>= (\x -> putStrLn $ "Ola " ++ x)

Assim, o exemplo do início do post poderia ser reescrito sem o uso da palavra-chave do:

main =
     putStrLn "Entre com seu nome:" >> 
       getLine >>= 
         (\inpStr -> putStrLn $ "Ola " ++ inpStr)

Manipulação de arquivos de texto

A leitura e escrita de arquivos de texto em Haskell é bastante parecida com a de linguagens imperativas. Temos a função openFile

openFile :: FilePath -> IOMode -> IO Handle

que recebe o caminho do arquivo (uma string) e um modo de acesso (leitura, escrita, etc.)), e retorna um manipulador (handler) do arquivo (encapsulado em uma ação de IO).

Temos também as funções hGetLine que lê uma linha do manipulador, hPutStrLn que escreve uma linha no manipulador e hIsEOF que decide se o manipulador atingiu o final do arquivo.

import System.IO
import Data.Char(toUpper)

main :: IO()
main = do
     inh <- openFile "entrada.txt" ReadMode
     outh <- openFile "saida.txt" WriteMode     
     mainloop inh outh
     hClose inh
     hClose outh

mainloop inh outh = 
         do ineof <- hIsEOF inh
            if ineof
               then return()
               else do inpStr <- hGetLine inh
                       hPutStrLn outh (map toUpper inpStr)
                       mainloop inh outh

Temos os manipuladores para a entrada padrão, a saída padrão e a saída de erro. Desta forma poríamos usar as seguintes definições:

getLine = hGetLine stdin
putStrLn = hPutStrLn stdout
print = hPrint stdout

hGetContents

Ao invés de definir a função mainloop como no exemplo acima, podemos usar a função hGetContents

hGetContents :: Handle -> IO String

import System.IO
import Data.Char(toUpper)

main :: IO ()
main = do 
       inh <- openFile "entrada.txt" ReadMode
       outh <- openFile "saida.txt" WriteMode
       inpStr <- hGetContents inh
       hPutStr outh (map toUpper inpStr)
       hClose inh
       hClose outh

Como Haskell é uma linguagem com avaliação preguiçosa (lazy evaluation), no exemplo acima a função hGetContents não carregará todo o arquivo em memória, mas fará a leitura e escrita em partes.

readFile, writeFile e interact

As funções readFile e writeFile simplificam a leitura e escrita em arquivos de texto para casos como o do nosso exemplo, abstraindo o uso direto dos manipuladores:

readFile :: FilePath -> IO String
writeFile :: FilePath -> String -> IO ()

A nova versão fica bastante concisa:

import System.IO
import Data.Char(toUpper)

main :: IO ()
main = do 
       inpStr <- readFile "entrada.txt"
       writeFile "saida.txt" (map toUpper inpStr)

No caso particular de estarmos trabalhando com a entrada e saída padrão, podemos usar a função interact. Ela lê uma String da entrada padrão, processa com a função passada como parâmetro e retorna a String processada.

interact :: (String -> String) -> IO ()

Nesse caso nosso código se reduziria a uma linha!

import Data.Char(toUpper)

main :: IO ()
main =
       interact (map toUpper)

Buffering

Se rodarmos o código acima no ghci, ao mesmo tempo em que digitamos os caracteres eles passam a ser impressos no terminal. Há três tipos de buffers NoBuffering, LineBuffering e BlockBuffering. O modo padrão no ghci é o NoBuffering. Podemos mudar o modo padrão através da função hSetBuffering,

main :: IO ()
main = do
       hSetBuffering stdin LineBuffering
       interact (map toUpper)

Um efeito colateral indesejável é que depois que executarmos o main, os próximos comandos digitados no ghci só aparecerão depois de apertarmos o Enter :P

Parâmetros via linha de comando

Para obter os parâmetros passados como parâmetro via linha de comando, podemos usar a função getArgs presente em System.Environment

getArgs :: IO [String]

Ele retorna uma action contendo uma lista de strings correspondente aos parâmetros.

import System.IO
import System.Environment

main = do
     list <- getArgs
     putStrLn(show(list))

Praticando com problemas de programação

Agora que já aprendi o básico de leitura da entrada e saída padrão, vou começar a praticar no SPOJ-Br com os problemas da OBI. Até agora eu vinha usando o project Euler pois lá só precisa submeter a solução, não importando o modo como se faz a leitura/escrita dos dados.

Outra maneira de praticar é com a lista de 99 problemas de Haskell, mas esse eu ainda não tentei.

Minha sugestão de problemas para serem resolvidos no SPOJ-Br são Quadrados, Soma, Fatorial, Primo. Alguns com lógica bem simples também, mas um pouco mais chato de processar a entrada são Pneu, Fliperama, Garçom, Tacógrafo e Sedex.

Spoiler!

No problema Quadrados dá fazer uma solução bem compacta usando conceitos discutidos anteriormente como IO, funções lambda, currying e composição de função:

main = interact ((++ "\n") . show . (\x -> x*x) . read)

Referências

[1] Real World Haskell – Capítulo 7
[2] Haskell.org – Introduction to IO


Equações de Pell

Fevereiro 12, 2012

Equações diofantinas são equações polinomiais que só admitem soluções inteiras. Neste post, vou comentar sobre três casos particulares e me concentrar em um deles, conhecido como equações de Pell.

Triplas de Pitágoras

O caso mais conhecido de equações diofantinas é da forma:

x^2 + y^2 = z^2

As soluções inteiras para essa equação são conhecidas como triplas pitagóricas, por causa do teorema de Pitágoras, sobre a relação entre os comprimentos dos lados de um triângulo retângulo.

Para o caso mais geral, da forma x^n + y^n = z^n com n > 2, o famoso último teorema de Fermat diz que não existem soluções inteiras.

Indentidade de Bézout

Outro caso particular conhecido são as equações diofantinas lineares de duas variáveis, por exemplo, x e y, da forma

ax + by = c

Onde a, b, c são constantes inteiras. No caso em que c é o máximo divisor comum de a, b, temos a identidade de Bézout. É possível encontrar um par x, y inteiro usando o algoritmo de Euclides estendido.

Note entretanto que há infinitas soluções inteiras para essa equação, pois se x, y é uma solução, x' = x + b e y' = y - a é também uma solução.

Equação de Pell

Só recentemente ouvi falar sobre um outro caso particular, conhecido como equações de Pell, com a forma:

(1) x^2 - ny^2 = 1

Onde n é um inteiro positivo. Se n não possui raíz exata, então existem infinitas soluções inteiras x, y (Se n tiver raíz exata dá pra mostrar que a única solução é x = \pm 1 e y = 0). Vamos apresentar um algoritmo para encontrar as soluções para esse caso particular de n.

Frações continuadas

Um conceito usado no algoritmo é o de frações continuadas, que podem ser usadas para aproximar um número irracional através de frações. A fração continuada possui a seguinte forma:

Dado um número d, os coeficientes de sua fração continuada, a_0, a_1, \cdots, a_n são positivos e podem ser calculados através das recorrências, para i \ge 1:

r_i = \frac{1}{r_{i-1} - a_{i-1}}

a_i = \lfloor r_i \rfloor

e com a_0 = \lfloor d \rfloor.

Podemos representar uma fração continuada por seus coeficientes, ou seja, [a_0,a_1,a_2,\cdots]. Incrivelmente, no caso particular em que o número irracional é da forma \sqrt{n}, prova-se que os coeficientes da sua fração continuada são periódicos, ou seja \sqrt{n} = [a_0, \overline{a_1,a_2,\cdots,a_{r-1},a_{r}}] e a_{r} = 2a_0.

Como um exemplo, para n = 14 temos \sqrt{14} = [3,\overline{1,2,1,6}]

É possível calcular explicitamente o numerador p_i e o denominador q_i da fração continuada com i termos, através das recorrências:

\begin{array}{lcl}   p_0 & = & a_0\\  p_1 & = & a_1 a_0 + 1\\  p_n & = & a_n p_{n-1} + p_{n-2}   \end{array}

e

\begin{array}{lcl}   q_0 & = & 1\\  q_1 & = & a_1\\  q_n & = & a_n q_{n-1} + q_{n-2}   \end{array}

A fração p_i / q_i é chamada de n-ésimo convergente. Voltando ao exemplo para n = 14, temos:

\begin{array}{llcl}   i: & p_i / q_i  &  & \\  0:  & 3/1 & = & 3.0\\  1: & 4/1 & = & 4.0\\  2: & 11/3 & = & 3.66666666667\\   3: & 15/4 & = & 3.75\\  4: & 101/27 & = & 3.74074074074  \end{array}

Sendo que \sqrt{14} é aproximadamente 3.74165769645

Uma solução para a equação de Pell

Considere os coeficientes da fração continuada de \sqrt{n} e r o índice a partir do qual os coeficientes ficam periódicos.

Se r é par, seja x = p_{r-1} e y = q_{r-1}. Caso contrário, seja x = p_{2r-1} e y = q_{2r-1}. Surpreendentemente, existe um teorema que diz que x, y representam a menor solução inteira positiva para (1).

Algoritmo

Dadas essas propriedades, um algoritmo para encontrar uma solução para (1), consiste em iterar sobre os coeficientes p_i e q_i, até encontrar r tal que a_r = 2a_0. Segundo Lenstra [2], r \in O(\sqrt{n} \log n), ou seja, tem complexidade pseudo-polinomial. Assim, se d é o número de bits necessários para representar n, temos que r \in O(2^{d/2}d), ou seja, mesmo ignorando as complexidades das operações artiméticas no código, o nosso algoritmo é exponencial no número de bits.

Gerando mais soluções

Dada uma solução fundamental (x_1,y_1), Lenstra [2] afirma que se ordenarmos as soluções por magnitude, então a k-ésima solução (x_k, y_k) é tal que

(2) x_k + \sqrt{n}y_k = (x_1 + \sqrt{n}y_1)^k

Usando a ideia de [1], como ambos (x_1,y_1) e (x_k, y_k) são solução para (1), temos

x_k^2 - ny_k^2 = (x_1^2 - ny_1^2)^k = 1

Fatorando temos,

(x_k + \sqrt{n}y_k)(x_k - \sqrt{n}y_k) = (x_1 + \sqrt{n}y_1)^k(x_1 - \sqrt{n}y_1)^k

Por (2), concluímos que,

(3) x_k - \sqrt{n}y_k = (x_1 - \sqrt{n}y_1)^k

Resolvendo para (2) e (3), chegamos em:

\begin{array}{lcl}   x_k & = & \dfrac{(x_1 + y_1\sqrt{n})^k + (x_1 - y_1\sqrt{n})^k}{2}\\  \\  y_k & = & \dfrac{(x_1 + y_1\sqrt{n})^k - (x_1 - y_1\sqrt{n})^k}{2\sqrt{n}}  \end{array}

Implementação

Com base na teoria apresentada acima, é simples escrever um algoritmo. Adicionei uma implementação em python à minha biblioteca pessoal de teoria dos números, disponível no github.

Encontrei um post bastante interessante sobre equações de Pell e Haskell aqui [3]. Para praticar, resolvi implementar a minha versão antes de olhar o código do post. Apanhei bastante para lidar com o fato do Haskell não fazer conversão de tipos ponto flutuante e inteiro automaticamente. É preciso fazer isso explicitamente e por isso a função fromIntegral no código deste link.

Leitura complementar

[1] Wolfram – Pell Equation
[2] Solving the Pell Equation – H. W. Lenstra Jr.
[3] A Foray into Number Theory with Haskell


Haskell – Typeclass

Dezembro 4, 2011

Neste post vou comentar sobre a estrutura typeclass do Haskell. A minha principal referência é o capítulo 6 do Real World Haskell.

Typeclasses

Como em Haskell existem tipos parametrizados, podemos querer definir funções que aceitam parâmetros com esse tipo. Entretanto, provavelmente a implementação da função será diferente para cada tipo.

Assim, typeclass é uma estrutura para prover essa funcionalidade. A sintaxe básica é a seguinte:

class <Nome> <Tipos parametrizados> where
    <função 1> :: <Assinatura de tipos>
    <função 2> :: <Assinatura de tipos>

Apesar do nome, um typeclass é bem diferente de uma classe que estamos acostumados em linguagens orientadas à objetos.

Um caso onde typeclass é útil é na implementação do operador de igualdade. Suponha que temos dois tipos Booleano e CorRGB:

data CorRGB = Vermelho | Verde | Azul
     deriving (Show)

data Booleano = Falso | Verdadeiro
     deriving (Show)

Podemos definir uma typeclass contendo uma função de igualdade, que recebe dois parâmetros de um mesmo tipo parametrizado a, e retorna True se forem iguais ou False caso contrário.

class Compara a where
      igual :: a -> a -> Bool

Aí podemos definir uma implementação para cada tipo, usando uma estrutura chamada instance. A sintaxe é semelhante ao typeclass, mas agora especificamos os tipos parametrizados e definimos a implementação da função. Para o caso do Booleano e da CorRGB, temos:

instance Compara Boolean where
         igual Verdadeiro Verdadeiro = True
         igual Falso Falso = True
         igual _ _  = False

instance Compara RGBColor where
         igual Vermelho Vermelho = True
         igual Verde Verde = True
         igual Azul Azul = True
         igual _ _ = False

Também podemos prover implementações padrões para um typeclass, definindo a implementação na estrutura class. Na execução, a implementação utilizada é sempre a mais específica.

Complementando o exemplo da typeclass Compara, podemos definir a função diferente e definir implementações padrões para ela e também para a função igual:

class Compara a where
      igual :: a -> a -> Bool
      igual x y =  not (diferente x y)

      diferente :: a -> a -> Bool
      diferente x y = not (igual x y)

Derivação automática

Na definição de Booleano e CorRGB, usamos a diretiva deriving(Show). Essencialmente Show é um typeclass da biblioteca padrão. A função show desse typeclass transforma um tipo genérico em String.

Fazendo alguns testes no terminal (ghci):

> show(Vermelho)
"Vermelho"
> :type show
show :: Show a => a -> String

Note que o comando :type usa uma sintaxe diferente para dizer que a função show pertence ao typeclass Show.

Podemos escrever nossa própria implementação para CorRGB ao invés de usar o padrão. Para isso, removemos a declaração deriving(Show) e adicionamos:

instance Show CorRGB where
         show Vermelho = "Red"
         show _ = "Not implemented"

Segundo [2], a funcionalidade do derive só pode ser usada com um conjunto específico de built-in typeclasses.

Typeclass com lista de tipos paramétricos

Imagine que queiramos implementar a função igual para uma lista de Booleanos. A primeira tentativa seria:

instance Compara [Boolean] where
         igual = undefined

No código acima, undefined é um tipo coringa que não causa erros de compilação devido a incompatibilidade de tipos, mas que causa um erro em tempo de execução. Essa técnica de usar undefined‘s é interessante para ir compilando versões intermediárias do seu código mesmo sem ter a implementação de todas as funções.

Enfim, veremos que tal trecho de código leva ao seguinte erro de compilação:

   Illegal instance declaration for `Compara [Boolean]'
      (All instance types must be of the form (T a1 ... an)
       where a1 ... an are *distinct type variables*,
       and each type variable appears at most once in the instance head.
       Use -XFlexibleInstances if you want to disable this.)
    In the instance declaration for `Compara [Boolean]'
Failed, modules loaded: none.

Há diversas maneiras de se contornar esse erro. Um deles é definir uma função exclusiva para listas, no caso da função igual, podemos criar uma igualLista,

class Compara a where
  ...
  igualLista :: [a] -> [a] -> Bool
  igualLista (xa:a) (xb:b) | diferente xa xb = False
                           | otherwise = igualLista a b
  igualLista [ ] [ ] = True
  igualLista _ _ = False
  ...

A vantagem nesse caso é que a implementação padrão deverá servir para a maior parte dos casos, pois em geral o teste de igualdade entre duas listas consiste em verificar se todos os elementos em ambas são iguais.

No caso de você querer definir a implementação apenas para uma lista de um tipo particular (p. e. [Booleano]), pode-se encapsular essa lista em uma estrutura chamada newtype.

O newtype é parecido com um tipo de dado algébrico (keyword data), com algumas diferenças como por exemplo o newtype exigir exatamente um data constructor e o tipo de um newtype é resolvido em tempo de compilação, ao contrário do data, e por isso seu uso não ocasiona overhead na execução do programa [1].

Assim, poderíamos fazer:

newtype Wrapper = Wrapper [Booleano]

Agora podemos implementar a função, com o inconveniente de encapsular os dados do novo tipo com Wrapper:

instance Compara Wrapper where
  igual (Wrapper x) (Wrapper y) = igualAux x y
    where igualAux (xa:a) (xb:b) | diferente xa xb = False
                                 | otherwise = igualAux a b
          igualAux [ ] [ ] = True
          igualAux _ _ = False

Uma boa referência para essas e outras alternativas é o haskell wiki [3].

Conclusão

Achei esse assunto bem complicado! Pra piorar, parece que o livro Real World Haskell no qual estou me baseando, escreveu muito mal os capítulos 5 e 6, dando exemplos muito complexos (talvez seja a diretriz do “real world”, mas definitivamente isso não é didático), confusos e chatos. Há diversos comentários que compartilham dessa opinião.

Apesar de tudo, continuarei meus estudos com esse livro, mesmo que eu só use os tópicos para me guiar e procurar explicações em referências como [2] e [3].

Referências

[1] http://book.realworldhaskell.org/read/using-typeclasses.html
[2] http://en.wikibooks.org/wiki/Haskell/Class_declarations
[3] http://www.haskell.org/haskellwiki/List_instance


Currying de funções em Haskell

Novembro 6, 2011

Currying de função é uma técnica de avaliação parcial dos argumentos de uma função. O nome da técnica é em homenagem a Haskell Curry, que segundo a Wikipedia re-inventou o método (Moses Schönfinkel já havia desenvolvido o método anteriormente). O curioso é que esse matemático também deu nome à linguagem Haskell.

Nesse post vou falar um pouco sobre currying de funções em Haskell, baseando-me principalmente no capítulo 4 do livro “Real World Haskell“.

Funções com múltiplos argumentos em Haskell

A sintaxe para especificarmos o tipo de uma função em Haskell com múltiplos argumentos parece meio confusa no começo. Por exemplo, se quisermos definir uma função que soma dois inteiros, devemos especificá-la da seguinte forma.

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

A partir do cabeçalho não dá a impressão de que a função recebe dois inteiros como argumento e retorna um inteiro. Isso porque as funções em Haskell recebem na verdade apenas um argumento. Quando há múltiplos argumentos, chamamos a função ‘f’ com o primeiro argumento e retornamos uma função ‘g’ com as ocorrências desse primeiro argumento substituídas pelo valor passado como argumento.

Por exemplo, considere uma função f(a, b, c) sobre três inteiros a, b e c. A primeira chamada da função f(1,2,3) retorna uma nova função g(b, c) = f(1, b, c), que por sua vez retorna uma outra função h(c) = g(2, c), que recebe apenas um argumento.

Para testar isso na prática, podemos fazer no terminal (ghci):

> :type soma
soma :: Int -> Int -> Int
> let somaTres = soma 3
> :type somaTres
soma3 :: Int -> Int
> somaTres 7
10 

No exemplo acima, o parâmetro a de soma, foi substituído por 3 e a função resultante atribuída a somaTres, que agora só recebe um argumento.

Em uma função com vários parâmetros, podemos trabalhar com versões intermediárias do processo de currying provendo apenas alguns dos parâmetros. Por exemplo,

-- Função que retorna uma tripla a partir de 3 argumentos
foo a b c = (a, b, c)
foo1 = foo 3
foo2 = foo 4 5
foo3 = foo 6 7 8

Nesse caso, foo1 recebe dois argumentos, foo2 apenas um e foo3 já é o resultado da função foo.

Omissão de parâmetros usando currying

Suponha que queiramos selecionar os números primos de uma lista de entrada. Uma versão bem simples, onde tentamos encontrar um divisor de p indo de 2 até \sqrt{p}, pode ser dada por:

ehPrimo p | p < 2 = False
          | otherwise = ehPrimoAux p 2 
                      
ehPrimoAux p q | q*q > p        = True
               | p `mod` q == 0 = False 
               | otherwise      = ehPrimoAux p (q+1)

Na biblioteca padrão do Haskell, existe a função filter, que recebe um array e uma função que recebe um elemento desse array e retorna verdadeiro ou falso. Podemos passar nossa função ehPrimo para gerar uma lista com os elementos primos de 1 a 50 por exemplo.

> :type filter
filter :: (a -> Bool) -> [a] -> [a]
> filter ehPrimo [1..50]
[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47]

Para facilitar, podemos criar uma função que recebe um array e retorna a lista de primos:

listaPrimos xs = filter ehPrimo xs

Utilizando currying, é possível definir a função acima sem o parâmetro

listaPrimos = filter ehPrimo

No primeiro caso, estamos definindo uma função que chama filter ehPrimo xs. No segundo, estamos apenas associando o resultado da avaliação parcial da função filter com seu primeiro argumento, no caso o ehPrimo.

Currying sobre o segundo parâmetro

Por padrão, a substituição dos argumentos é feita a partir do primeiro argumento, ou seja, da esquerda para a direita. Entretanto, para funções com dois parâmetros (binárias), podemos usar a notação infixa para fazer a substituição do segundo argumento.

A notação infixa consiste em chamar a função entre acentos graves (backtick). Por exemplo, a função soma poderia ser chamada assim:

> 1 `soma` 2
3

Essa sintaxe é interessante para fins de legibilidade de código. Ao chamar a função na forma infixa passando somente o segundo argumento, a substituição é feita somente para ele. Como um exemplo, vamos definir a função potência que recebe dois inteiros a e b e eleva a a b (a função soma não tem graça porque ela é comutativa).

> let potencia a b = a ^ b

Agora, podemos fazer currying e aplicar a função a um argumento apenas

-- Faz a substituição do parâmetro b
> let quadrado = (`potencia` 2)
> quadrado 9
81

Currying em C++

A STL do C++ provê algumas ferramentas para trabalhar com o paradigma funcional, através da biblioteca functional. Através dela podemos reproduzir o nosso primeiro exemplo em Haskell:

#include <functional>
#include <iostream>
using namespace std;

struct adder : public binary_function<int, int, int> {
    int operator() (int a, int b) const {
        return a + b;
    }
};
// currying sobre o primeiro argumento da funcao 
int main (){

    adder soma;
    binder1st<adder> somaTres = bind1st(soma, 3);  
    cout << somaTres(7) << endl; // 10
    cout << somaTres(-1) << endl; // 2
}

Nesse caso trabalhamos com um functor, que é um objeto representando uma função. A classe adder deve derivar da classe binary_function. A função bind1st faz um bind do primeiro argumento da função, e retorna um objeto do tipo binder1st, que deriva da classe unary_function e que recebe um argumento.

É possível fazer o bind do segundo argumento através da função bind2nd.


Haskell – Tipos de Dados Algébricos

Setembro 25, 2011

Haskell usa uma sintaxe elegante para representar um tipo de estrutura de dados, análoga a diversas outras estruturas presentes em linguagens como C e C++. Essas estruturas são chamadas tipos de dados algébricos. Minha principal referência para esse post foi o capítulo 3, do livro Real World Haskell.

Este é o segundo post sobre meus estudos em Haskell. O primeiro se encontra aqui.

Struct

Considere a seguinte struct em C++ representando um livro através de seu código, título e autores:

#include <string>
#include <vector>
struct {
    int isbn;
    std::string title;
    std::vector < std::string > authors;
};

Em haskell podemos escrever:

data BookInfo = Book Int String [String]
                deriving (Show)

Para definir essa estrutura, deve-se iniciar com a keyword data e dar um nome para esse novo tipo, no caso BookInfo (chamado de type constructor). Além disso, definimos um construtor desse tipo, que no exemplo tem o nome Book (chamado de value constructor ou data constructor), mas poderia ter o mesmo nome do tipo. Tanto o nome do construtor quanto o nome do tipo devem ser iniciados por letra maiúscula.

A linha deriving (Show) está sendo usada nesse e nos outros exemplos deste post para que uma instância desse estrutura possa ser impressa no terminal. Podemos instanciar a estrutura BookInfo da seguinte forma:

myBook = Book 9780135072455 "Algebra of Programming"
         ["Richard Bird", "Oege de Moor"]

Note que os parâmetros de entrada devem estar na mesma ordem em que eles são definidos na estrutura.

Note também que os “membros” dessa estrutura são anônimos, sendo representados apenas por seu tipo. Para contornar a possível perda de legibilidade, é possível usar sinônimos de tipos, através da keyword type (parecido com o typedef de C++).

type ISBN = Int
type Title = String
type Author = String

data BookInfo = Book ISBN Title [Author]
                deriving (Show)

Enum

Outra estrutura em C++ que pode ser representada sucintamente em Haskell é o enum. Considere um enum representando as cores RGB:

enum Color { Red, Green, Blue };

Um tipo de dado algébrico admite mais de um construtor, desde que tenham nomes diferentes. Além disso, os construtores não precisam ter parâmetros, o que permite escrever o enum acima da seguinte forma:

data Color = Red | Green | Blue
             deriving (Show)

Union

Ainda aproveitando que podemos ter vários construtores com diferentes parâmetros, podemos também representar uma union. Considere o seguinte exemplo em C++ de uma union podendo representar duas formas geométricas – um círculo ou um polígono:

struct Point {
    double x, y;
};
struct Circle {
    Point center;
    double radius;
};
struct Polygon {
    int nvertices;
    Point *vertices;
};
union Shape {
    Circle circle;
    Polygon polygon;
};

Em Haskell, é possível fazer o seguinte:

type Point = (Double, Double)
type Center = Point
type Radius = Double

data Shape = Circle Center Radius
           | Polygon [ Point ]
             deriving (Show)

Curiosidade: Na especificação atual do C++ (2003), membros de uma union não podem ter construtores não-triviais. Parece porém, que na nova especificação (C++11) será possível. Portanto, o exemplo abaixo não compila com gcc-4.2.1:

#include <utility>
#include <vector>

typedef std::pair <double, double> Point;
typedef std::vector<Point> Polygon;

struct Circle {
    Point center;
    double radius;
};

union Shape {
    Circle circle;
    Polygon polygon;
};

Getters e Setters

Quando trabalhamos com classes, eventualmente queremos proteger o acesso de leitura/escrita a seus membros usando getters e setters, como por exemplo:

#include <string>
class Person {
    int id;
    std::string name;

public:

    int get_id(){ return id; }
    void set_id(int _id){ id = _id; };
    std::string get_name(){ return name; }
    void set_name(std::string &_name) { name = _name; }
};

Há um mecanismo parecido em Haskell, implementado pelo chamado record syntax. Num exemplo análogo ao anterior:

type ID = Int
type Name = String

data Person = Person {
      personID      :: ID,
      personName    :: Name
      } deriving (Show)

Essa sintaxe mais verbosa permite instanciar a estrutura atribuindo os parâmetros aos membros explicitamente como:

you = Person {personName = "YourName", personID = 2}

O getter de um membro é dado por:

personName you

Enquanto o setter seria:

you {personID 3}

Tipos Parametrizados

Tipos de dados algébricos representam ainda outra funcionalidade presente em C++: templates. Tomemos como exemplo uma classe representando um ponteiro genérico para qualquer tipo:

template <typename T>
struct GenericPointer {
    T* ptr;
};

Ao instanciar essa classe podemos definir os tipos que queremos representar:

int i = 2;
GenericPointer<int> p1;
p1.ptr = &i;
GenericPointer<double> p2;
p2.ptr = NULL;

Aqui temos ponteiros para os tipos int e double, sendo que o NULL é um valor genérico para dizer que o ponteiro não aponta pra lugar algum.

Uma analogia (forçada) em Haskell seria a seguinte:

data GenericPointer a = Ptr a |
                        Null
                        deriving(Show)

Embora em Haskell não tenhamos o valor NULL, podemos simulá-lo através de um construtor como no exemplo acima. Esse encapsulamento é particularmente interessante para prover uma condição de exceção. Por exemplo, considere uma função que retorna o primeiro elemento de uma lista:

first_elem (x:xs) = x

O que retornar caso a lista seja vazia? Uma solução seria usar o encapsulamento:

first_elem (x:xs) = Ptr x
first_elem _      = Null

No exemplo, o caractere '_' funciona como um coringa, ou seja, qualquer parâmetro casa com ele. Como foi posto depois do outro padrão, ele se comporta como um “else” e só será chamado quando a lista não tiver elementos.

Tipos Recursivos

Outra possibilidade de um tipo de dado algébrico é usar tipos recursivos, isto é, membros da estrutura são do tipo dessa estrutura. Em C e C++ é possível fazer isso utilizando ponteiros. Por exemplo, podemos implementar uma lista ligada de elementos genéricos da seguinte maneira:

template <typename T>
struct LinkedList {
    LinkedList<T>* next;
};

Em Haskell temos algo como:

data LinkedList a = Node a (LinkedList a)
            | Null 
            deriving(Show)

Para representar uma lista ligada contendo 3, 1 e 2, nessa ordem, usamos a seguinte sintaxe:

Node 3 (Node 1 (Node 2 Nil))

Um árvore binária também é bem simples de se representar:

data Tree a = Node a (Tree a) (Tree a)
            | Null
              deriving (Show)

Conclusão

Haskell tem uma sintaxe sucinta para descrever tipos de dados algébricos, que por sua vez são bastante versáteis, podendo representar tanto estruturas quanto uniões, enumerações, classes, etc.

Ainda sei muito pouco sobre a linguagem, mas por enquanto estou achando-a bastante interessante.


Haskell

Agosto 7, 2011

Faz algum tempo que eu vinha querendo aprender Haskell, que é uma linguagem funcional. A motivação começou com uma série de posts que andei lendo sobre C++ que faziam referência a conceitos de Haskell e dos quais eu não entendi quase nada.

Também queria relembrar alguns conceitos de linguagens funcionais, que aprendi quando vi Lisp na faculdade, mas que acabei esquecendo.


Estou estudando o livro Real World Haskell, disponível gratuitamente na internet. Achei legal o esquema deles de prover espaço para comentários em cada parágrafo do livro. Assim, os leitores atuam como revisores, sugerindo exemplos mais explicativos ou corrigindo erros de digitação.

Sendo o primeiro de uma série de anotações de meus estudos dessa linguagem, este post será como uma introdução. Nos posts seguintes pretendo discutir sobre os aspectos mais importantes da linguagem.

Antes de mais nada, é preciso instalar o interpretador de Haskell. Estou usando o ghci para rodar os programas abaixo. Para tal, deve-se executar ghci no terminal e carregar os códigos-fontes com :load <nome do arquivo>. Os códigos de exemplo podem ser salvos com a extensão .hs.

Hello World!

O fatorial é um dos primeiros problemas que vemos ao aprender recursão. Como linguagens funcionais fazem bastante uso de recursão, vamos começar com esse exemplo ao invés do famoso “Hello World!”.

-- Função que calcula o fatorial
fact n = if n == 0 
      then 1
      else n * fact (n-1)

(o wordpress não tem syntax highlight pra Haskell :( coloquei o de sql pois o jeito de comentar é o mesmo)

Aqui já aprendemos um pouco da sintaxe de uma função: o nome da função, fact (nomes de variáveis e funções devem obrigatoriamente começar com letra minúscula), o parâmetro ‘n’ logo em seguida (não é necessário colocar parênteses englobando os parâmetros e os parâmetros são separados por espaços, não por vírgulas).

Depois do sinal de igual, está definido o corpo da função, que no caso é um if. Além disso, funções em Haskell devem ser apenas uma única expressão (a presença do if dá a impressão de que há duas, mas na prática apenas uma delas será executada).

O valor retornado é o resultado da expressão executada. Além disso, o tipo retornado pelas expressões deve ser o mesmo e por isso todo if deve ser acompanhado else.

Um outro modo de escrever a função fatorial é através do seguinte código:

-- Usando casamento de padroes
fact 0 = 1
fact n = n * fact (n-1)

Aqui vemos o conceito de casamento de padrões. Lembra um pouco polimorfismo, mas aqui é um pouco diferente pois você pode definir uma constante como parâmetro. Ao chamar a função fact com o código abaixo,

fact 5

Ela vai casando com as funções até que uma bata todos os parâmetros. Assim, fact 5 só casa com fact n, pois 5 != 0. Essa função faz recursão com valores de n até que fact 0 é chamado. A ordem em que as funções estão definidas é importante, porque o casamento é feito de cima pra baixo. Note que fact 0 casa tanto com fact 0 quanto fact n e se casássemos com essa última, teriámos um loop infinito.

E se chamarmos a função com um valor real?

fact 5.1

Ela funciona, mas obviamente subtraindo 1 nunca teremos o valor 0 exato, resultando em loop infinito. Note que na definição da função não definimos tipo. Entretanto, as variáveis em Haskell têm tipo sim. A diferença é que ela faz inferência de tipos a partir dos valores quando estes não estão definidos.

Podemos restringir os tipos aceitos por uma função para que ninguém chame-a indevidamente. Para isso, podemos usar a assinatura de tipos, conforme o código abaixo:

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

A primeira linha define que a entrada, bem como a saída sejam do tipo Int. Agora vamos calcular fatorial de 30:

> fact 30
-8764578968847253504

Deu overflow. Felizmente, Haskell tem uma implementação nativa de inteiros de precisão arbitrária (big integer), que é o tipo Integer. Podemos forçar nossa função de fatorial a usar esse tipo se formos calcular fatoriais bem grandes:

fact :: Integer -> Integer 
fact 0 = 1
fact n = n * fact (n-1)

Descobri por um acaso um modo bem mais simples de computar fatorial:

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

Aqui temos o conceito de listas, que são encapsuladas por colchetes, têm tamanho variável e todos os seus elementos devem ser do mesmo tipo. A sintaxe [x..y] gera uma lista com números entre x e y (inclusive) contando de 1 em 1 (y pode ser menor do que x, caso em que ele conta de trás pra frente). É possível definir um “passo” definindo o segundo elemento da sequência. Assim, [x,y..z] vai gerar de x a z, com passo (y-x). Exemplos:

[1..10] = [1,2,3,4,5,6,7,8,9,10]
[7..2]  = [7,6,5,4,3,2]
[1,4..15] = [1,4,7,10,13]