Efeitos Colaterais em Haskell

Ser puro ou impuro? Eis a questão!

Atualmente a comunidade de pesquisa em linguagens funcionais debate incessantemente sobre o tema de qual a melhor maneira de manipular efeitos (estado, I/O, logging, continuações, …) .  Existem duas correntes principais:

  • Linguagens funcionais “puras”, como Haskell, que são baseadas na noção matemática de que uma função consiste no simples mapeamento de seus argumentos em seus respectivos resultados.
  • Linguagens funcionais impuras, como ML, que estendem esta noção com “efeitos” como atribuições, exceções, etc.

Linguagens puras são mais simples, por permitirem que raciocínio algébrico padrão da matemática seja utilizado em seus programas sem maiores problemas (o que facilita a prova de corretude de programas) . Além disso, essas linguagens permitem a utilização de avaliação sobre demanda. Porém linguagens impuras tendem a ser mais eficientes.

Diante de tal impasse, na década de 90 iniciaram-se diversas pesquisas visando integrar as abordagens puras e impuras, utilizando o conceito matemático de mônadas. Neste post, irei apresentar como mônadas podem ser utilizadas para permitir o desenvolvimento de programas effect-ivos (programas com efeitos) em Haskell.

Reutilizando padrões de computação

Mônadas são um exemplo de uma idéia recorrente em computação de reutilizar padrões de programas. Antes de considerarmos mônadas, vamos rever como podemos reutilizar padrões de computação em linguagens funcionais, utilizando dois exemplos simples:

   inc :: [Int] -> [Int]
   inc [ ] = [ ]
   inc (x:xs) = (x + 1) : inc xs

   sqr :: [Int] -> [Int]
   sqr [ ] = [ ]
   sqr (x:xs) = x ^ 2 : sqr xs

É simples observar que  as funções anteriores possuem a mesma estrutura, ambas quando aplicadas a uma lista vazia a retornam e quando a lista é não vazia, aplicam uma função à cabeça desta lista e repetem o processo para a cauda desta lista. A reutilização de tal padrão de computação nos leva a função map, presente na biblioteca de Haskell:

    map :: (a -> b) -> [a] -> [b]
    map f []     = []
    map f (x:xs) = f x : map f xs

Utilizando map, as duas funções anteriores podem ser descritas de maneira mais compacta:

    inc = map (+1)
    sqr = map (^2)

Avaliando expressões aritméticas

Sem sombra de dúvida, o exemplo mais utilizado para mostrar o poder de linguagens funcionais é a codificação de interpretadores de alguma linguagem. Considere, a seguinte linguagem simples de expressões que é constituída de constantes inteiras e um operador de divisão:

   data Expr = Val Int | Div Expr Expr

A função que avalia tais expressões possui uma implementação direta:

  eval :: Expr -> Int
  eval (Val n) =  n
  eval (Div x y) =  eval x `div` eval y

Porém,esta função não leva em consideração a possibilidade de uma divisão por zero, e irá produzir um erro em tempo de execução neste caso. Para lidar com este problema de maneira simples, podemos utilizar o tipo de dados Maybe

data Maybe a = Nothing | Just a

para definir uma versão “segura” (isto é, que não causa erros em tempo de execução) da divisão:

safediv :: Int -> Int -> Maybe Int
safediv n m =  if m == 0 then Nothing else Just (n `div` m)

e então realizar as mudanças necessárias na função que interpreta as expressões, como mostrado no trecho seguinte:

eval :: Expr -> Maybe Int
eval (Val n)   =  Just n
eval (Div x y) =  case eval x of
                    Nothing -> Nothing
                    Just n   -> case eval y of
                                 Nothing -> Nothing
                                 Just m  -> safediv n m

Assim como na seção anterior, pode-se observar um padrão nesta definição: um casamento de padrão sobre um valor do tipo Maybe, mapeando valores Nothing neles próprios, e valores da forma Just x em algum resultado que depende de alguma maneira de x.

Mas como este padrão pode ser reutilizado? Uma abordagem seria observar que a chave de avaliar uma divisão é realizar um casamento de padrão sobre dois valores do tipo Maybe que resultam de avaliar ambos os argumentos da divisão. Sendo assim, pode-se definir uma função para abstrair este casamento de padrão:

seqn  :: Maybe a -> Maybe b -> Maybe (a,b)
seqn Nothing   _        =  Nothing
seqn _         Nothing  =  Nothing
seqn (Just x)  (Just y) =  Just (x,y)

Usando seqn pode-se definir a avaliação de expressões de maneira mais elegante e compacta:

eval (Val n)   = Just n
eval (Div x y) = apply f (eval x `seqn` eval y)
                 where f (n,m) = safediv n m

A função apply é uma simples aplicação par ao tipo Maybe e é usada para processar o resultado de duas avaliações:

apply :: (a -> Maybe b) -> Maybe a -> Maybe b
apply f Nothing  =  Nothing
apply f (Just x) =  f x

Tudo parece muito bom! Porém a função seqn pode tornar o código uma “baderna”  se tentarmos manipular tuplas aninhadas.  Suponha, como exemplo, que nossa linguagem de expressões possuísse suporte a operadores de três argumentos. A avaliação de tal operador é apresentada no trecho de código seguinte:

eval (Op x y z) = apply f (eval x `seqn` (eval y `seqn` eval z))
                  where f (a,(b,c)) = ...

Reutilizando sequenciamento e processamento

O problema de tuplas aninhadas pode ser evitado ao novamente observar que isso nada mais é que “um casamento de padrão sobre valores do tipo Maybe, que preserva valores da forma Nothing e transforma valores da forma Just x em algo que depende de x.” A reutilização deste padrão é feita pelo operador definido a seguir:

(>>=) :: Maybe a -> (a -> Maybe b) -> Maybe b
Nothing  >>= _ = Nothing
(Just x) >>= f = f x

Se o primeiro argumento é da forma Nothing, então o segundo argumento é ignorado e Nothing é retornado como resultado. Caso contrário, se o primeiro argumento é da forma (Just x), então o segundo argumento é aplicado a x para obter um resultado de tipo Maybe b. Simples, não?

O operador >= evita o problema do aninhamento de tuplas de resultados porque o resultado do primeiro argumento é disponibilizado diretamente para processamento pelo segundo, ao invés de aguardar um segundo resultado para ser processado posteriormente. Desta maneira, >>= integra o sequenciamento de valores de tipo Maybe com o processamento de valores resultantes de computações sobre esse tipo. Em Haskell, o operador >>= é muitas vezes denominado “bind” (vincular), pois o segundo argumento é vinculado ao resultado do primeiro. Observe que >>= é idêntico a função apply definida anteriormente, a menos de que seus argumentos são “trocados”.

Usando o operador >>=, a função que avalia expressões aritméticas pode ser reescrita como:

eval (Val n)   = Just n
eval (Div x y) = eval x >>= (\n -> eval y >>=
                        (\m -> safediv n m))

A equação para a divisão pode ser lida da seguinte maneira: avalie x e chame o resultado desta avaliação de n, então avalie y e chame seu resultado de m, e finalmente combine estes dois resultados usando a função safediv.

Podemos generalizar a estrutura deste pequeno exemplo para expressões quaisquer que utilizam o operador >>=. Essas expressões possuem a seguinte estrutura:

     m1 >>= \x1 ->
     m2 >>= \x2 ->
         ...
     mn >>= \xn ->
         f x1 x2 ... xn

Traduzindo esta definição para português simples: Avalie cada uma das expressões m1, m2, …, mn e combine os resultados de cada uma delas aplicando a função f.

A definição de >>= garante que tal expressão somente retorna um valor de forma Just se nenhum mi na sequência retorna Nothing. Em outras palavras, não é necessário o programador se preocupar com eventuais falhas (representado no exemplo, por retornar um valor Nothing) em cada uma das expressões envolvidas, pois o operador >>= cuida desta manipulação de maneira simples.

Tais expressões são tão comuns em Haskell, que a linguagem possui uma notação especial permitindo que essas sejam escritas de uma forma mais legível:

do
    x1 <- m1
    x2 <- m2
    ...
    xn <- mn
    f x1 x2 ... xn

Utilizando esta notação, pode-se reescrever o avaliador de expressões de maneira bem simples e legível:

eval (Val n)   = Just n
eval (Div x y) = do
                    n <- eval x
                    m <- eval y
                    safediv n m

Mônadas em Haskell

O uso da notação do não é restrita a valores do tipo Maybe, a única restrição sobre essa notação é que ela deve somente ser utilizada em computações envolvendo tipos que constituem uma mônada. O conceito de mônada vem de um ramo da matemática chamado de teoria das categorias. Para a utilização de mônadas em Haskell não é necessário entender este conceito matemático. Na prática, uma mônada em Haskell, é um tipo m que possui duas funções:

return :: a -> m a

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

Por exemplo, se considerarmos que m  = Maybe, temos que os tipos de return e >>= são:

return :: a -> Maybe a

(>>=)  :: Maybe a -> (a -> Maybe b) -> Maybe b

Com estas duas funções, temos nossa primeira mônada.

Haskell suporta a definição de funções sobrecarregadas utilizando classes de tipos. Uma classe de tipo é uma coleção de tipos que possuem uma determinada interface de funções sobrecarregadas definidas sobre estes.

Por exemplo, a classe Eq de tipos que permitem o teste de igualdade, pode ser declarado da seguinte maneira:

class Eq a where
    (==) :: a -> a -> Bool
    (/=) :: a -> a -> Bool

    x /= y = not (x == y)

A definição declara que para um tipo “a” ser uma instância da classe Eq , ele deve suportar os operadores de teste de igualdade / desigualdade com os tipos especificados. Devido ao fato da classe possuir uma definição padrão para o operador de desigualdade (/=), é necessário apenas definir a igualdade para o tipo em questão. Como um exemplo, podemos definir uma instância para o tipo Bool:

instance Eq Bool where
    False == False = True
    True  == True  = True
     _     == _      = False

A noção de mônada pode ser representada utilizando a seguinte declaração de classe:

class Monad m where
    return :: a -> m a
    (>>=)  :: m a -> (a -> m b) -> m b

Isto é, uma mônada é um tipo “m” que implementa as funções return e >>= dos tipos especificados. A definição de uma instância para o tipo Maybe:


instance Monad Maybe where
     return x       =  Just x

     Nothing  >>= _ =  Nothing
     (Just x) >>= f =  f x

Agora que definimos esta instância para o tipo Maybe, podemos utilizar a notação do para computações envolvendo este tipo. Todo tipo que é instância da classe Monad, pode ser utilizado com a notação do.

A mônada de listas

A mônada de Maybe provê um simples modelo de computações que podem falhar, no sentido de que um valor de tipo Maybe é da forma Nothing, que pode ser pensado como uma falha, ou possui a forma Just x para algum x de tipo a, que pode ser entendido como um sucesso. A mônada de listas generaliza esta noção, permitindo múltiplos resultados no caso de sucesso.

Sendo mais preciso, um valor de tipo [a] ou é uma lista vazia [ ], que podemos ver como uma falha, ou possui a forma de uma lista não vazia [x_1, x_2, ..., x_n] para algum x_i de tipo a, que pode ser visto como o sucesso. De certa maneira, uma mônada de lista pode ser utilizada para modelar computações não determinísticas, onde mais de um resultado é produzido a cada passo. A definição de uma lista como sendo uma mônada é direta:

instance Monad [ ] where
    return x  =  [x]
    xs >>= f  =  concat (map f xs)

(Nota: Nesta definição, [ ] representa um tipo lista sem seu parâmetro a ). A função return simplesmente converte um valor qualquer em um resultado contendo este valor, enquanto >>= fornece uma maneira de sequenciar computações que podem retornar mais de um resultado: xs >>= f aplica a função f a cada um dos resultados da lista xs produzindo, assim, uma lista de listas de resultados que é posteriormente concatenada para formar uma única lista contendo todos os resultados.

Como exemplo da utilização da mônada de listas, uma função que retorna todas as maneiras de combinar pares de elementos de duas listas pode ser definida utilizando a notação do da seguinte maneira:

pairs     :: [a] -> [b] -> [(a,b)]
pairs xs ys =  do
                 x <- xs
                 y <- ys
                 return (x,y)

Isto é, considere cada possível valor x da lista xs, e cada valor y da lista ys, e retorne o par (x,y). Observe a definição da função pairs utilizando list comprehension:

pairs xs ys = [(x,y) | x <- xs, y <- ys]

Na verdade, list comprehensions e a notação do para listas são equivalentes. Ambas notações são maneiras diferentes de se utilizar o operador >>= para listas.

A mônada de estado

Agora consideremos o problema de implementar funções que manipulam algum tipo de estado, representado por um tipo cujos detalhes internos podemos, por agora, ignorar. Pode-se considerar que este tipo possui a seguinte forma:

type State = ...

A mais básica função sobre um estado é o que chamamos de “transformador de estado” (abreviado como ST , do inglês state transformer), que recebe como parâmetro o estado atual, e produz um estado possivelmente modificado e um resultado.

type ST a = State -> (a, State)

A figura a seguir ilustra a aplicação de tal função a um estado s, produzindo um novo estado s’ e um resultado v.

Transformador de estado

Um transformador de estados pode receber argumentos adicionais. Todavia, não é necessário alterar o tipo ST, porque este comportamento pode obtido por currying. Por exemplo, um transformador de estados que recebe um caractere (Char) e retorna um inteiro (Int) possui o tipo Char -> ST Int, que é uma abreviação para Char -> State -> (Int, State). Isto pode ser representado graficamente por:

Retornando às mônadas, é fácil observar que ST constitui uma mônada de simples definição:

 instance Monad ST where
    return x  =  \s -> (x,s)
    st >>= f  =  \s -> let (x,s') = st s in f x s'

Isto é, return converte um valor em um transformador de estado que apenas retorna aquele valor sem modificar o estado. Graficamente:

Visão diagramática da função return

Por sua vez, (>>=) provê uma maneira de sequenciar transformadores de estados: st >>= f aplica o tranformador de estado st a um estado inicial s, então aplica a função f ao resultado x para produzir um segundo transformador de estado (f x), que é então aplicado ao novo estado s’ para produzir o resultado final. Graficamente:

Sequenciando transformadores de estado

Perceba que return poderia ser definido como:

return x s = (x,s)

Todavia, a definição anterior é preferida por ocultar o parâmetro de estado s. Um pequeno detalhe sobre a instância para a mônada ST definida anteriormente: Haskell não permite a definição de instâncias para sinônimos de tipos. Portanto, podemos definir o tipo ST da seguinte forma alternativa (mas equivalente):

newtype ST a = ST { runST :: State -> (a, State) }

A definição da mônada ST pode ser feita da seguinte maneira:

instance Monad ST where
    return x   = ST (\s -> (x,s))
    st >>= f   = ST (\s -> let
                             (x,s') = runST st s
                           in runST (f x) s')

Mônada de estado: Um Exemplo

Como um simples exemplo de utilização de uma mônada de estado, vamos considerar a tarefa de rotular cada nó de uma árvore binária com um número inteiro que o identifica unicamente. Para isso, será necessário definir um tipo de dados para árvores binárias:

data Tree a = Leaf a | Node (Tree a) (Tree a)

Segue um pequeno exemplo de uma árvore:

tree :: Tree Char
tree =  Node (Node (Leaf 'a') (Leaf 'b')) (Leaf 'c')

Agora iremos considerar nosso problema original: de rotular cada nó com um número inteiro correspondente ao valor deste nó. Primeiramente, deve-se definir o tipo do estado a ser manipulado. Como o objetivo é adicionar um número inteiro para cada nó da árvore, toda vez que passarmos por um nó devemos “incrementar nosso” contador, que representa o estado a ser manipulado. Portanto, nada mais natural que definir o estado como sendo um número inteiro:


type State = Int

Considerando que o estado armazenado seja um número inteiro e que a cada nó visitado o estado deve ser atualizado com o sucessor deste número, temos que implementar um transformador de estado que retorna o estado atual como seu resultado e incrementa este número para formar o novo estado. Isto é:

fresh :: ST Int
fresh =  S (\n -> (n, n+1))

Usando esta função e as funções monádicas para ST fica fácil definir uma função que recebe uma árvore como argumento e retorna um transformador que produz a mesma árvore onde cada nó é rotulado com um inteiro:

mlabel :: Tree a -> ST (Tree (a,Int))
mlabel (Leaf x)   =  do
                       n <- fresh
                       return (Leaf (x,n))
mlabel (Node l r) =  do
                       l' <- mlabel l
                       r' <- mlabel r
                       return (Node l' r')

Observe que não é necessário que o programador se preocupe com a tarefa tediosa e propensa a erros de lidar com a criação de novos rótulos para cada componente da árvore, já que isso é diretamente manipulado pela mônada de estado!

Tendo este transformador de estado em mãos, podemos definir uma função que rotula uma árvore simplesmente aplicando o transformador tendo o inteiro 0 como estado inicial e descartando o estado final.

label  :: Tree a -> Tree (a,Int)
label t = fst (apply (mlabel t) 0)

A aplicação da função label à árvore tree resulta em:

Node (Node (Leaf ('a',0)) (Leaf ('b',1))) (Leaf ('c',2))

A mônada de I/O

Programas interativos em Haskell são escritos utilizando o tipo IO a que retorna um valor de tipo a, mas pode realizar alguma entrada / saída. A biblioteca Prelude possui diversas funções para construir valores de tipo IO:

return  :: a -> IO a
(>>=)   :: IO a -> (a -> IO b) -> IO b
getChar :: IO Char
putChar :: Char -> IO ()

Veja só… o tipo IO  possui as funções return  e (>>=), o que quer dizer que o tipo IO é uma mônada, e portanto, podemos utilizar a notação do para escrever programas interativos. Como exemplo, considere a seguinte função que lê uma sequência de caracteres a partir do teclado:

getLine :: IO String
getLine = do
            x <- getChar
            if x == '\n' then []
              else do
                    xs <- getLine
                    return (x:xs)

É interessante notar que a mônada de IO pode ser interpretada como um caso especial de uma mônada de estado, na qual o estado interno da mônada representa o estado de “todo o mundo”:

type World = ...
type IO a  = World -> (a,World)

Isto é, uma ação (um valor de tipo IO a) pode ser visto como uma função que recebe o estado atual do mundo como seu argumento, e produz um valor e este estado possivelmente modificado (refletindo possíveis resultados de entrada e saída executados pela ação). Internamente, o compilador GHC utiliza uma representação similar a esta para codificar valores de tipo IO.

Conclusão

Este post foi extenso, mas serviu apenas para “arranhar” o tópico sobre mônadas e programação funcional. Como o tema é deveras extenso, não é possível abordar todas as nuances deste. Recomendo os seguintes artigos, para leitores que desejam aprofundar seus conhecimentos:

  1. The Essence of Functional Programming – Philip Wadler
  2. Monadic Parsing Combinators – Graham Hutton

Além disso tem havido interesse em arrows  e funtores aplicativos que são generalizações de mônadas. Referências sobre estes temas são

  1. Generalizing monads to arrows – John Hughes
  2. Applicative Programming with Effects – Connor McBride.
Anúncios

Deixe um comentário

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s


%d blogueiros gostam disto: