Esse post é baseado no livro Teoria das Categorias para Programadores, de Bartosz Milewski.
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
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.
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.
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))
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))
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)
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])
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)
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
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.
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
https://bartoszmilewski.com/2014/10/28/category-theory-for-programmers-the-preface/