Understanding Deforestation (PT Version)

Este post descreve um dos conceitos que mais me agradam e está intrinsecamente ligado ao conceito de fold e unfold.

Comecemos por considerar o tipo de listas built-in:

data [x] = x : [x] | []

Algumas das funções básicas que estamos habituados a construir são do género:

sumL, prodL  :: [Int] -> Int
sumL (x:xs)  = x + sumL xs
sumL []      = 0
prodL (x:xs) =  x * prodL xs
prodL []     =  1

Partindo destas funções básicas podemos verificar que há um padrão de recursividade sobre o operador e o caso de paragem. O operador recebe um elemento da lista e o resultado da invocação da função sobre a cauda da lista.
Como muitos de vocês já sabem, este padrão de recursividade é representado como um fold.
Encaremos o fold como uma função que consome uma estrutura de dados. Existe por isso um fold para cada estrutura de dados, em Haskell para cada “Data”.
Vamos agora interpretar a função fold para daí chegarmos ao conceito de Álgebra.
Vou representar o foldr para listas como foldL, não confundir com o “verdadeiro” foldl.
A primeira codificação de foldL que aprendi, em PF, foi:

foldL :: (a -> b -> b) -> b -> [a] -> b
foldL f c []       = c
foldL f c (x:xs) = f x (foldL f c xs)

Esta função é sobretudo um resultado da aplicação de pattern matching sobre as listas.
Eu penso que esta não será a melhor forma de encarar o que o fold verdadeiramente representa, mas sim a sua versão uncurried:

foldL :: ((a ->b->b),b) -> [a] -> b
foldL (cons, nil) = fold where
 fold :: [a] -> b
 fold []    = nil
 fold (x:xs) = cons x (fold xs)

Com esta representação podemos realmente perceber que:

sumL, prodL  :: [Int] -> Int
sumL = foldL ((+),0)
prodL = foldL ((*), 1)

Esta forma de entender o fold através das estruturas de dados tornam-se mais claras.
Este par ((+),0), ((*),1) ou genericamente (op,c), chama-se de Álgebra de Listas, ou list-algebra. Vamos ficar-nos pela notação inglesa para uniformizar as coisas.
Uma list-algebra consiste num tipo [b]l[/b] (designado de portador da álgebra, algebra carrier), um operador binário [b]x -> l -> l[/b] e uma constante [b]c[/b] do tipo l.
Obviamente que um tipo como Int pode ser portador de várias list-algebras como ((+),0) ou ((*),1).

Vamos agora ao que realmente interessa, utilizar mecanismo para folds “genericos”.
Para isso consideremos o tipo:

type ListAlgebra x l = ((x->l->l),l)

A forma de como chegamos a este tipo para cada estrutura de dados é da seguinte forma:
A parte da esquerda do tipo é fácil de construir:
1. Acrescentamos “Algebra” ao nome (considerando que [x] é na verdade List x, uma representação User-defined de listas).
2. Acrescentamos um argumento l.
Passamos entao de, List x para ListAlgebra x l

A parte da direita é construída da seguinte forma:
1. Olhemos para os construtores (:) e [] de listas:

(:) :: x -> [x] -> [x]
[]  :: [x]

Substituindo [x] pelo nosso tipo l, ficamos com:
De notar que este tipo l é o tipo que nos realmente queremos decompor a estrutura, no caso de sumL seria Int.

(:)' :: x -> l -> l
[]'  :: l

Podemos encarar (:)’ como a função cons e []‘ como nil. Tipicamente estas definições diferem das built-in lists ou das user-defined lists.

Como foi definido antes, uma algebra generica é um par (op,c). Chegamos assim à parte da direita da ListAlgebra que é constituída por ((:)’,[]‘) ou (cons,nil).
O nosso foldL, para o tipo de listas user-defined será:

data List x = Cons x (List x) | Nil
type ListAlgebra x l = ((x -> l -> l),l)

foldL :: ListAlgebra x l -> List x -> l
foldL (cons, nil) = fold where
 fold :: List x -> l
 fold Nil               = nil
 fold (Cons x xs) = cons x (fold xs)

Vamos aplicar o método num exemplo:

data BinTree x = Bin (BinTree x) (BinTree x) | Leaf x

Pede agora para definirem um foldBT. Aplicando o método, a primeira coisa a fazer é desvendar os construtores, neste caso Bin e Leaf (para quem não sabe, um construtor é simplesmente uma função que recebe argumentos e devolve uma estrutura de dados; entra fermento e farinha, saí pão).

Bin :: BinTree x -> BinTree x -> BinTree x
Leaf :: x -> BinTree x

Continuando definimos agora a nossa álgebra para árvores binárias:

type BinTreeAlgebra x l = (l -> l -> l, x -> l)

Se quiseres ver as coisas ainda mais abstractas, pensem: Hmm, o fold pega num BinTree x e transforma num l qualquer. Então, para cada construtor eu defino uma função que faz isso:

bin :: l -> l -> l
leaf :: x -> l

E agora sei que a minha Algebra para esta estrutura é:

type BinTreeAlgebra x l = (bin, leaf)

Automatizando este processo (para ficarmos mais rápidos e termos tempo para acabar o exame) chegamos à definição do foldBT:

foldBT :: BinTreeAlgebra x l -> BinTree x -> l
foldBT (bin, leaf) = fold where
 fold :: BinTree x -> l
 fold Leaf            = leaf
 fold (Bin esq dir) = bin (fold esq) (fold dir)

Reparem na semelhança entre esta definição de fold e a de uma função fácil de definir como:

flatBT :: BinTree x -> [x]
flatBT Leaf             = (:[])
flatBT (Bin esq dir) = (++) (fold esq) (fold dir)

Será assim tão dificl passar de flatBT para uma definição de foldBT?! Só temos de descobrir qual é a nossa função leaf e bin, neste caso (:[]) que recebe um elemento e o coloca como lista, basicamente  e (++).
Portanto flatBT = foldBT ((++),(:[])).
A definição que o professo alcino provavemente quer é: flatBT = foldBT (++) (:[]) (facilimo passar de uma para outra).
Não há assim razão para ninguém errar este tipo de perguntas no exame, para quem realmente quer saber, para perceber o que é um fold e a razão pelo qual são tão importantes.

Considermos agora o caso:

data Parentheses = Match Parentheses Parentheses | Empty

Esta estrutura de dados representa uma sintaxe abstracta para uma gramática que gera a linguagem de parênteses aninhados e simétricos. Ou seja, ()() pertence a esta linguagem, mas ()( não.
A forma como representamos ()() é: Match Empty (Match Empty Empty).

Aplicando o método ficamos com:

type ParenthesesAlgebra m = (m -> m -> m , m)
ou (para quem ainda não tem prática)
type ParenthesesAlgebra m = (match, empty)
match :: m -> m -> m
empty :: m

e o foldP:

foldP :: ParenthesesAlgebra m -> Parentheses -> m
foldP (match,empty) = fold where
 fold (Match l r) = match (fold l) (fold r)
 fold Empty       = empty

Podemos agora definir funções que calculam coisas como a profundidade:

depthParenthesesAlgebra :: ParenthesesAlgebra Int
depthParenthesesAlgebra = (\x y -> max (1+x) y,0)

depthParentheses :: Parentheses -> Int
depthParentheses = foldParentheses depthParenthesesAlgebra

Imaginemos que queremos passar deste tipo Parentheses para uma String que representa, para assim provar que eu não menti quando disse que Match Empty (Match Empty Empty) equivalia a ()().
Queremos “shredar” ou decompor Parentheses numa String, logo o nosso tipo m passa agora a ser String.
Chamemos a essa função a2cParentheses:

a2cParentheses :: Parentheses -> String
a2cParentheses = foldParentheses a2cParenthesesAlgebra

Falta-nos definir apenas a função a2cParenthesesAlgebra que recebe a Álgebra e a transforma numa String.

a2cParenthesesAlgebra :: ParenthesesAlgebra String
a2cParenthesesAlgebra = (\xs ys -> "("++xs++")"++ys,"")

Agora para quem já domina disto:
Suponhamos que existe uma função que faz parsing de uma string para esta estrutura de dados:

parens  :: Parser Char Parentheses
parens  = f <$> open <*> parens <*> close <*> parens
 <|> succeed Empty
 where f a b c d = Match b d

Noutro post explicarei estes combinadores e também como tudo funciona, mas para agora apenas tenham em consideração que esta função existe e funciona.
Tendo esta função, vamos criar uma variante que faz algo parecido como a depthParentheses, mas sem receber a estrutura mas texto.

nesting  :: Parser Char Int
nesting  =  f <$> open <*> nesting <*> close <*> nesting
 <|> succeed 0
 where f a b c d = max (1+b) d

O truque está na definição de f, chamada a função semântica que constrói o que queremos (no caso do parens a estrutura Parentheses, no caso de nesting um Int).

Uma função equivalente à de nesting é:

nesting’ :: Parser Char Int
nesting’ = depthParentheses <$> parens

Reparem que ambas as funções são equivalentes, mas nesting’ é criada através do fold e nesting através um parser no qual facilmente nos podemos enganar, mas sem duvida mais eficiente, pois na função nesting estamos a consumir a String, enquanto na função nesting’ criamos uma estrutura de Parentheses auxiliar que depois vamos consumir com o fold.
A função nesting’ é um hilomorfismo: fold . unfold, ou para sermos fancies um catamorfismo . anamorfismo, primeiro criamos uma estrutura auxiliar com o anamorfismo e depois consumimos essa estrutura com o catamorfismo.
O nosso objectivo é que codificar a função nesting’ e esperar que o compilador seja esperto o suficiente para automaticamente transformar nesting’ em nesting. A esta transformação dá-se o nome de deforestation.

Este post foi baseado no conteúdo de:

Johan Jeuring and Doaitse Swierstra, Grammars and Parsing
UU Lecture Notes from 2001 (revised in 2006)

Available Online

Nota: Este post não foi devidamente analisado por falta de tempo. Qualquer erro é da responsabilidade do autor e não necessariamente das fontes.

Note: This post was not properly reviewed due to lack of time. Any error on the content is of the author responsability and not necessarily from the source.

Advertisement