Playlists
data Expr = Val Int
| Add Expr Expr
| Sub Expr Expr
| Mul Expr Expr
| Div Expr Expr
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)
> eval (Div (Val 1) (Val 0))
*** Exception: divide by zero
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
> eval (Div (Val 1) (Val 0))
Nothing
pure maybeDiv <*> eval x <*> eval y
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.
case of
:vincular :: Maybe a -> (a -> Maybe b) -> Maybe b
vincular mx g = case mx of
Nothing -> Nothing
Just x -> g x
mx
ao argumento da função g
.bind
e definido como:(>>=) :: Maybe a -> (a -> Maybe b) -> Maybe b
Qualquer semelhança com o logo de Haskell, é mera coincidência 😄
return
(>>=)
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_).
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
(>>=)
tem a seguinte estrutura:m1 >>= \x1 ->
m2 >>= \x2 ->
...
mn >>= \xn ->
f x1 x2 ... xn
Nothing
, []
, etc.)do x1 <- m1
x2 <- m2
...
xn <- mn
f x1 x2 ... xn
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
class Applicative m => Monad m where
return :: a -> m a
(>>=) :: m a -> (a -> m b) -> m b
return = pure
bind
ela redefine a função pure
com o nome
de return
.Monad Maybe
mas podemos deixá-la
mais clara utilizando Pattern Matching:instance Monad Maybe where
Nothing >>= _ = Nothing
(Just x) >>= f = f x
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
Monad
para o tipo SafeNum
.data SafeNum a = NaN | NegInf| PosInf | SafeNum a deriving Show
data SafeNum a = NaN | NegInf| PosInf | SafeNum a deriving Show
instance Monad SafeNum where
(SafeNum v) >>= f = f v
v >>= _ = boxedCoerce v
Existe um limite do quanto nosso programa pode ser puro!
As funções impuras são necessárias para diversas ocasiões conforme apontado por Eugenio Moggi:
f :: a -> Bool
retorna True
, False
ou _|_
.
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:
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:
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)
pares :: [a] -> [b] -> [(a,b)]
pares xs ys = xs >>= \x ->
ys >>= \y ->
return (x,y) -- [(x,y)]
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)]
pares xs ys = [(x,y) | x <- xs, y <- ys]
== do x <- xs
y <- ys
return (x,y)
Either
exceções, podemos utilizar o Maybe
.
na avaliação das funções, mas não diz qual foi ele.
Maybe
e permite reportaro ponto que ocorreu a falha é o Either
:
data Either a b = Left a | Right b
Left
como o log do erro e Right
como o valor esperado, caso tudo dê certo.
instance Functor (Either a) where
fmap f (Left x) = Left x
fmap f (Right x) = Right (f x)
Maybe
, a instância de Applicativepropaga 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)
Maybe
:instance Monad (Either a) where
(Left x) >>= f = Left x
(Right x) >>= f = f x
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
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
postTweet, valida
tem tipos
String -> ()
e String -> Bool
, mas foram embelezadas para
receber também as configurações globais.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
data Reader e a = Reader (e -> a)
postTweet :: String -> Reader Config ()
valida :: String -> Reader Config Bool
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)
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
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)
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)
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
isEven x = even x
not' b = not b
isOdd x = (not' . isEven) x
> isOdd 3
(True, " isEven not' ")
isEven x = (even x, " isEven ")
not' b = (not b, " not' ")
isOdd x = (not' . isEven) x -- ops
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)
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)
m = (, String)
, temos a -> m b
🤔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
.
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 🤔
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)
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.
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)
isOddW'
com o operadorde composição de Monads >=>
:
-- (>=>) :: (a -> m b) -> (b -> m c) -> (a -> m c)
isOddW' :: Integer -> Writer String Bool
isOddW' = (isEvenW' >=> notW')
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)
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?
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)
Tree a -> Int -> (Tree Int, Int)
t -> (a -> (b, a))
Reader
é a -> b
, o tipo Writer
é (a, b)
:t -> (a -> (b, a))
t -> Reader a (Writer a b)
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)
Figure 1: Transformador de estado
Figure 2: Transformador de estado
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 -> b
na parte do valor do resultado de um
ST a
, transformando-o efetivamente em um tipo ST b
:Figure 3: Functor ST
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'))
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:
Figure 4: pure ST
Então definimos:
instance Applicative (State s) where
-- pure :: a -> State s a
pure x = State (\s -> (x, s))
(<*>)
define a sequência de mudança de
estados pelos transformadores e a combinação dos valores finais
como um resultado único:Figure 5: <*> ST
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
sInc
é um transformador de estados que incrementa um contador,
então:
pure Leaf
é aplicado no estado atual s
retornando ele mesmo
(pois é puro)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:
Figure 6: Monad ST
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.
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))
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)
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.
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)
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'
Escreva a função putStrLn
usando Applicative.
putStrLn :: String -> IO ()
putStrLn xs = do putStr xs
putChar '\n'
putStrLn :: String -> IO ()
putStrLn xs = do sequenceA [putStr' xs, putChar 'n']
return ()
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)
conv :: Char -> Maybe Int
conv c | isDigit c = Just (digitToInt c)
| otherwise = Nothing
mapM
para obter:> mapM conv "1234"
Just [1,2,3,4]
> mapM conv "12a4"
Nothing
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)
> 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!
[]
/ \
[1] []
/ \ / \
[1,2] [1] [2] []
...
filter
seleciona elementos de uma listafilterM
seleciona possíveis eventos de uma sequência de computaçõesf x | even x = [False]
| otherwise = [True, False]
Qual a saída para filterM f [1, 2, 3]
?
filterM f [1, 2, 3]
Saída:
g x | x == 0 = Nothing
| even x = Just True
| otherwise = Just False
filterM g [1, 2, 3, 0, 4]
e filterM g [1, 2, 3, 4]
?filterM g [1, 2, 3, 0, 4]
Saída:
filterM g [1, 2, 3, 4]
Saída:
Nothing
indica que a lista é inválida e não deve ser processada.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:
filterM h [1, 2, 3, 4]
Saída:
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.