Exemplos de Mônadas

Esse post é baseado no livro Teoria das Categorias para Programadores, de Bartosz Milewski.

1 Monads e Efeitos

Uma das críticas frequentes ao Haskell é o fato de forçar a pureza das funções, o que teoricamente tornaria a linguagem por si só inútil na prática. Embora seja possível minimizar a quantidade de funções impuras de um programa, elas são necessárias pelo menos para a leitura dos dados de entrada e saída dos resultados. Imagine um programa que apenas calcula o seno de \(3\) mas nunca apresenta o resultado!

Algumas das utilidades de funções impuras conforme listado no artigo de Eugenio Moggi:

  • Parcialidade: quando a computação de uma função pode não terminar.

  • Não determinismo: quando a computação pode retornar múltiplos resultados dependendo do caminho da computação.

  • Efeitos colaterais: quando a computação acessa ou altera um estado como

    • Read-only, leitura do ambiente
    • Write-only, escrita de um log
    • Read/Write
  • Exceções: funções parciais que podem falhar.

  • Continuações: quando queremos salvar o estado de um programa e retomá-lo sob demanda.

  • Entrada e Saída Interativa.

Todos esses efeitos podem ser tratados com embelezamento de funções e uso de Monads conforme veremos em seguida.

1.1 Parcialidade

A parcialidade ocorre quando temos uma função que pode não terminar. Para lidar com isso, o Haskell inclui em todos os tipos o valor bottom \(\bot\), com isso uma função f :: a -> Bool pode retornar True, False ou _|_. Uma vez que Haskell dá preferência para avaliação preguiçosa, podemos compor funções que retornam \(\bot\) contanto que nunca seja necessário avaliá-lo.

Por conta desse valor não-terminável falamos da categoria \(\mathbf{Hask}\) ao invés de \(\mathbf{Set}\), por conta disso \(\mathbf{Hask}\) não é realmente uma categoria, pois a função identidade não funciona com o bottom. A validade de assumir que \(\mathbf{Hask}\) forma uma categoria divide opiniões de especialistas da linguagem.

1.2 Não-determinismo

Se uma função pode retornar diferentes resultados, dependendo de certos estados internos, ela é chamada de não-determinística. Por exemplo, a saída da função getDate depende do dia atual, assim como random depende do estado atual do gerador de números aleatórios. Uma função que avalia a melhor jogada de um jogo de xadrez deve levar em conta todas as possibilidades de jogadas do seu adversário.

Esse tipo de computação pode ser representada como uma lista contendo todas as possibilidades de saída. Como no Haskell podemos trabalhar com listas infinitas (e a avaliação delas é preguiçosa), podemos usar o Monad [] para representar computações não-determinística.

Uma vez que uma função retorna uma lista, se quisermos apenas um elemento, podemos pegar o primeiro da lista e ignorar todo o restante (que não será avaliado). A instância Monad para listas é dado pela função join:

instance Monad [] where
  join     = concat
  return x = [x]

Essa definição é suficiente para o operador bind, que é definido como as >> k = concat (fmap k as)=. Em versões futuras do C++ teremos o range comprehensions que implementa uma lista preguiçosa similar ao Haskell:

template<typename T, typename Fun>
static generator<typename std::result_of<Fun(T)>::type>
bind(generator<T> as, Fun k)
{
    for (auto a : as) {
	for (auto x : k(a) {
	    __yield_value x;
	}
    }
}

E no Python, utilizamos os generators:

def bind(xs, k):
    return (y for x in xs for y in k(x))

Um exemplo interessante da expressividade do Monad lista no Haskell é o cálculo de todas as triplas pitagóricas, que pode ser implementada como:

guard :: Bool -> [()]
guard True  = [()]
guard False = []

triples = do z <- [1..]
	     x <- [1..z]
	     y <- [x..z]
	     guard (x^2 + y^2 == z^2)
	     return (x, y, z)

Reescrevendo utilizando bind percebemos melhor o que ele está fazendo:

[1..] >>= \z  -> [1..z] >>=
	  \x  -> [x..z] >>=
	  \y  -> guard (x^2 + y^2 == z^2) >>=
	  \() -> return (x, y, z)

triples = concat (fmap fz [1..])
fz      = concat (fmap fx [1..z])
fx      = concat (fmap fy [x..z])
fy      = concat (fmap f() guard (x^2 + y^2 == z^2))
f()     = return (x, y, z)

As funções lambdas selecionam um valor para \(x, y, z\) das listas correspondentes. A função fy ou retorna uma lista vazia ou uma lista com um único elemento, dependendo do resultado da expressão booleana. Para o caso de retornar a lista vazia, o bind seguinte aplicará fmap f() em uma lista vazia, retornando a própria lista vazia. Caso retorne a lista [()], fmap retornará [[(x,y,z)]] que será transformado em [(x,y,z)] pela função concat.

O Haskell também provê um syntactic sugar específico para listas, e essa mesma lista pode ser reescrita como:

triples = [(x,y,z) | z <- [1..]
		   , x <- [1..z]
		   , y <- [x..z]
		   , x^2 + y^2 == z^2]

No Python podemos fazer uma construção parecida como:

def triples(n):
  return ( (x,y,z) for z in range(1, n+1)
		   for x in range(1, z+1)
		   for y in range(x, z+1)
		   if (x**2 + y**2 == z**2))

1.3 Read-only

A leitura de um estado externo, seja proveniente da leitura de um arquivo, ou de um banco de dados ou qualquer ambiente genérico e pode ser interpretado como uma função que recebe não só o argumento original como um argumento extra codificando o ambiente e, ou seja, uma função f :: a -> b é embelezada para f :: (a, e) -> b.

Ao aplicar o currying nessa função temos que ela é equivalente a f :: a -> (e -> b), ou seja, f :: a -> Reader e b. O Monad Reader faz o papel de manipulação de estados somente-leitura e vem equipado com as funções auxiliares runReader, que executa o Reader para um ambiente e, e ask que recupera o ambiente:

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

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

ask :: Reader e e
ask = (Reader id)

Note que a definição do Reader e todas as funções que a utilizam são essencialmente puras, dada uma tabela grande o suficiente poderíamos memoizar todas as entradas e saídas possíveis para todo estado possível do ambiente e. A definição de Monad para o Reader e é:

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

  return a = Reader (\e -> a)

O bind do Reader e primeiro executa ra no ambiente atual e, capturando o resultado puro a. Em seguida, aplica a função k em a que retorna um Reader e b. Finalmente, executa esse Reader no ambiente passado como argumento. A função return simplesmente cria uma função constante que sempre retorna um valor a para qualquer ambiente (verifique a propriedade ra >> return = ra=).

Imagine a situação em que temos um algoritmo que utiliza uma estrutura de configuração (somente leitura) que armazena seus parâmetros e chama funções auxiliares que também utilizam dessa configuração:

data Config = Conf { alg :: String
		   , thr :: Double
		   , it  :: Int
		   }

go :: Int -> [Double] -> [Double]
go _ []     = []
go 0 xs     = xs
go i (x:xs) = (i' * x) : go (i-1) xs
  where i' = fromIntegral i

filterLess thr xs = filter (<thr) xs

f2 :: Config -> [Double] -> [Double]
f2 cfg xs = f3 cfg $ filterLess (thr cfg) xs

f3 :: Config -> [Double] -> [Double]
f3 cfg xs = go (it cfg) xs

algorithm :: Config -> [Double] -> [Double]
algorithm cfg xs | alg cfg == "f2" = f2 cfg xs
		 | otherwise       = f3 cfg xs

Para evitar ter que passar o parâmetro de configuração para todas as funções (o que pode ocasionar em bugs ao atualizar o código), podemos definir cfg como uma variável global acessível por todas as funções.

Porém, se precisarmos carregar essas configurações de um arquivo externo, não podemos deixá-la como global no Haskell. Nas linguagens que permitem o uso de variáveis globais, todas as funções que utilizam a estrutura de configuração em funções se tornariam impuras.

Utilizando o Reader Monad podemos resolver essa situação da seguinte forma:

askFor f = fmap f ask

f3 :: [Double] -> Reader Config [Double]
f3 xs = askFor it >>= runGo
  where runGo t = return (go t xs)

f2 :: [Double] -> Reader Config [Double]
f2 xs = askFor thr >>= gof3
  where gof3 t = f3 (filterLess t xs)


algorithm :: [Double] -> Reader Config [Double]
algorithm xs = askFor alg >>= choice
  where choice a | a == "f2" = f2 xs
		 | otherwise = f3 xs

Nesse código o nosso ambiente é caracterizado por um tipo Config, que armazena a configuração do algoritmo. O comando fmap f ask cria uma função que recebe um Config e retorna o parâmetro especificado por f. O segundo parâmetro do operador bind é uma função que recebe um f Config e retorna o resultado esperado do tipo [Double]. Com isso, o operador bind recebe uma função Config -> f Config e uma função f Config -> [Double] e transforma em uma função Config -> [Double]. Utilizando do-notation o mesmo programa fica:

f3 :: [Double] -> Reader Config [Double]
f3 xs = do
  t <- askFor it
  return (go t xs)

f2 :: [Double] -> Reader Config [Double]
f2 xs = do
  t  <- askFor thr
  f3 (filterLess t xs)

algorithm :: [Double] -> Reader Config [Double]
algorithm xs = do
  alg <- askFor alg
  if alg == "f2"
  then f2 xs
  else f3 xs

As instruções fmap f ask recupera um elemento da nossa configuração. Notem, porém, que a variável contendo a configuração não é passada diretamente para nenhum das funções do algoritmo, qualquer alteração que seja feita nessa estrutura ou no uso dela, não criará um efeito cascata de alterações no código. Para executar o algoritmo precisamos fazer runReader (algorithm xs) c, sendo c a variável contendo a configuração.

Em Python podemos fazer uso de funções de alta-ordem para obter algo similar, só que com o ônus de que o arquivo de configuração tem que ser passado explicitamente ao chamar f3 dentro de f2 em nosso exemplo:

from collections import namedtuple

'''
Config struct and functions
'''
Conf = namedtuple('Conf', ['alg', 'thr', 'it'])

def alg(c):
  return c.alg
def thr(c):
  return c.thr
def it(c):
  return c.it

'''
Reader Monad class
'''
class Reader():
  # Reader e a
  def __init__(self, fun = None):
    self.r = fun

  def run(self, e):
    return self.r(e)

  # (a -> b) -> Reader e a -> Reader e b
  def fmap(self, f):
    return Reader(lambda e: f(self.r(e)))

  def unit(self, x):
    return Reader(lambda e: x)

  # Reader e a -> (a -> Reader e b) -> Reader e b
  def bind(self, fab):
    def f(e):
      a = self.r(e)
      rb = fab(a)
      return rb.run(e)
    return Reader(f)

def ask(e):
  return e

def askFor(f):
  return Reader(ask).fmap(f)

'''
Example of use
'''

def go(it, xs):
  ys = []
  for x in xs:
    ys.append(it*x)
    it = it - 1
  return ys

def f3(xs):
  # ask for it and pass to 'runGo'
  runGo = lambda t: Reader().unit(go(t, xs))
  return (askFor(it)
	  .bind(runGo))

def f2(xs):
  # ask for a thr and pass to 'gof3'
  gof3 = lambda t: f3(filter(lambda x: x<t, xs))
  return (askFor(thr)
	  .bind(gof3))

def algorithm(xs):
  f = {"f2" : f2, "f3" : f3}
  choice = lambda algo: f[algo](xs)
  return (askFor(alg)
	  .bind(choice))

c = Conf("f2", 2.5, 5)
print(algorithm(range(1,11))
      .run(c))

1.4 Write-only

Analogamente, podemos definir um estado Write-only como nosso Monad Writer equipado com uma função runWriter e a função tell:

data Writer w a = Writer (a, w)

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

tell :: w -> Writer w ()
tell s = Writer ((), s)
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 `mappend` w')

  return a = Writer (a, mempty)

Motivamos o uso do Writer Monad com a implementação de um traço de execução:

notW :: Bool -> Writer Bool
notW b = (b, "not")

is_even :: Int -> Writer Bool
is_even x = (x `mod` 2 == 0, "even")

is_odd :: Int -> Writer Bool
is_odd = is_even >=> notW

Podemos generalizar ainda mais ao utilizar nossa função tell:

trace :: Int -> Writer String Bool
trace x = do
  tell "even"
  b <- return (even x)
  tell "not"
  return (not b)

Ou também:

trace2 :: Int -> Writer String Bool
trace2 x = (evenW >=> notW) x
  where
    evenW :: Int -> Writer String Bool
    evenW x = tell "even" >> return (even x)

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

Veja que dessa forma, a função tell pode transformar uma função a -> b para a -> Writer s b automaticamente, reduzindo as alterações necessárias em nosso programa. Para completude, reproduzimos os códigos equivalentes em C++ e Python:

// C++
template<class A>
Writer<A> identity(A x) {
    return make_pair(x, "");
}

auto const compose = [](auto m1, auto m2) {
    return [m1, m2](auto a) {
	auto p1 = m1(a);
	auto p2 = m2(p1.first);
	return make_pair(p2.first, p1.second + p2.second);
    };
};

Writer<bool> not(bool b) {
    return make_pair(!b, "not ");
}

Writer<bool> is_even(int x) {
    return make_pair(x%2==0, "even ");
}

Writer<bool> is_odd(int x) {
    return compose(is_even, not)(x);
}
# Python
def id_writer(x):
    return Writer(x, "")

def compose_writer(m1, m2):
    def f(a):
	b, s1 = m1(a)
	c, s2 = m2(b)
	return Writer(c, s1+s2)
    return f

def not(b):
    return (not b, "not")

def is_even(x):
    return (x%2==0, "even")

def is_odd(x):
    return compose_writer(is_even, not)(x)

1.5 State

Um estado simplesmente é um ambiente \(e\) que permite leitura e escrita, ou seja, é a combinação dos Monads Reader e Writer. Uma função f :: a -> b é embelezada para f :: (a, s) -> (b, s), e utilizando currying temos f :: a -> (s -> (b, s)):

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

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

get :: State s s
get = State (\s -> (s, s))

put :: s -> State s ()
put s' = State (\s -> ((), s'))

Com isso temos a capacidade de ler ou alterar um estado. A instância de Monad nesse caso fica muito parecida com o Monad Reader, exceto que tomamos o cuidado de passar o novo estado para o segundo runState:

instance Monad (State s) where
  -- (State s a) -> (a -> State s b) -> (State s b)
  sa >>= k = State (\s -> let (a, s') = runState sa s
			  in runState (k a) s')

  return a = State (\s -> (a, s))

Uma aplicação desse Monad é na manipulação de números aleatórios em que queremos que o estado do gerador seja atualizado a cada chamada da função random. Vamos exemplificar com uma função que alterar uma lista de Bool, invertendo cada um de seus elementos, caso um certo valor aleatório seja < 0.3:

randomSt :: (RandomGen g) => State g Double
randomSt = state (randomR (0.0, 1.0))

mutation :: [Bool] -> State StdGen [Bool]
-- se a lista estiver vazia, nada a fazer
mutation [] = return []

mutation (b:bs) = do
    -- aplica o algoritmo no restante da lista,
    -- o estado atual do gerador é passado implicitamente
    -- para a função
    bs' <- mutation bs

    -- sorteia um valor aleatório e altera de acordo
    p   <- randomSt
    if p < 0.3
    then return (not b : bs')
    else return (b : bs')

Alternativamente, sem o do-notation ficaria como:

mutation (b:bs) = (mutation >=> choice) bs
  where
     choice bs' = randomSt >>= concat bs'
     concat bs' p = if p < 0.3
		    then return (not b : bs')
		    else return (b : bs')

A chamada da função mutation bs gera um novo estado State StdGen [Bool] que é passado para a função choice. Essa função recebe a lista de Bool, gera um número aleatório e chama concat para então retornar a nova lista com os elementos alterados de acordo. E uma terceira opção:

rule :: Double -> State StdGen (Bool -> Bool)
rule p = if p < 0.3 then return not else return id

mutatePoint :: State StdGen (Bool -> Bool)
mutatePoint = randomSt >>= rule

mutation'' :: [Bool] -> State StdGen [Bool]
mutation'' bs = state (\s -> (zipWith ($) (fst $ runState fs s) bs, s))
  where fs = sequence [mutatePoint | _ <- bs]

O equivalente desse código em Python fica:

import random

class State:
  # State s -> (a, s)
  def __init__(self, f = None):
    self.r = f

  def run(self, s):
    return self.r(s)

  def unit(self, x):
    return State(lambda s: (x, s))

  def bind(self, k):
    def f(s):
      (a, sn) = self.run(s)
      return k(a).run(sn)
    return State(f)


getSt = State(lambda s: (s, s))
setSt = State(lambda s: (None, s))

def mutation(bs):
  if len(bs)==0:
    return State().unit([])

  b = bs.pop()

  myRandST = State(myRand)

  def ifthenelse(bsm, p):
    if p < 0.3:
      return State().unit([not b] + bsm)
    else:
      return State().unit([b] + bsm)

  return (mutation(bs)
	  .bind(lambda bsm: myRandST
			    .bind(lambda p: ifthenelse(bsm, p))
	       )
	 )

def myRand(s):
  random.setstate(s)
  x = random.random()
  return x, random.getstate()

print(mutation([True, True, False, True]).run(random.getstate())[0])

1.6 Exceções

O tratamento de exceções é necessário quando uma função é parcial e pode falhar, por exemplo quando faz o processo de divisão em um valor que pode ser igual a zero. A forma mais simples de tratar exceções no Haskell é através do Monad Maybe em que uma computação que falha é sinalizada com o valor Nothing:

instance Monad Maybe where
  Nothing >>= k = Nothing
  Just a  >>= k = k a
  return a = Just a

Vimos um exemplo anteriormente em que a composição de duas funções que podem falhar não dá continuidade no processamento caso a primeira falhe:

safeRoot :: Double -> Maybe Double
safeRoot x | x < 0     = Nothing
	   | otherwise = Just (sqrt x)

safeReciprocal:: Double -> Maybe Double
safeReciprocal 0 = Nothing
safeReciprocal x = Just (1.0 / x)

sequencia x = (safeReciprocal x) >>= safeRoot
-- ou sequencia = safeReciprocal >=> safeRoot

Em C++ e Python isso fica:

//C++
#include <iostream>
#include <cmath>
#include <tuple>
#include <experimental/optional>

using namespace std;
using namespace experimental;

optional<double> safe_root(double x) {
    if (x >= 0) return optional<double>{sqrt(x)};
    else return optional<double>{};
}

optional<double> safe_reciprocal(double x) {
    if (x != 0) return optional<double>{1.0/x};
    else return optional<double>{};
}

auto const fish = [](auto f, auto g) {
    return [f, g](double x) {
	auto z = f(x);
	if (z) return g(z.value());
	else return z;
    };
};

auto sequencia = fish(safe_reciprocal, safe_root);
# Python
from math import sqrt

def safe_root(x):
    if x>=0:
	return sqrt(x)
    else:
	return None

def safe_reciprocal(x):
    if x!=0:
	return 1.0/x
    else:
	return None

def fish(f, g):
    def h(x):
	z = f(x)
	if z is None:
	    return z
	else:
	    return g(z)
    return h

sequencia = fish(safe_root, safe_reciprocal)

1.7 Continuation

O Continuation-passing Style (CPS) é um estilo de programação em que o fluxo de controle se torna explícito através de uma função de continuação. Por exemplo, uma função que recebe dois valores numéricos e retorna o dobro da soma deles:

def soma(x, y):
    return 2*(x+y)

se tornaria:

def soma(x, y, k):
    return k(x+y)

def dobra(x, k):
    return k(2*x)

g = lambda x: dobra(x, print)
soma(2, 3, g)
soma x y k = k (x+y)
dobra x k  = k (2*x)

main = soma 2 3 (\g -> dobra g print)

Uma das vantagens desse estilo é a de transformar todo retorno de função em uma execução caudal, levando a otimizações de funções não caudais de forma mais natural. Por exemplo, considere a versão recursiva de Fibonacci (extraído de resposta do stackoverflow):

def fib(n):
    if n<=1:
	return n
    return fib(n-1) + fib(n-2)
fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)

No estilo CPS essa função seria reescrita como:

def fib(n, k):
    if n<=2:
	return k(n)

    def g(x):
	return fib(n-2, lambda y: k(x+y))

    return fib(n-1, g)
fib 0 k = k 0
fib 1 k = k 1
fib n k = fib (n-1) d
	   where g x = fib (n-2) (\y -> k (x+y))

Notem que essa cadeia de funções lembra o uso de bind para sequenciamento de operações, que teria um bloco do equivalente a:

fib 0 = return 0
fib 1 = return 1
fib n = do x <- fib (n-1)
	   y <- fib (n-2)
	   return (x+y)

Essa construção pode ser facilmente otimizada pelo compilador e transformada internamente em =goto=s.

Outra aplicação de continuação ocorre quando temos uma função que pode ficar suspensa por um momento aguardando o retorno de uma thread ou a requisição de novos elementos para então resumir sua operação. Podemos ainda pensar em múltiplas funções de continuação para tratar casos de exceções:

fat n k h | n < 0     = h "numero negativo"
	  | n == 0    = k 1
	  | otherwise = fat (n-1) (\x -> k (n*x)) h

main = do
  fat (-1) print print
  fat 3 print print

Esse tipo de construção é caracterizada por uma função handler (geralmente chamada k) que executa a ação e retorna o resultado da computação r:

data Cont r a = Cont ((a -> r) -> r)

runCont :: Cont r a -> (a -> r) -> r
runCont (Cont k) h = k h

A instância Monad para o Cont fica (contraste com nossa definição CPS de fibonacci):

instance Monad (Cont r) where
    ka >>= kab = Cont (\hb -> runCont ka (\a -> runCont (kab a) hb))
    return a   = Cont (\ha -> ha a)

A instância de return simplesmente cria uma função que recebe um handler e aplica esse handler no valor a. O bind cria uma função que recebe uma função de continuação hb, executa a função ka em uma função que recebe um tipo a e retorna a execução de a transformado em b, via kab com a função hb. Basicamente, ele cria a continuação de ka.

Nossos dois exemplos em Haskell ficam:

soma :: Int -> Int -> (Cont r Int)
soma x y = return (x+y)

dobra :: Int -> (Cont r Int)
dobra x = return (2*x)

runCont (soma 2 3 >>= dobra) print


fib :: Int -> (Cont r Int)
fib 0 = return 0
fib 1 = return 1
fib n = do x <- fib (n-1)
	   y <- fib (n-2)
	   return (x+y)

runCont (fib 6) print

A tradução de soma 2 3 >> = dobra se torna:

Cont (\hb -> runCont (soma 2 3) (\a -> runCont (dobra a) hb)
= Cont (\hb -> runCont (Cont (\ha -> ha (2 + 3)) (\a -> runCont (Cont (\ha -> ha (2*a))) hb)
= Cont (\hb -> (\ha -> ha (2 + 3)) (\a -> runCont (Cont (\ha -> ha (2*a))) hb)
= Cont (\hb -> ((\a -> runCont (Cont (\ha -> ha (2*a))) hb) (2 + 3))
= Cont (\hb -> (\ha -> ha (2*(2+3))) hb)
= Cont (\hb -> hb (2*(2+3))))

Aplicando print:

runCont (Cont (\hb -> hb (2*(2+3))))) print
= (\hb -> hb (2*(2+3))) print
= print (2*(2+3))

Um uso interessante do Cont Monad é a definição de um SAT solver:

sat n = runCont $ sequence $ replicate n $ Cont $ \k -> k $ k True

Dado um número de variáveis n e uma função f :: [Bool] -> Bool ele retorna True se a expressão booleana sempre for verdadeira. A primeira parte importante é a definição da função:

e :: (Bool -> Bool) -> Bool
e k = (k True) || (k False)

que faz um ou lógico da aplicação da função Bool -> Bool nos valores True e False. Sabemos que só existem \(4\) definições para essa função:

k b = True
k b = False
k b = b
k b = not b

A única alternativa em que ela retorna False é em k b = False. Essa função é utilizada para construir um Cont Monad do tipo Cont Bool Bool. A função replicate n cria uma lista de tamanho n do segundo argumento, então ela cria uma lista [Cont Bool Bool]. O próximo passo é o uso da função sequence que tem assinatura (simplificada) sequence :: Monad m => [m a] -> m a, no nosso caso transforma nosso [Cont Bool Bool] em Cont Bool [Bool].

O tipo Cont Bool [Bool] é traduzido para uma continuação que recebe uma função de [Bool] -> Bool e retorna um Bool ((([Bool] -> Bool) -> Bool)), sequence faz isso aplicando a função Bool -> Bool dentro de um fold (reduce em outras linguagens). Finalmente, runCont executa a função de continuação:

sat 3 (\(b1:b2:b3:_) -> b1 && b2 || b3)
True

1.8 IO

Quando dizemos que Haskell é uma linguagem de programação puramente funcional e todas suas funções são puras, a primeira questão que vem na mente é de como as funções de entrada e saída são implementadas. Como as funções getChar, putChar podem ser puras se elas dependem do efeito colateral? Como é possível compor funções puras com a saída de getChar se a saída é, teoricamente, indeterminada?

O segredo das funções de manipulação de IO é que elas tem seus valores guardados dentro de um container (o IO Monad) que nunca pode ser aberto. Ou seja, criamos funções que lidam com Char sem saber exatamente quem é esse caracter. Podemos imaginar o Monad IO como uma caixa quântica contendo uma superposição de todos os valores possíveis de um tipo. Toda chamada de função para esse tipo é jogada lá dentro e executada pelo sistema operacional quando apropriado.

As assinaturas de getChar e putChar são:

getChar :: IO Char -- () ->  IO Char

putChar :: Char :: IO ()

Note que a implementação da instância de Functor e Monad para IO é implementada internamente no Sistema Operacional e não temos um runIO que nos devolve um valor contido no container, ao fazer fmap f getChar a função será executada no retorno de getChar mas não poderemos ver seu resultado. Uma outra forma de pensar no IO é como um tipo State:

data IO a = Mundo -> (a, Mundo) = State Mundo a

A sequência:

do putStr "Hello"
   putStr "World"

Causa uma dependência funcional entre as duas funções de tal forma que elas serão executadas na sequência.

1.9 Leitura de arquivos usando IO

Imagine o seguinte arquivo de dados, exemploData.txt:

1.2 3.5 2.3
4.1 2.1 3.4

Queremos ler seu conteúdo e transformar em uma lista de listas:

\[ [ [1.2, 3.5, 2.3], [4.1, 2.1, 3.4], …] \]

A função readFile lê o arquivo em FilePath e retorna ele como String (envolvido em um IO).

readFile :: FilePath -> IO String

Vamos criar uma função parseFile que fará a conversão, a assinatura dela deve ser:

parseFile :: String -> [[Double]]

Queremos que cada linha do arquivo seja uma lista de Doubles:

parseFile :: String -> [[Double]]
parseFile file =  map parseLine (lines file)

A função parseLine converte cada palavra da linha em um Double:

parseFile :: String -> [[Double]]
parseFile file =  map parseLine (lines file)
  where
    parseLine l = map toDouble (words l)
    toDouble  w = read w :: Double

Nossa função readMyFile ficaria:

readMyFile :: [FilePath] -> IO [[Double]]
readMyFile []     = error "./readMyFile nome-do-arquivo"
readMyFile [name] = do conteudo <- readFile name
		       return (parseFile conteudo)

E a main:

main = do args <- getArgs
	  conteudo <- readMyFile args
	  print conteudo

2 Referências

https://bartoszmilewski.com/2014/10/28/category-theory-for-programmers-the-preface/