Applicatives e Traversable


Playlists

1 Applicative Functors

  • Ok, digamos que eu queira fazer:
> [1,2] + [3,4]
[4,5]
> (Just 3) + (Just 2)
Just 5
  • Idealmente teríamos:
fmap0 :: a -> f a
fmap1 :: (a -> b) -> f a -> f b
fmap2 :: (a -> b -> c) -> f a -> f b -> f c
fmap3 :: (a -> b -> c -> d) -> f a -> f b -> f c -> f d
  • Com isso poderíamos:
> fmap2 (+) [1,2] [3,4]
[4,5]
> fmap2 (+) (Just 3) (Just 2)
Just 5
  • Mas definir todas essas funções é um trabalho tedioso…

1.1 Applicative

  • Podemos resolver isso através do uso de currying:
pure   :: a -> f a
aplica :: f (a -> b) -> f a -> f b

fmap0 :: a -> fa
fmap0 = pure

fmap1 :: (a -> b) -> (f a -> f b)
fmap1 g x = aplica (pure g) x

fmap2 :: (a -> (b -> c)) -> (f a -> (f b -> f c))
fmap2 g x y = aplica (aplica (pure g) x) y
  • Este padrão é tão recorrente que ganhou um nome: Applicative Functor ou simplesmente Applicative, cuja classe de tipo é definida como:
class Functor f => Applicative f where
  pure  :: a -> f a
  (<*>) :: f (a -> b) -> f a -> f b
  • E com isso podemos fazer:
> pure (+) <*> [1,2] <*> [3,4] -- não dá esse resultado
[4,6]
> pure (+) <*> (Just 3) <*> (Just 2)
Just 5
  • O significado de pure nesse contexto é a de que estamos transformando uma função pura em um determinado contexto computacional (de computação não determinística, de computação que pode falhar, etc.)

1.2 Applicative Maybe

  • Para o tipo Maybe basta definirmos:
instance Applicative Maybe where
  pure             = Just
  Nothing  <*> _   = Nothing
  (Just g) <*> mx  = fmap g mx
  • Essas definições nos ajudam a definir um modelo de programação em que funções puras podem ser aplicadas a argumentos que podem falhar, sem precisar gerenciar a propagação do erro:
r1 = maybeDiv x y
r2 = maybeDiv y x

-- Se alguma divisão falhar, retorna Nothing
-- Não precisamos criar um maybeAdd!
somaResultados = pure (+) <*> r1 <*> r2
pure (+) <*> maybeDiv 1 0 <*> maybeDiv 0 1

Saída:


Nothing

1.3 Applicative List

  • Para as listas, o uso de applicative define como aplicar um operador em todas as combinações de elementos de duas listas:
instance Applicative [] where
  pure x    = [x]
  gs <*> xs = [g x | g <- gs, x <- xs]
  • Com isso temos:
pure (+1) <*> [1,2,3]

Saída:


[2,3,4]
pure (+) <*> [1] <*> [2]

Saída:


[3]
pure (*) <*> [1,2] <*> [3,4]

Saída:


[3,4,6,8]
pure (++) <*> ["ha","heh","hmm"] <*> ["?","!","."]

Saída:


["ha?","ha!","ha.","heh?","heh!","heh.","hmm?","hmm!","hmm."]

1.4 Computação não-determinística

  • Imagine que queremos fazer a operação x * y, mas tanto x quanto y são não-determinísticos, ou seja, podem assumir uma lista de possíveis valores.
  • Uma forma de tratar esse problema é através do Applicative listas que retorna todas as possibilidades:
pure (*) <*> [1,2,3] <*> [2,3]

Saída:


[2,3,4,6,6,9]
pure (*) <*> [1,2,3] <*> []

Saída:


[]
  • Uma outra interpretação para o Applicative de listas é a operação elemento-a-elemento pareados. Ou seja:
-- Não dá esse resultado. Veja ZipList.
> pure (+) <*> [1,2,3] <*> [4,5]
[5,7]
  • Como só pode existir uma única instância para cada tipo, criaram a ZipList que é uma lista que terá essa propriedade na classe Applicative:
import Control.Applicative
pure (+) <*> ZipList [1,2,3] <*> ZipList [4,5]

Saída:


ZipList {getZipList = [5,7]}

2 SafeNum + Applicative

A instância de Applicative para SafeNum é bem simples:

instance Applicative SafeNum where
  pure = SafeNum
  f <*> x = flatten $ fmap (`fmap` x) f
-- 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 a) = a
    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  -- SafeNum Int
      yx = safeDiv y x  -- SafeNum Int
  in
    flatten $ pure safeAdd <*> xy <*> yx

Será que dá pra fazer melhor?

3 Traversable

  • Imagine que temos uma sequência de aplicações de uma função g a ser aplicada na ordem:
g :: a -> Maybe a

[g x1, g x2, g x3]
  • Na avaliação preguiçosa, quando avaliarmos uma lista cada elemento será avaliado em ordem arbitrária (dependendo da função sendo avaliada).
  • Como a sequência é importante, não queremos continuar computando no caso de falhas.
  • Podemos construir uma lista de Applicative da seguinte forma:
pure (:) <*> g x1 <*>
   (pure (:) <*> g x2 <*>
      (pure (:) <*> g x3 <*> pure []))
  • Se uma aplicação falhar, não temos motivos para continuar computando, caso a aplicação g x2 falhe, podemos retornar Nothing imediatamente.
  • É possível generalizar essa função com:
-- sequencia de Applicatives
sequenceA :: (Applicative f) => [f a] -> f [a]
sequenceA []     = pure []
sequenceA (x:xs) = pure (:) <*> x <*> sequenceA xs
sequenceA [Just 3, Just 2, Just 1]

Saída:


Just [3,2,1]
sequenceA [Just 3, Nothing, Just 1]

Saída:


Nothing
sequenceA [[1,2,3],[4,5,6]]

Saída:


[[1,4],[1,5],[1,6],[2,4],[2,5],[2,6],[3,4],[3,5],[3,6]]
sequenceA [[1,2,3],[4,5,6],[3,4,4],[]]

Saída:


[]
  • Sequenciamento é útil quando queremos ter controle da ordem das operações e tais operações podem gerar efeitos colaterais ou falhar. Ex.:
    • Capturar caracteres do teclado
    • Backtracking

3.1 Traversable

Uma última classe que veremos no curso é a Traversable ou seja, tipos que podem ser mapeados:

class (Functor t, Foldable t) => Traversable t where
  traverse :: Applicative f =>
			    (a -> f b) -> t a -> f (t b)
  • Essa classe é útil quando, por exemplo, temos uma função que mapeia um tipo a para Maybe b e temos uma lista de a.
  • Nesse caso queremos retornar um Maybe [b] ao invés de [Maybe b]. Isso dá para ser feito utilizando o Applicative para listas:
class (Functor t, Foldable t) => Traversable t where
  traverse :: Applicative f =>
			    (a -> f b) -> t a -> f (t b)

instance Traversable [] where
  traverse g []     = pure []
  traverse g (x:xs) = pure (:) <*> g x <*> traverse g xs

Supondo a função:

dec :: Int -> Maybe Int
dec x | x <= 0    = Nothing
      | otherwise = Just (x - 1)
traverse dec [1,2,3]

Saída:


Just [0,1,2]
traverse dec [2,1,0]

Saída:


Nothing

3.2 Exercício 1

Escreva a instância de Traversable para Tree.

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

class (Functor t, Foldable t) => Traversable t where
   traverse :: Applicative f =>
			     (a -> f b) -> t a -> f (t b)

3.3 Exercício 1 - Resposta

Escreva a instância de Traversable para Tree:

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

class (Functor t, Foldable t) => Traversable t where
   traverse :: Applicative f =>
			     (a -> f b) -> t a -> f (t b)

instance Traversable Tree where
   traverse g (Leaf x)   = pure Leaf <*> g x
   traverse g (Node l r) =
	      pure Node <*> traverse g l <*> traverse g r

4 Folds

  • Relembrando na aula sobre Foldable criamos um tipo Fold:
{-# LANGUAGE ExistentialQuantification #-}

data Fold i o = forall m . Monoid m => Fold (i -> m) (m -> o)
  • Podemos criar uma instância de Functor:
instance Functor (Fold i) where
 fmap k (Fold toMonoid summarize) = Fold toMonoid (k . summarize)
  • E uma instância de Applicative:
instance Applicative (Fold i) where
 pure o = Fold (\_ -> ()) (\_ -> o)

 Fold toMonoidF summarizeF <*> Fold toMonoidX summarizeX = Fold toMonoid summarize
   where
     toMonoid i = (toMonoidF i, toMonoidX i)

     summarize (mF, mX) = summarizeF mF (summarizeX mX)
  • Com isso podemos combinar =fold=s da seguinte forma:
sum :: Num n => Fold n n
sum = Fold Sum getSum

length :: Num n => Fold i n
length = Fold (\_ -> Sum 1) getSum

average :: Fractional n => Fold n n
average = (/) <$> sum <*> length

Código no Repl.it

4.1 Para saber mais…

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.