Grupo de Estudos em Haskell da UFABC > Introdução à Programação Funcional em Haskell > Monads

Monads

Playlists

Desta aula:
- Parte 1: https://www.youtube.com/playlist?list=PLYItvall0TqLW_mPtIpVA8qHpuQ3YbnVO
- Parte 2: https://www.youtube.com/playlist?list=PLYItvall0TqIl6y3FydOuEjFMH6jp7ROm
Do curso: https://www.youtube.com/playlist?list=PLYItvall0TqJ25sVTLcMhxsE0Hci58mpQ

1 Monads

Vamos definir um tipo de dado que representa expressões matemáticas:

data Expr = Val Int
	  | Add Expr Expr
	  | Sub Expr Expr
	  | Mul Expr Expr
	  | Div Expr Expr

Para avaliar essa expressão podemos definir:

eval :: Expr -> Int
eval (Val n)   = n
eval (Add x y) = (eval x) + (eval y)
eval (Sub x y) = (eval x) - (eval y)
eval (Mul x y) = (eval x) * (eval y)
eval (Div x y) = (eval x) `div` (eval y)

Porém, se fizermos:

> eval (Div (Val 1) (Val 0))
*** Exception: divide by zero

1.1 Maybe

Podemos resolver isso usando maybeDiv e Maybe (vamos focar apenas na divisão):

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  -> maybeDiv n m

Agora temos:

> eval (Div (Val 1) (Val 0))
Nothing

Mas nosso código está confuso…

O uso de Applicative pode resolver muitos problemas de encadeamento de funções com efeito
Seria legal poder fazer:

pure maybeDiv <*> eval x <*> eval y

Mas maybeDiv tem tipo Int -> Int -> Maybe Int e deveria ser Int -> Int -> Int para o uso de applicativo.

O problema aqui é que o uso de Applicative é para sequências de computações que podem ter efeitos mas que são independentes entre si.
Queremos agora uma sequência de computações com efeito mas que uma computação dependa da anterior.

Precisamos de uma função que capture nosso padrão de case of:

vincular :: Maybe a -> (a -> Maybe b) -> Maybe b
vincular mx g = case mx of
		  Nothing -> Nothing
		  Just x  -> g x

O nome significa que estamos vinculando o resultado da computação de mx ao argumento da função g.

No Haskell esse operador é conhecido como bind e definido como:

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

Qualquer semelhança com o logo de Haskell, é mera coincidência 😄

1.2 Monoid de Monad

Em teoria das categorias um Monad pode ser visto como um Monoid das categorias dos Functors.
- O elemento identidade é o return
- O operador associativo é uma variação de (>>=) com a assinatura:

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

Ou seja, duas funções que transformam um valor puro em um Monad podem ser combinadas formando uma terceira função.

(>=>) também chamado de operador peixe (_ fish operator_).

Com isso podemos reescrever eval como:

eval :: Expr -> Maybe Int
eval (Val n)   = Just n
eval (Div x y) = eval x >>= \n ->
		 eval y >>= \m ->
		 maybeDiv n m

> eval (Div (Val (Just 4)) (Val (Just 2)))
  => (Just 4) >>= \n ->
	      (Just 2) >>= \m -> maybeDiv n m
  => (Just 2) >>= \m -> maybeDiv 4 m
  => maybeDiv 4 2

> eval (Div (Val (Nothing)) (Val (Just 2)))
  => Nothing >>= \n ->
	     (Just 2) >>= \m -> maybeDiv n m
  => Nothing

> eval (Div (Val (Just 4)) (Val (Nothing))
  => (Just 4) >>= \n ->
	      (Just 2) >>= \m -> maybeDiv n m
	      => Nothing >>= \m -> maybeDiv 4 m
  => Nothing

Generalizando, uma expressão construída com o operador (>>=) tem a seguinte estrutura:

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

Indicando um encadeamento de computação sequencial para chegar a uma aplicação de função. Esse operador garante que se uma computação falhar, ela para imediatamente e reporta a falha (em forma de Nothing, [], etc.)

1.3 Monads: Syntactic Sugar

Essa mesma expressão pode ser escrita com a notação chamada do-notation :

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

Com isso podemos reescrever eval novamente como:

eval :: Expr -> Maybe Int
eval (Val n)   = Just n
eval (Div x y) = do n <- eval x
		    m <- eval y
		    safeDiv n m

Que captura uma sequência de computações que devem respeitar a ordem, são dependentes e podem falhar. Uma notação imperativa? 🤔

Esse tipo de operação forma uma nova classe de tipos denominada Monads :

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

   return = pure

Além do operador bind ela redefine a função pure com o nome de return.

Já escrevemos a definição de Monad Maybe mas podemos deixá-la mais clara utilizando Pattern Matching:

instance Monad Maybe where
   Nothing  >>= _ = Nothing
   (Just x) >>= f = f x

2 `SafeNum` + `Monad`

-- Versão com monad
f3' :: Int -> Int -> SafeNum Int
f3' x y =
  safeDiv x y >>= \xy ->
  safeDiv y x >>= \yx ->
  safeAdd xy yx

f3 :: Int -> Int -> SafeNum Int
f3 x y = do
  xy <- safeDiv x y
  yx <- safeDiv y x
  safeAdd xy yx

-- Versão "pura"
f0 :: Int -> Int -> SafeNum Int
f0 x y
  | isSafe xy && isSafe yx = safeAdd (unbox xy) (unbox yx)
  | (not.isSafe) xy = xy
  | otherwise = yx
  where
    xy = safeDiv x y
    yx = safeDiv y x
    unbox (SafeNum x) = x
    isSafe (SafeNum _) = True
    isSafe _           = False

-- Versão com functors
f1 :: Int -> Int -> SafeNum Int
f1 x y =
  let xy = safeDiv x y
      yx = safeDiv y x
      safeAddXY = fmap safeAdd xy
      safeXYPlusYX = fmap (`fmap` yx) safeAddXY
  in
    (flatten.flatten) safeXYPlusYX

-- Versão com applicative
f2 :: Int -> Int -> SafeNum Int
f2 x y =
  let xy = safeDiv x y
      yx = safeDiv y x
  in
    flatten $ pure safeAdd <*> xy <*> yx

-- Versão com monad
f3 :: Int -> Int -> SafeNum Int
f3 x y = do
  xy <- safeDiv x y
  yx <- safeDiv y x
  safeAdd xy yx

2.1 Exercício 1

Escreva a instância de Monad para o tipo SafeNum.

data SafeNum a = NaN | NegInf| PosInf | SafeNum a deriving Show

2.2 Resposta - Exercício 1

data SafeNum a = NaN | NegInf| PosInf | SafeNum a deriving Show

instance Monad SafeNum where
  (SafeNum v) >>= f = f v
  v           >>= _ = boxedCoerce v

3 Monads e Efeitos

Embora a linguagem Haskell seja conhecida como uma linguagem puramente funcional .

Existe um limite do quanto nosso programa pode ser puro!

Imagine um programa que computa 1 milhão de casas decimais de \(\pi\) só que não imprime o resultado por causa da ausência de efeitos colaterais.

As funções impuras são necessárias para diversas ocasiões conforme apontado por Eugenio Moggi:

Parcialidade
Não-determinismo
Efeitos colaterais: Read only, Write only, Read/Write
Exceções
Continuações
Entrada e Saída Interativa

3.1 Parcialidade

Quando temos uma função que pode não terminar.
Valor bottom ⊥:

f :: a -> Bool

retorna True, False ou _|_.

3.2 Não-determinismo

Quando uma função pode retornar diferentes saídas dependendo de certas condições internas ou externas, ela é dita não-determinística .

Por exemplo, ao jogar um dado, podemos ter seis saídas diferentes!

Uma forma de modelar não-determinismo é com uso de listas:

data Dado = Um | Dois | Tres | Quatro | Cinco | Seis
	       deriving (Show, Bounded, Enum, Eq)

jogaDado = [Um .. Seis]

A cada jogada de dados, eu recebo um novo número de Um a Seis. Quais combinações eu posso ter ao jogar os dados duas vezes?

jogaDuasVezes = do
  dado1 <- jogaDado
  dado2 <- jogaDado
  return (dado1, dado2)

jogaDuasVezes

Saída:


[(Um,Um),(Um,Dois),(Um,Tres),(Um,Quatro),(Um,Cinco),(Um,Seis),(Dois,Um),(Dois,Dois),(Dois,Tres),(Dois,Quatro),(Dois,Cinco),(Dois,Seis),(Tres,Um),(Tres,Dois),(Tres,Tres),(Tres,Quatro),(Tres,Cinco),(Tres,Seis),(Quatro,Um),(Quatro,Dois),(Quatro,Tres),(Quatro,Quatro),(Quatro,Cinco),(Quatro,Seis),(Cinco,Um),(Cinco,Dois),(Cinco,Tres),(Cinco,Quatro),(Cinco,Cinco),(Cinco,Seis),(Seis,Um),(Seis,Dois),(Seis,Tres),(Seis,Quatro),(Seis,Cinco),(Seis,Seis)]

Imagine agora que esse dado é mágico, e toda vez que ele cai em um número par, o próximo é ímpar e vice-versa:

magica :: Dado -> [Dado]
magica dado
  | any (dado==) [Um, Tres, Cinco] = [Dois, Quatro, Seis]
  | otherwise                      = [Um, Tres, Cinco]

jogaDuasVezes' :: [(Dado, Dado)]
jogaDuasVezes' = do
  dado1 <- jogaDado
  dado2 <- magica dado1
  return (dado1, dado2)

jogaDuasVezes'

Saída:


[(Um,Dois),(Um,Quatro),(Um,Seis),(Dois,Um),(Dois,Tres),(Dois,Cinco),(Tres,Dois),(Tres,Quatro),(Tres,Seis),(Quatro,Um),(Quatro,Tres),(Quatro,Cinco),(Cinco,Dois),(Cinco,Quatro),(Cinco,Seis),(Seis,Um),(Seis,Tres),(Seis,Cinco)]

A Monad lista é definida como:

instance Monad [] where
  xs >>= f = [y | x <- xs, y <- f x]

Nossa função jogaDuasVezes usando bind fica:

jogaDuasVezes :: [(Dado, Dado)]
jogaDuasVezes = jogaDado >>= \dado1 ->
		  jogaDado >>= \dado2 ->
		    return (dado1, dado2)

E a versão jogaDuasVezes' como:

jogaDuasVezes' :: [(Dado, Dado)]
jogaDuasVezes' = jogaDado >>= \dado1 ->
		  magica dado1 >>= \dado2 ->
		   return (dado1, dado2)

Para gerar todas as combinações de elementos de duas listas pode ser escrito como:

pares :: [a] -> [b] -> [(a,b)]
pares xs ys = xs >>= \x ->
	      ys >>= \y ->
	      return (x,y) -- [(x,y)]

Ou em do-notation:

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

> pares [1,2] [3,4]
  => [1,2] >>= \x ->
	  [3,4] >>= \y ->
	       [(x,y)]
  => [x' | x  <- [1,2],
	   x' <- \x -> [3,4] >>= \y -> [(x,y)]]
  => [x' | x  <- [1,2],
	   x' <- \x -> [y' | y <- [3,4], y' <- [(x,y)]]
  => [x' | x  <- [1,2],
	   x' <- \x -> [y' | y' <- [(x,3), (x,4)]]
  => [x' | x  <- [1,2],
	   x' <- \x -> [(x,3), (x,4)]]
  => [x' | x' <- [(1,3),(1,4),(2,3),(2,4)]]
  => [(1,3),(1,4),(2,3),(2,4)]

A compreensão de listas surgiu a partir da notação do:

pares xs ys = [(x,y) | x <- xs, y <- ys]
  == do x <- xs
	y <- ys
	return (x,y)

3.3 Exceções: `Either`

Para lidarmos com funções parciais ou que geram

exceções, podemos utilizar o Maybe.

Porém, ele apenas indica que houve um problema

na avaliação das funções, mas não diz qual foi ele.

Um tipo que generaliza o Maybe e permite reportar

o ponto que ocorreu a falha é o Either:

data Either a b = Left a | Right b

Podemos definir Left como o log do erro e Right

como o valor esperado, caso tudo dê certo.

A instância de Functor age apenas no valor da direita:

instance Functor (Either a) where
  fmap f (Left x) = Left x
  fmap f (Right x) = Right (f x)

Similar ao Maybe, a instância de Applicative

propaga o Left e aplica a função no Right:

instance Applicative (Either a) where
  pure x = Right x

  (Left f)  <*> _         = Left f
  _         <*> (Left x)  = Left x
  (Right f) <*> (Right x) = Right (f x)

A instância de Monad também é similar ao Maybe:

instance Monad (Either a) where
  (Left x) >>= f  = Left x
  (Right x) >>= f = f x

Com isso podemos fazer:

safeDiv :: (Show a, Eq a, Floating a) => a -> a -> Either String a
safeDiv a b
  | b == 0 = Left ("Divisao por zero: " ++ show a ++ "/" ++ show b)
  | otherwise = Right (a/b)

safeLog :: (Show a, Ord a, Eq a, Floating a) => a -> Either String a
safeLog x
  | x <= 0    = Left ("Log invalido: " ++ show x)
  | otherwise = Right (log x)

safeAdd :: Floating a => a -> a -> Either String a
safeAdd a b = Right (a+b)

safeExpr1, safeExpr2 :: Either String Double
safeExpr1 = do q <- safeDiv 10 (-2)
	       l <- safeLog q
	       safeAdd 2 q

safeExpr2 = do q <- safeDiv 10 0
	       safeAdd 2 q

print safeExpr1
print safeExpr2

3.4 Experiment no Repl.it

Código no Repl.it

3.5 Efeitos Colaterais: Read Only

Digamos que temos uma configuração global compartilhada com todas as funções:

data Config = Conf { tweet_key  :: String
		   , api_secret :: String
		   }

E toda função f :: a -> b passa a receber um argumento adicional Config com essa configuração global:

postTweet :: (String, Config) -> String
postTweet (t, e)
  | valida (t, e) = t
  | otherwise     = "senha inválida"

valida :: (String, Config) -> Bool
valida (x, e)
  | (tweet_key e) == "teste" = True
  | otherwise = False

Veja que essencialmente postTweet, valida tem tipos String -> () e String -> Bool, mas foram embelezadas para receber também as configurações globais.

Aplicando currying temos:

postTweet :: String -> Config -> String
postTweet t e
  | valida t e = t
  | otherwise  = "senha inválida"

valida :: String -> Config -> Bool
valida x e
  | (tweet_key e) == "teste" = True
  | otherwise = False

E podemos definir o tipo:

data Reader e a = Reader (e -> a)

postTweet :: String -> Reader Config ()
valida :: String -> Reader Config Bool

Como fica a instância de Functor para o tipo Reader?

data Reader e a = Reader (e -> a)

instance Functor (Reader e) where
  -- fmap :: (a -> b) -> Reader e a -> Reader e b
  fmap f (Reader g) = Reader (f.g)

E a instância de Applicative?

data Reader e a = Reader (e -> a)

runReader :: Reader e a -> e -> a
runReader (Reader f) e = f e

instance Applicative (Reader e) where
  -- pure :: a -> Reader e a
  pure x = Reader (\e -> x)

  -- (<*>) :: Reader e (a -> b) -> Reader e a -> Reader e b
  rab <*> ra = Reader (\e -> ab e (a e))
    where
      ab = runReader rab -- :: e -> (a -> b)
      a  = runReader ra  -- :: e -> a

Para evitar os parênteses, podemos reescrever como:

instance Applicative (Reader e) where
  -- pure :: a -> Reader e a
  pure x = Reader (\e -> x)

  -- (<*>) :: Reader e (a -> b) -> Reader e a -> Reader e b
  rab <*> ra = Reader (\e -> let fab = runReader rab e
				 fa  = runReader ra e
			     in  fab fa)

Finalmente para criar a instância de Monad temos:

data Reader e a = Reader (e -> a)

instance Monad (Reader e) where
  -- (>>=) :: Reader e a -> (a -> Reader e b) -> Reader e b
  ra >>= arb =
    Reader (\e -> let a  = runReader ra e -- a
		      rb = arb a -- Reader e b
		  in  runReader rb e)

Uma versão simplificada do exemplo do tweet acima fica:

postTweet :: String -> Reader Config String
postTweet t = do
  b <- valida t
  if b then return t
  else return "senha inválida"

valida :: String -> Reader Config Bool
valida x = do
  key <- askfor tweet_key
  if key == "teste"
  then return True
  else return False

3.6 Experiment no Repl.it

Código no Repl.it

3.7 Efeitos Colaterais: Write Only

Considere o seguinte código:

isEven x = even x
not'   b = not b
isOdd  x = (not' . isEven) x

Digamos que eu gostaria de gravar o traço de execução para verificar as funções que são chamadas. Logo eu gostaria que:

> isOdd 3
(True, " isEven not' ")

Podemos criar novas versões de nossas funções:

isEven x = (even x, " isEven ")
not'   b = (not b, " not' ")
isOdd  x = (not' . isEven) x -- ops

Não é mais possível compor as funções isEven e not'…

isEven x = (even x, " isEven ")
not'   b = (not b, " not' ")
isOdd  x = let (b1, trace1) = isEven x
	       (b2, trace2) = not' b
	   in  (b2, trace1 ++ trace2)

Nada prático…

As assinaturas dessas funções seguem o formato a -> (b, String):

isEven :: Integer -> (Bool, String)
isEven x = (even x, " isEven ")

not' :: Bool -> (Bool, String)
not'   b = (not b, " not' ")

isOdd :: Integer -> (Bool, String)
isOdd  x = let (b1, trace1) = isEven x
	       (b2, trace2) = not' b
	   in  (b2, trace1 ++ trace2)

Fazendo m = (, String), temos a -> m b 🤔

Vamos definir o tipo Writer e algumas funções auxiliares:

data Writer w a = Writer a w

runWriter :: Writer w a -> (a, w)
runWriter (Writer a w) = (a, w)

tell :: w -> Writer w ()
tell s = Writer () s

O w do tipo Writer representa o tipo do efeito colateral desejado, no nosso exemplo, a String.

A instância de Functor simplesmente aplica uma função no valor sem causar um efeito colateral.

instance (Monoid w) => Functor (Writer w) where
  -- fmap :: (a -> b) -> Writer w a -> Writer w b
  fmap f (Writer a w) = Writer (f a) w

Hmmm…Monoid 🤔

Para a instância de Applicative a função pure cria um valor sem efeito colateral. No nosso exemplo, a String vazia! O operador aplicar simplesmente aplica a função no valor e concatena os efeitos!

instance (Monoid w) => Applicative (Writer w) where
  -- pure :: a -> Writer w a
  pure x = Writer x mempty

  -- (<*>) :: Writer w (a -> b) -> Writer w a -> Writer w b
  (Writer f m1) <*> (Writer a m2) = Writer (f a) (m1 <> m2)

A instâcia de Monad aplica a função no valor puro de

nosso Writer, gerando um efeito colateral…

instance (Monoid w) => Monad (Writer w) where
  -- (Writer w a) -> (a -> Writer w b) -> (Writer w b)
  (Writer a w) >>= k = let (b, w') = runWriter (k a)
		       in  Writer b (w <> w')

…em seguida retorna o valor com os efeitos compostos.

Dessa forma nosso exemplo fica:

isEvenW' :: Integer -> Writer String Bool
isEvenW' x = do tell " even "
		return (even x)

notW' :: Bool -> Writer String Bool
notW' b = do tell " not "
	     return (not b)

E podemos definir isOddW' com o operador

de composição de Monads >=>:

-- (>=>) :: (a -> m b) -> (b -> m c) -> (a -> m c)
isOddW' :: Integer -> Writer String Bool
isOddW' = (isEvenW' >=> notW')

3.8 Experiment no Repl.it

Código no Repl.it

3.9 Efeitos Colaterais: Read and Write

Considere o seguinte problema: tenho uma árvore do tipo Tree Char e quero converter para uma Tree Int sendo que os nós folhas receberão números de [0..] na sequência de visita:

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

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

f tree = Node (Node (Leaf 0) (Leaf 1)) (Leaf 2)

3.10 Estado

Um esqueleto dessa função seria:

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

rlabel :: Tree a -> Tree Int
rlabel (Leaf _)   = Leaf n
rlabel (Node l r) = Node (rlabel l) (rlabel r)

Queremos que n seja uma variável de estado, ou seja, toda vez que a utilizarmos ela altere seu estado!
Mas somos puros e imutáveis! Como podemos resolver isso?

Uma ideia é incorporar o estado atual na declaração da função:

rlabel :: Tree a -> Int -> (Tree Int, Int)
rlabel (Leaf _) n = (Leaf n, n + 1)
rlabel (Node l r) = (Node l' r', n'')
  where
    (l', n')   = rlabel l n  -- altera o estado de n
    (l'', n'') = rlabel r n' -- altera o estado de n'

Com isso podemos chamar:

> rlabel tree 0
 => (Node l' r', n'')
> (l', n') = rlabel (Node (Leaf 'a') (Leaf 'b')) 0
 => (Node l' r', n'')
> (l', n') = rlabel (Leaf 'a') 0
  => (Leaf 0, 1)
> (r', n'') = rlabel (Leaf 'b') 1
 => (Leaf 1, 2)
> (r, n'') = rlabel (Leaf 'c') 2
 => (Leaf 2, 3)

(Node (Node (Leaf 0) (Leaf 1)) (Leaf 2), 3)

Vamos generalizar o tipo Tree a -> Int -> (Tree Int, Int)

t -> (a -> (b, a))

A segunda parte me lembra algo…🤔

O tipo Reader é a -> b, o tipo Writer é (a, b):

t -> (a -> (b, a))
t -> Reader a (Writer a b)

Faz sentido, queremos um valor que pode ser lido e alterado: Reader-Writer.

3.11 Transformador de Estado

Vamos definir o tipo State como:

--             = Reader s (Writer s a)
data State s a = State (s -> (a, s))

Com isso a assinatura de rlabel pode se tornar:

rlabel :: Tree a -> State Int (Tree Int)

Um transformador de estado pode ser visto como uma caixa que recebe um estado e retorna um valor e um novo estado:

Podemos pensar também em um transformador de estados que, além de um estado, recebe um valor para agir dentro do ambiente que ele vive:

Vamos criar uma função auxiliar para aplicar um transformador de estado em um estado (que está encapsulado no construtor State):

runState :: State s a -> s -> (a, s)
runState (State f) s = f s

Essencialmente, as instâncias de Functor, Applicative, Monad são muito parecidas com as do Reader.

A ideia geral de um Functor ST é que ele defina como aplicar uma função pura do tipo a -> b na parte do valor do resultado de um ST a, transformando-o efetivamente em um tipo ST b:

Com isso temos:

instance Functor (State s) where
  -- fmap :: (a -> b) -> State s a -> State s b
  fmap f (State g) = State (\s -> let (a, s') = g s
				  in  (f a, s'))

criamos uma função que gera o valor a e um novo estado e, então, retorna f a com esse novo estado.

Esse Functor promete aplicar uma função pura apenas no valor de saída do transformador de estado, sem influenciar o estado.
Se em rlabel eu quiser gerar rótulos pares, poderia aplicar fmap (*2) a função de estado.

A classe Applicative define formas de combinar computações sequenciais puras dentro de computações que podem sofrer efeitos colaterais.
Embora cada computação na sequência possa alterar o estado s, o valor final é a computação dos valores puros.

A definição de pure cria um transformador de estado puro, ou seja, que não altera o estado:

Então definimos:

instance Applicative (State s) where
  -- pure :: a -> State s a
  pure x = State (\s -> (x, s))

A definição do operador (<*>) define a sequência de mudança de estados pelos transformadores e a combinação dos valores finais como um resultado único:

Então definimos:

instance Applicative (State s) where
  -- (<*>) :: State s (a -> b) -> State s a -> State s b
  sab <*> sa = State (\s -> let (f, s1) = runState sab s
				(a, s2) = runState sa  s1
			    in  (f a, s2))

Como primeiro passo é preciso recuperar a função f, o que altera o estado. Em seguida, recuperamos a utilizando o novo estado, gerando o próximo estado. Finalmente, aplicamos f a e retornamos o último estado gerado.

No nosso exemplo de rlabel, podemos imaginar algo como:

pure Leaf <*> sInc

Se sInc é um transformador de estados que incrementa um contador, então:
1. pure Leaf é aplicado no estado atual s retornando ele mesmo (pois é puro)
2. sInc é aplicado a s retornando um novo estado com o contador incrementado: (Leaf n, n + 1)

No caso de Monads, queremos definir um operador (>>=) que se comporte como:

Podemos observar que o operador bind age de forma similar a (<*>), porém cada encadeamento gera um novo transformador de estado que pode depender do valor retornado pelo transformador anterior.
Ou seja, um Monad ST pode ser usado quando queremos gerar novos transformadores dependendo do valor de retorno de outro.

Com isso definimos:

instance Monad (State s) where
  -- (>>=) :: State s a -> (a -> State s b) -> State s b
  sa >>= f = State (\s -> let (a, s1) = runState sa s
			      sb      = f a
			  in  runState sb s1)

Primeiro recuperamos o valor de a, gerando um novo estado. Em seguida, aplicamos f a que gera um novo State que é executado com o último estado gerado.

No nosso exemplo de rlabel, podemos imaginar algo como:

do n <- sInc
   return (Leaf n)

para alterar o rótulo de um nó folha.

3.12 Applicative rlabel

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

rlabel :: Tree a -> Int -> (Tree Int, Int)
rlabel (Leaf _) n   = (Leaf n, n+1)
rlabel (Node l r) n = let (l', n1) = rlabel l n
			  (r', n2) = rlabel r n1
		      in  (Node l' r', n2)

A versão completa do Applicative rlabel fica:

alabel :: Tree a -> State Int (Tree Int)
alabel (Leaf _) = pure Leaf <*> sInc
alabel (Node l r) = pure Node <*> alabel l <*> alabel r

mlabel :: Tree a -> State Int (Tree Int)
mlabel (Leaf _) = do n <- sInc
		     return (Leaf n)
mlabel (Node l r) = do l' <- mlabel l
		       r' <- mlabel r -- e se eu trocar a ordem?
		       return $ Node l' r'

Finalmente, a definição de sInc fica:

sInc :: State Int Int
sInc = S (\n -> (n, n+1))

3.13 Experiment no Repl.it

Código no Repl.it

Para aplicar essas funções, devemos fazer:

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

newtype ST a = S (State -> (a, State))
app :: ST a -> State -> (a, State)
app (S st) s = st s

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

alabel :: Tree a -> ST (Tree Int)
alabel (Leaf _)   = pure Leaf <*> sInc
alabel (Node l r) = pure Node <*> alabel l <*> alabel r

> stTree = alabel tree -- cria transformador de estado
> app stTree 0         -- começa a contar do 0
(Node (Node (Leaf 0) (Leaf 1)) (Leaf 2), 3)

3.14 Efeitos Colaterais: IO

Conforme discutimos anteriormente, funções de entrada e saída de dados são impuras pois alteram o estado atual do sistema.
A função getChar captura um caracter do teclado. Se eu executar tal função duas vezes, o valor da função não necessariamente será igual.
A função putChar escreve um caracter na saída padarão (ex.: monitor). Se eu executar duas vezes seguidas com a mesma entrada, a saída será diferente.

Basicamente, as funções de entrada e saída alteram estado, ou seja:

newtype IO a = newtype ST a = State -> (a, State)

com a definição de estado sendo:

type State = Environment

o estado sendo o ambiente, sistema operacional, o mundo computacional que ele vive.

Com isso, tudo que fizemos até agora é suficiente para trabalharmos com IO sem afetar a pureza dos nossos programas:

getchar :: IO Char

putChar :: Char -> IO ()

Se eu fizer:

do putChar 'a'
   putChar 'a'

Na verdade ele estará fazendo algo como:

(_, env')  = putChar 'a' env
(_, env'') = putChar 'a' env'

No Haskell chamamos as funções de entrada e saída como ações de IO (_ IO actions _).
As funções básicas são implementadas internamente de acordo com o Sistema Operacional

Vamos trabalhar inicialmente com três ações básicas:

-- recebe um caracter da entrada padrão
getChar :: IO Char

-- escreve um caracter na saída padrão
putChar :: Char -> IO ()

-- retorna um valor puro envolvido de uma ação IO
return :: a -> IO a

Em vez de capturar apenas um caracter, podemos capturar uma linha inteira de informação. Podemos escrever getLine da seguinte maneira:

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

A função return não se comporta como em outras linguagens!
Lembre-se: return apenas pega um valor puro e o coloca no em um contexto. Ele não interrompe a execução.

3.15 Exercício 2

Escreva as instruções do else como Applicative

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

3.16 Exercício 2 - Resposta

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

A função inversa escreve uma String na saída padrão:

putStr :: String -> IO ()
putStr []     = return ()
putStr (x:xs) = do putChar x
		   putStr  xs

putStrLn :: String -> IO ()
putStrLn xs = do putStr xs
		 putChar 'n'

3.17 Exercício 3

Escreva a função putStrLn usando Applicative.

putStrLn :: String -> IO ()
putStrLn xs = do putStr xs
		 putChar '\n'

3.18 Exercício 3 - Resposta

putStrLn :: String -> IO ()
putStrLn xs = do sequenceA [putStr' xs, putChar 'n']
		 return ()

4 Funções de alta ordem para Monads

As funções de alta ordem possuem versões para Monads na biblioteca Control.Monad:

mapM :: Monad m => (a -> m b) -> [a] -> m [b]
mapM f []     = return []
mapM f (x:xs) = do y  <- f x
		   ys <- mapM f xs
		   return (y:ys)

Digamos que tenho a seguinte função:

conv :: Char -> Maybe Int
conv c | isDigit c = Just (digitToInt c)
       | otherwise = Nothing

Podemos aplicar mapM para obter:

> mapM conv "1234"
Just [1,2,3,4]
> mapM conv "12a4"
Nothing

Também temos a versão monádica de filter:

filterM :: Monad m => (a -> m Bool) -> [a] -> m [a]
filterM p []     = return []
filterM p (x:xs) = do b  <- p x
		      ys <- filter M p xs
		      return (if b then x:ys else ys)

Podemos gerar o conjunto das partes com essa função e o Monad List:

> filterM (\x -> [True, False]) [1,2,3]
[[1,2,3],[1,2],[1,3],[1],[2,3],[2],[3],[]]

🤨 🤨 🤨

Lembrando que o Monad listas representa uma computação não deterministica.
filterM: “para um certo elemento da lista, quais as possibilidades de selecioná-lo?”
\_ -> [False, True] diz que cada elemento pode existir ou não na lista!

Para cada elemento da lista, ele cria duas ramificações: uma em que aquele elemento existe e outra que ele não existe.

      []
    /    \
   [1]     []
  /  \    /   \
[1,2] [1] [2] []
...

filter seleciona elementos de uma lista
filterM seleciona possíveis eventos de uma sequência de computações

Considere esse outro exemplo:

f x | even x = [False]
    | otherwise = [True, False]

Qual a saída para filterM f [1, 2, 3]?

filterM f [1, 2, 3]

Saída:


[[1,3],[1],[3],[]]

Nesse caso geramos a combinação dos elementos ímpares.

E se nossa função for:

g x | x == 0 = Nothing
    | even x = Just True
    | otherwise = Just False

Qual a saída para filterM g [1, 2, 3, 0, 4] e filterM g [1, 2, 3, 4]?

filterM g [1, 2, 3, 0, 4]

Saída:


Nothing

filterM g [1, 2, 3, 4]

Saída:


Just [2,4]

o Nothing indica que a lista é inválida e não deve ser processada.

E com essa função?

h :: Int -> Writer String Bool
h x | x == 0 = writer (True, "Invalid! ")
    | even x = writer (True, "Valid! ")
    | otherwise = writer (False, "Discarded!" )

Qual a saída para filterM h [1, 2, 3, 0, 4] e filterM h [1, 2, 3, 4]?

filterM h [1, 2, 3, 0, 4]

Saída:


WriterT (Identity ([2,0,4],"Discarded!Valid! Discarded!Invalid! Valid! "))

filterM h [1, 2, 3, 4]

Saída:


WriterT (Identity ([2,4],"Discarded!Valid! Discarded!Valid! "))

4.1 Monads

4.2 Para saber mais - I

Functors, Applicatives e Monads
[GH] 12
[SGS] 14
[ML] 11, 12

[GH] 14
[SGS] 13, 14, 15
[ML] 11
State IO e Leitura de Arquivos

5 Disclaimer

Estes slides foram preparados para os cursos de Paradigmas de Programação e Desenvolvimento Orientado a Tipos na UFABC.

Este material pode ser usado livremente desde que sejam mantidos, além deste aviso, os créditos aos autores e instituições.

Monads

1 Monads

1.1 Maybe

1.2 Monoid de Monad

1.3 Monads: Syntactic Sugar

2 SafeNum + Monad

2.1 Exercício 1

2.2 Resposta - Exercício 1

3 Monads e Efeitos

3.1 Parcialidade

3.2 Não-determinismo

3.3 Exceções: Either

3.4 Experiment no Repl.it

3.5 Efeitos Colaterais: Read Only

3.6 Experiment no Repl.it

3.7 Efeitos Colaterais: Write Only

3.8 Experiment no Repl.it

3.9 Efeitos Colaterais: Read and Write

3.10 Estado

3.11 Transformador de Estado

3.12 Applicative rlabel

3.13 Experiment no Repl.it

3.14 Efeitos Colaterais: IO

3.15 Exercício 2

3.16 Exercício 2 - Resposta

3.17 Exercício 3

3.18 Exercício 3 - Resposta

4 Funções de alta ordem para Monads

4.1 Monads

4.2 Para saber mais - I

5 Disclaimer

2 `SafeNum` + `Monad`

3.3 Exceções: `Either`