Programação Funcional em Haskell
29/02 e 07/03 de 2020

Para instalar o compilador o jeito mais recomendado é via stack: https://docs.haskellstack.org/en/stable/install_and_upgrade/

Uma vez instalado vocês podem criar um novo programa com o comando stack new nome-do-programa simple. Ele criará uma pasta com o nome de seu programa e nela uma arquivo src/Main.hs. Para programas simples, podemos utilizar esse próprio código para implementar todas as nossas funções.

Você consegue executar um programa com stack run no diretório do seu projeto (dado que ele consiga compilar :P).

Outra dica é utilizar o REPL do Haskell com stack ghci, nele você pode testar as funções padrões, verificar os tipos de funções e definições, obter mais informações sobre os tipos e classes de tipos, etc.

Prelude> [1 .. 10]
[1,2,3,4,5,6,7,8,9,10]
Prelude> :t [1 .. 10]
[1 .. 10] :: (Num a, Enum a) => [a]

O comando :i retorna informações sobre um tipo, quais classes ele pertence e em qual código-fonte ele está implementado:

Prelude> :i Int
data Int = GHC.Types.I# GHC.Prim.Int#     -- Defined in ‘GHC.Types’
instance Eq Int -- Defined in ‘GHC.Classes’
instance Ord Int -- Defined in ‘GHC.Classes’
instance Show Int -- Defined in ‘GHC.Show’
instance Read Int -- Defined in ‘GHC.Read’
instance Enum Int -- Defined in ‘GHC.Enum’
instance Num Int -- Defined in ‘GHC.Num’
instance Real Int -- Defined in ‘GHC.Real’
instance Bounded Int -- Defined in ‘GHC.Enum’
instance Integral Int -- Defined in ‘GHC.Real’

Esse mesmo comando para uma função ou operador permite ver a ordem de precedência, se ele é avaliado da esquerda pra direita ou o contrário:

Prelude> :i (+)
class Num a where
  (+) :: a -> a -> a
  ...
      -- Defined in ‘GHC.Num’
infixl 6 +

Nesse caso o operador (+) é avaliado da esquerda pra direita (o l em infixl e tem precedência 6 (quanto maior esse valor maior a prioridade). E em classe de tipos ele mostra as funções suportadas por uma classe:

Prelude> :i Num
class Num a where
  (+) :: a -> a -> a
  (-) :: a -> a -> a
  (*) :: a -> a -> a
  negate :: a -> a
  abs :: a -> a
  signum :: a -> a
  fromInteger :: Integer -> a

Idealmente suas funções devem ter uma assinatura mais abstrata possível, ou seja, se ela pode funcionar para diversos tipos, explicite isso. Inicialmente essa ideia é difícil de ser colocada em prática, então uma dica é criar a função com um tipo concreto e generalizar aos poucos:

-- calcula o seno do produto de uma lista de números
produto ::  [Double] -> Double
produto xs = foldr (*) 1 xs

f :: [Double] -> Double
f xs = sin (produto xs)

Observando a função sin no ghci com :i sin verificamos que ela faz parte da classe Floating, com isso nossas funções podem ser alteradas para:

-- calcula o seno do produto de uma lista de números
produto ::  Floating [a] -> a
produto xs = foldr (*) 1 xs

f :: Floating a => [a] -> a
f xs = sin (produto xs)

Da mesma forma, olhando a função produto verificamos que a única operação utilizada é (*) que é aplicável a qualquer tipo da classe Num:

-- calcula o seno do produto de uma lista de números
produto ::  Num [a] -> a
produto xs = foldr (*) 1 xs

f :: Floating a => [a] -> a
f xs = sin (produto xs)

Para finalizar, a função f nada mais do que a aplicação de sin após produto ou:

f = sin . produto

Lembrando que a sequência de Fibonacci é definida por \(f(n) = f(n-1) + f(n-2)\). Enumerando a sequência temos a lista [0, 1, 1, 2, 3, 5, 8, 13, ..]. Uma outra forma de construir uma lista é utilizando os elementos existentes para definir o próximo:

lista :: [Integer]
lista = 0 : 1 : f geraLista
  where
    f :: [Integer] -> [Integer]
    f (x:y:xs) = x+y : f (y:xs)

Se você fizer take 5 lista você obtém os 5 primeiros números da sequência de Fibonacci! Mas o que está acontecendo durante a execução do programa?

lista = 0 : 1 : f lista
take 5 lista

Ele consegue preencher os dois primeiros elementos requisitados, pois sabe que são 0 e 1. O restante será gerado pela função f da seguinte forma (vamos usar o símbolo _ para representar que não sabemos essa parte da lista):

take 5 lista = 0 : 1 : _ : _ : _
             = 0 : 1 : f (0:1:_)
f (0:1:_) = 0+1 : f _

Após esse ponto a lista é atualizada e temos:

take 5 lista = 0 : 1 : _ : _ : _
             = 0 : 1 : 1 : f (1:1:_) : _
f (0:1:_) = 0+1 : f (1:1:_)
f (1:1:_) = 1+1 : f (1:2:_)

e finalmente:

take 5 lista = 0 : 1 : _ : _ : _
             = 0 : 1 : 1 : 2 : f (1:2:_)
f (0:1:_) = 0+1 : f (1:1:_)
f (1:1:_) = 1+1 : f (1:2:_)
f (1:2:_) = 1+2 : f (2:3:_)

[0,1,1,2,3]

O foldr é definido como:

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f v [] = v
foldr f v (x:xs) = f x (foldr f v xs)

Examinando foldr (&&) True [True, True, False, True] temos:

foldr (&&) True (True:bs) = True && (foldr (&&) True bs)

que usando o curto-circuito do operador (&&): (True && x = x) gera:

foldr (&&) True bs

Prosseguindo temos:

foldr (&&) True (True:False:True:[]) = True && (foldr (&&) True (False:True:[]))
                                     = foldr (&&) True (False:True:[])
                                     = False &&  (foldr (&&) True (True:[]))
                                     = False

Ou seja, o foldr tem a capacidade de interromper o cálculo em caso de curto-circuito. Se você possui uma lista infinitas, o foldr é a melhor opção. Vejamos o que acontece com o foldl:

foldl :: (a -> b -> a) -> a -> [b] -> a
foldl f v []     = v
foldl f v (x:xs) = foldl f (f v x) xs

foldl (&&) True (True:True:False:True:[])
  = foldl (&&) (True && True) (True:False:True:[])
  = foldl (&&) (True) (True:False:True:[])
  = foldl (&&) (True && True) (False:True:[])
  = foldl (&&) (True) (False:True:[])
  = foldl (&&) (True && False) (True:[])
  = foldl (&&) (False) (True:[])
  = foldl (&&) (False && True) []
  = False

Nesse caso tivemos que percorrer toda a lista…

Um desafio para quem quiser praticar o uso de folds. É possível definir as funções map e filter utilizando foldr e foldl.