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

Functors

Playlists

1 Functors

Functors são funções que fazem com que as funções de um certo tipo sejam aplicáveis a um tipo paramétrico contendo esse tipo.

Functors e teoria das categorias

Functors são morfismos que transformam os morfismos de uma categoria inteira (Tipos) em morfismos de outra ([], Maybe, …).
No Haskell o que temos são endofunctors.
Mais sobre isso no curso de teoria das categorias para programadores!

No Haskell um Functor é definido como uma classe de tipos:

class Functor f where
   fmap :: (a -> b) -> f a -> f b

Ou seja, se eu já tenho uma função $g : a \rightarrow b$, e tenho um tipo paramétrico f, eu posso aplicar a função g em f a para obter f b.

Em outras linguagens funcionais, e algumas imperativas, há uma operação chamada flat map. O f de fmap não tem nada a ver com flat e sim com Functor. Em breve veremos o equivalente ao flat map em outras linguagens.

Uma outra forma de entender Functor é como um tipo paramétrico f que armazena zero ou mais valores do tipo a, e que toda função a -> b pode ser mapeada para uma função f a -> f b:

class Functor f where
   fmap :: (a -> b) -> (f a -> f b)

A definição de fmap deve obedecer duas propriedades:

fmap id = id
fmap f . fmap g = fmap (f.g)

1.1 Functors de lista

Para as listas nós já temos o functor:

instance Functor [] where
  fmap = map

1.2 Functors de Maybe

Para o Maybe definimos da seguinte forma:

instance Functor Maybe where
  fmap _ Nothing =  Nothing
  fmap g (Just x) = Just (g x)

Agora podemos fazer:

> fmap chr Nothing
Nothing
> fmap chr (Just 65)
Just 'A'
> fmap (+1) (Just 65)
Just 66

Reforçando a ideia de promessa computacional, imagine que eu esteja aplicando a função chr em um valor proveniente de uma computação que pode falhar:

> x = (n + 36) `mod` y
> fmap chr x

Nesse caso, se a computação de x falhar, a função não será aplicada e o programa não termina com erro.

Vamos verificar se essa definição obedece as leis de Functor:

fmap id Nothing = id Nothing
Nothing = Nothing

fmap id (Just x) = id (Just x)
Just (id x) = Just x
Just x = Just x

Vamos verificar se essa definição obedece as leis de Functor:

(fmap f . fmap g) Nothing = fmap (f.g) Nothing
fmap f (fmap g Nothing) = Nothing
fmap f Nothing = Nothing
Nothing = Nothing

Vamos verificar se essa definição obedece as leis de Functor:

(fmap f . fmap g) (Just x) = fmap (f.g) (Just x)
fmap f (fmap g (Just x)) = Just ((f.g) x)
fmap f (Just (g x)) = Just ((f.g) x)
Just ((f.g) x) = Just ((f.g) x)

1.3 Functors de Árvores

Definimos um Functor de Árvores como:

instance Functor Tree where
  fmap g (Leaf x)   = Leaf (g x)
  fmap g (Node l x r) = Node (fmap g l) (g x) (fmap g r)

> fmap (*2) (Node (Leaf 1) 2 (Node (Leaf 3) 4 (Leaf 5))
(Node (Leaf 2) 4 (Node (Leaf 6) 8 (Leaf 10))

1.4 Operador Functor

Podemos utilizar o operador (<$>) no lugar do fmap:
O operador (<$>) nada mais é que a definição de fmap infixa

> (+1) <$> [1,2,3]
[2,3,4]
> (+1) `fmap` [1,2,3]
[2,3,4]
-- Para o Functor [] é o mesmo que
> (+1) `map` [1,2,3]
[2,3,4]
> map (+1) [1,2,3]
[2,3,4]

2 Definindo Functors automaticamente

Vamos definir alguns Functors fundamentais de forma similar ao que foi feito na aula sobre Álgebra de Tipos.
Com isso podemos construir definições de Functor automaticamente através de um processo algébrico.

Pensando em um Functor como um container, a definição mais simples é aquela que não armazena nada:

data Const b a = Const b

instance Functor (Const b) where
  fmap _ (Const x) = Const x

De forma similar, podemos definir um Functor que armazena apenas um único elemento:

data Identity a = Identity a

instance Functor Identity where
  fmap f (Identity x) = Identity (f x)

Se temos um Functor que não armazena nada, e outro que armazena um único elemento, podemos definir um que armazena zero ou um elementos?

data NadaOuUm a = Either (Const () a) (Identity a)

instance Functor NadaOuUm where
  fmap f (Left x) = Left   (fmap f x)
  fmap f (Right x) = Right (fmap f x)

Com a definição dos Functors de Const e Identity, isso funciona!

Essa definição é análoga a definição do Functor Maybe!

data NadaOuUm a = Either (Const () a) (Identity a)

instance Functor NadaOuUm where
  fmap f (Left x) = Left   (fmap f x)
  fmap f (Right x) = Right (fmap f x)

Em muitos casos o compilador pode definir a instância de Functor automaticamente:

{-# LANGUAGE DeriveFunctor #-}

data NadaOuUm a = Either (Const () a) (Identity a)
                     deriving Functor

3 Aritmética segura com Functor

> 4 `div` 0
*** Exception: divide by zero
> maxBound :: Int
9223372036854775807
> (maxBound :: Int) + 1
-9223372036854775808

Inteiros têm precisão de 64 bits.
Caso qualquer operação resulte em um número que exija mais do que 64 bits, ocorre overflow e o número “flipa”
Checar isto a cara operação pode ser uma tarefa muito tediosa. Vamos criar uma função!

Considere o seguinte tipo:

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

Este tipo serve para armazenar valores de números de maneira segura
Os valores possíveis são:
- SafeNum a - Um número propriamente dito
- NegInf e PosInf - utilizado em caso de overflow
- NaN - Not a Number: utilizado em caso de operações aritméticas inválidas ($\sqrt{-1}$, divisão, por 0, …)
Podemos então criar uma função que dado dois inteiros devolva uma versão segura do valor

safeAdd :: Int -> Int -> SafeNum Int
safeAdd x y
  | signum x /= signum y = SafeNum z
  | signum z /= signum x = if signum x > 0
                           then PosInf
                           else NegInf
  | otherwise = SafeNum z
  where z = x + y

safeDiv :: Int -> Int -> SafeNum Int
safeDiv 0 0 = NaN
safeDiv x 0
  | x > 0     = PosInf
  | otherwise = NegInf
safeDiv x y = SafeNum $ x `div` y

E a partir daí podemos fazer:

> maxBound `safeAdd` 1
PosInf
> minBound `safeAdd` (-1)
NegInf
> 0 `safeDiv` (-1)
SafeNum 0
> (-1) `safeDiv` 0
NegInf
> 0 `safeDiv` 0
NaN

Porem agora temos um problema. Queremos fazer: negate (x + y)

> x = 5
> y = 7
> z = x `safeAdd` y
> :t z
z :: SafeNum Int
> :t negate
negate :: Num a => a -> a

Temos um valor dentro de um tipo paramétrico e desejamos aplicar uma função ao valor que ele contém!

Com um problema um pouquinho mais elaborado, a quantidade de boilerplate necessária para fazer uma operação que dependa de valores seguros é inaceitável. 🙄

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

Dá para fazer melhor?

Sim! Podemos transformar um SafeNum em um functor e usando fmap ter a certeza que não teremos problemas durante a execução.

Se SafeNum fosse um functor, poderíamos fazer:

> z = 5 `safeAdd` 7
> :t z
z :: SafeNum Int

> :t negate
negate :: Num a => a -> a
> :t (<$>)
(<$>) :: Functor f => (a -> b) -> f a -> f b

> negate <$> z
SafeNum (-12)
> negate <$> safeDiv 10 0
PosInf

Só falta® implementar uma instância de functor para SafeNum

3.1 Exercício 1

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

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

3.2 Resposta - Exercício 1

boxedCoerce :: SafeNum a -> SafeNum b
boxedCoerce NaN = NaN
boxedCoerce NegInf = NegInf
boxedCoerce PosInf = PosInf
boxedCoerce _ = error "Não deveria ser usado para valores safe"

instance Functor SafeNum where
  fmap f (SafeNum n) = SafeNum $ f n
  fmap _ x = boxedCoerce x

flatten :: SafeNum (SafeNum a) -> SafeNum a
flatten (SafeNum sn) = sn
flatten v = boxedCoerce v

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

Melhorou, mas ainda está ruim…

3.3 Para saber mais…

4 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.