Dobrar (função de ordem superior) - Fold (higher-order function)

Na programação funcional , dobrar (também denominado reduzir , acumular , agregar , comprimir ou injetar ) se refere a uma família de funções de ordem superior que analisam uma estrutura de dados recursiva e, por meio do uso de uma determinada operação de combinação, recombina os resultados do processamento recursivo de seu partes constituintes, construindo um valor de retorno. Normalmente, uma dobra é apresentada com uma função de combinação , um nó superior de uma estrutura de dados e, possivelmente, alguns valores padrão a serem usados ​​sob certas condições. A dobra então prossegue combinando elementos da hierarquia da estrutura de dados , usando a função de forma sistemática.

As dobras são de certo modo duplo para se desenrola , que levam uma semente valor e aplicar uma função de corecursively para decidir como construir progressivamente uma estrutura de dados corecursive, ao passo que uma dobra quebras recursivamente que a estrutura para baixo, substituindo-o com os resultados da aplicação de uma função que combina a cada nó em seus valores terminais e os resultados recursivos ( catamorfismo , versus anamorfismo de desdobramentos).

Como transformações estruturais

As dobras podem ser consideradas como uma substituição consistente dos componentes estruturais de uma estrutura de dados por funções e valores. Listas , por exemplo, são construídas em muitas linguagens funcionais a partir de duas primitivas: qualquer lista é uma lista vazia, comumente chamada de nil   ( []), ou é construída prefixando um elemento na frente de outra lista, criando o que é chamado de nó de cons  (   ), resultante da aplicação de uma função (escrita como dois pontos em Haskell ). Pode-se ver uma dobra nas listas substituindo   o nulo no final da lista por um valor específico e substituindo cada contras por uma função específica. Essas substituições podem ser vistas como um diagrama: Cons(X1,Cons(X2,Cons(...(Cons(Xn,nil)))))cons(:)

Há outra maneira de realizar a transformação estrutural de maneira consistente, com a ordem dos dois elos de cada nó invertida quando alimentada na função de combinação:

Essas imagens ilustram visualmente a dobra direita e esquerda de uma lista . Eles também destacam o fato de que foldr (:) []é a função de identidade nas listas (uma cópia superficial na linguagem Lisp ), já que substituir cons por conse nil por nilnão mudará o resultado. O diagrama de dobra à esquerda sugere uma maneira fácil de reverter uma lista foldl (flip (:)) []. Observe que os parâmetros a contras devem ser invertidos, porque o elemento a ser adicionado agora é o parâmetro à direita da função de combinação. Outro resultado fácil de ver deste ponto de vista é escrever a função de mapa de ordem superior em termos de foldr, compondo a função para atuar sobre os elementos cons, como:

 map f = foldr ((:) . f) []

onde o ponto final (.) é um operador que denota a composição da função .

Essa maneira de ver as coisas fornece uma rota simples para projetar funções semelhantes a dobras em outros tipos e estruturas de dados algébricos , como vários tipos de árvores. Um escreve uma função que recursivamente substitui os construtores do tipo de dados com as funções fornecidas e quaisquer valores constantes do tipo com os valores fornecidos. Essa função é geralmente chamada de catamorfismo .

Nas listas

A dobragem da lista [1,2,3,4,5]com o operador de adição resultaria em 15, a soma dos elementos da lista [1,2,3,4,5]. Para uma aproximação grosseira, pode-se pensar nessa dobra como a substituição das vírgulas na lista pela operação +, dando 1 + 2 + 3 + 4 + 5.

No exemplo acima, + é uma operação associativa , de modo que o resultado final será o mesmo, independentemente dos parênteses, embora a forma específica em que é calculado seja diferente. No caso geral de funções binárias não associativas, a ordem em que os elementos são combinados pode influenciar o valor do resultado final. Nas listas, há duas maneiras óbvias de realizar isso: ou combinando o primeiro elemento com o resultado da combinação recursiva do resto (chamado de dobra direita ), ou combinando o resultado da combinação recursiva de todos os elementos, exceto o último, com o último elemento (chamado de dobra esquerda ). Isso corresponde a um operador binário ser associativo à direita ou associativo à esquerda, na terminologia de Haskell ou Prolog . Com uma dobra direita, a soma seria colocada entre parênteses como 1 + (2 + (3 + (4 + 5))), enquanto com uma dobra esquerda seria entre parênteses (((1 + 2) + 3) + 4) + 5.

Na prática, é conveniente e natural ter um valor inicial que no caso de uma dobra à direita é usado quando se chega ao final da lista, e no caso de uma dobra à esquerda é o que é inicialmente combinado com o primeiro elemento de a lista. No exemplo acima, o valor 0 (a identidade aditiva ) seria escolhido como um valor inicial, dando 1 + (2 + (3 + (4 + (5 + 0))))para a dobra direita e ((((0 + 1) + 2) + 3) + 4) + 5para a dobra esquerda. Para a multiplicação, a escolha inicial de 0 não iria funcionar: 0 * 1 * 2 * 3 * 4 * 5 = 0. O elemento de identidade para multiplicação é 1. Isso nos daria o resultado 1 * 1 * 2 * 3 * 4 * 5 = 120 = 5!.

Dobras lineares vs. em árvore

O uso de um valor inicial é necessário quando a função combinadora f   é assimétrica em seus tipos (por exemplo a → b → b), ou seja, quando o tipo de seu resultado é diferente do tipo dos elementos da lista. Então, um valor inicial deve ser usado, com o mesmo tipo do  resultado de f , para que uma cadeia linear de aplicações seja possível. Se ele será orientado à esquerda ou à direita, isso será determinado pelos tipos esperados de seus argumentos pela função de combinação. Se for o segundo argumento que deve ser do mesmo tipo que o resultado, então f   pode ser visto como uma operação binária que se associa à direita e vice-versa.

Quando a função é um magma , ou seja, simétrico em seus tipos ( a → a → a), e o tipo de resultado é o mesmo que o tipo dos elementos da lista, os parênteses podem ser colocados de forma arbitrária, criando assim uma árvore de subexpressões aninhadas, por exemplo ((1 + 2) + (3 + 4)) + 5,. Se a operação binária f   for associativa, este valor será bem definido, ou seja, o mesmo para qualquer parênteses, embora os detalhes operacionais de como ele é calculado sejam diferentes. Isso pode ter um impacto significativo na eficiência se f não   for estrito .

Enquanto as dobras lineares são orientadas para o nó e operam de maneira consistente para cada nó de uma lista , as dobras em forma de árvore são orientadas para a lista inteira e operam de maneira consistente em grupos de nós.

Dobras especiais para listas não vazias

Freqüentemente, deseja-se escolher o elemento de identidade da operação f como o valor inicial z . Quando nenhum valor inicial parece apropriado, por exemplo, quando se deseja dobrar a função que calcula o máximo de seus dois parâmetros em uma lista não vazia para obter o elemento máximo da lista, existem variantes de foldre foldlque usam o último e primeiro elemento da lista, respectivamente, como o valor inicial. Em Haskell e em várias outras linguagens, estes são chamados de foldr1e foldl1, o 1 fazendo referência à provisão automática de um elemento inicial, e ao fato de que as listas às quais se aplicam devem ter pelo menos um elemento.

Essas dobras usam operação binária de tipo simétrico: os tipos de seus argumentos e de seu resultado devem ser os mesmos. Richard Bird em seu livro de 2010 propõe "uma função de dobra geral em listas não vazias" foldrnque transforma seu último elemento, ao aplicar uma função de argumento adicional a ele, em um valor do tipo de resultado antes de iniciar a dobra em si, e é, portanto, capaz para usar operação binária com tipo assimétrico como o regular foldrpara produzir um resultado de tipo diferente do tipo de elementos da lista.

Implementação

Dobras lineares

Usando Haskell como exemplo, foldle foldrpode ser formulado em algumas equações.

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

Se a lista estiver vazia, o resultado é o valor inicial. Caso contrário, dobre o final da lista usando como novo valor inicial o resultado da aplicação de f ao antigo valor inicial e ao primeiro elemento.

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

Se a lista estiver vazia, o resultado será o valor inicial z. Caso contrário, aplique f ao primeiro elemento e o resultado da dobra do resto.

Dobras de árvore

As listas podem ser dobradas em forma de árvore, tanto para listas finitas quanto indefinidamente definidas:

foldt f z []     = z
foldt f z [x]    = f x z
foldt f z xs     = foldt f z (pairs f xs)
 
foldi f z []     = z
foldi f z (x:xs) = f x (foldi f z (pairs f xs))
 
pairs f (x:y:t)  = f x y : pairs f t
pairs _ t        = t

No caso de foldifunção, para evitar sua avaliação descontrolada em listas indefinidamente definidas, a função nãof deve sempre exigir o valor de seu segundo argumento, pelo menos não todo ele ou não imediatamente (veja o exemplo abaixo).

Dobras para listas não vazias

foldl1 f [x]      = x
foldl1 f (x:y:xs) = foldl1 f (f x y : xs)

foldr1 f [x]      = x
foldr1 f (x:xs)   = f x (foldr1 f xs)

foldt1 f [x]      = x
foldt1 f (x:y:xs) = foldt1 f (f x y : pairs f xs)
 
foldi1 f [x]      = x
foldi1 f (x:xs)   = f x (foldi1 f (pairs f xs))

Considerações de ordem de avaliação

Na presença de avaliação preguiçosa , ou não estrita , foldrretornará imediatamente a aplicação de f para o topo da lista e o caso recursivo de dobrar o resto da lista. Assim, se f é capaz de produzir alguma parte de seu resultado sem referência ao caso recursivo à sua "direita", ou seja, em seu segundo argumento, e o resto do resultado nunca é exigido, então a recursão irá parar (por exemplo, ) . Isso permite que as dobras direitas operem em listas infinitas. Por outro lado, irá chamar a si mesmo imediatamente com novos parâmetros até atingir o final da lista. Essa recursão final pode ser compilada de forma eficiente como um loop, mas não pode lidar com listas infinitas - ela recursará para sempre em um loop infinito . head == foldr (\a b->a) (error "empty list")foldl

Tendo atingido o final da lista, uma expressão é efetivamente construída por foldlde faplicativos de aprofundamento à esquerda aninhados , que é então apresentada ao chamador para ser avaliada. Se a função fse referisse ao seu segundo argumento primeiro aqui, e fosse capaz de produzir alguma parte de seu resultado sem referência ao caso recursivo (aqui, à sua esquerda , isto é, em seu primeiro argumento), então a recursão pararia. Isso significa que, embora foldrrecorra à direita , permite que uma função de combinação preguiçosa inspecione os elementos da lista à esquerda; e, inversamente, embora seja foldlrecorrente à esquerda , permite que uma função de combinação preguiçosa inspecione os elementos da lista à direita, se assim desejar (por exemplo, ). last == foldl (\a b->b) (error "empty list")

Reverter uma lista também é recursivo na cauda (pode ser implementado usando ). Em listas finitas , isso significa que a dobra à esquerda e reversa podem ser compostas para realizar uma dobra à direita de forma recursiva na cauda (cf.  ), com uma modificação na função para que ela inverta a ordem de seus argumentos (isto é, ), tail-recursivamente construindo uma representação da expressão que a dobra à direita construiria. A estranha estrutura de lista intermediária pode ser eliminada com a técnica do estilo continuation-pass ,; da mesma forma, (  só é necessário em linguagens como Haskell com sua ordem invertida de argumentos para a função de combinação de, ao contrário, por exemplo, em Scheme, onde a mesma ordem de argumentos é usada para combinar funções para e ). rev = foldl (\ys x -> x : ys) []1+>(2+>(3+>0)) == ((0<+3)<+2)<+1ffoldr f z == foldl (flip f) z . foldl (flip (:)) []foldr f z xs == foldl (\k x-> k . f x) id xs zfoldl f z xs == foldr (\x k-> k . flip f x) id xs zflipfoldlfoldlfoldr

Outro ponto técnico é que, no caso de dobras à esquerda com avaliação preguiçosa, o novo parâmetro inicial não está sendo avaliado antes de ser feita a chamada recursiva. Isso pode levar a estouros de pilha quando se chega ao final da lista e tenta avaliar a expressão potencialmente gigantesca resultante. Por esse motivo, essas linguagens geralmente fornecem uma variante mais restrita da dobra à esquerda, que força a avaliação do parâmetro inicial antes de fazer a chamada recursiva. Em Haskell, esta é a função foldl'(observe o apóstrofo, pronunciado 'primo') na Data.Listbiblioteca (é preciso estar ciente do fato de que forçar um valor construído com um construtor de dados preguiçoso não forçará seus constituintes automaticamente por si só). Combinadas com a recursão da cauda, ​​tais dobras aproximam-se da eficiência dos loops, garantindo uma operação constante no espaço, quando a avaliação preguiçosa do resultado final é impossível ou indesejável.

Exemplos

Usando um interpretador Haskell , as transformações estruturais que as funções de dobra realizam podem ser ilustradas pela construção de uma string:

λ> foldr (\x y -> concat ["(",x,"+",y,")"]) "0" (map show [1..13])
"(1+(2+(3+(4+(5+(6+(7+(8+(9+(10+(11+(12+(13+0)))))))))))))"
 
λ> foldl (\x y -> concat ["(",x,"+",y,")"]) "0" (map show [1..13])
"(((((((((((((0+1)+2)+3)+4)+5)+6)+7)+8)+9)+10)+11)+12)+13)"
 
λ> foldt (\x y -> concat ["(",x,"+",y,")"]) "0" (map show [1..13])
"(((((1+2)+(3+4))+((5+6)+(7+8)))+(((9+10)+(11+12))+13))+0)"
 
λ> foldi (\x y -> concat ["(",x,"+",y,")"]) "0" (map show [1..13])
"(1+((2+3)+(((4+5)+(6+7))+((((8+9)+(10+11))+(12+13))+0))))"

Dobramento infinito em forma de árvore é demonstrado, por exemplo, na produção de primos recursivos por peneira ilimitada de Eratóstenes em Haskell :

primes = 2 : _Y ((3 :) . minus [5,7..] . foldi (\(x:xs) ys -> x : union xs ys) [] 
                       . map (\p-> [p*p, p*p+2*p..]))
_Y g = g (_Y g)     -- = g . g . g . g . ...

onde a função unionopera em listas ordenadas de maneira local para produzir com eficiência sua união de conjunto e minussua diferença de conjunto .

Para listas finitas, por exemplo, a classificação por mesclagem (e sua variedade de remoção de duplicatas nubsort) pode ser facilmente definida usando dobragem em árvore como

mergesort xs = foldt merge [] [[x] | x <- xs]
nubsort   xs = foldt union [] [[x] | x <- xs]

com a função mergeuma variante de preservação de duplicatas union.

Funciona heade lastpoderia ter sido definido por meio de dobramento como

head = foldr (\x r -> x) (error "head: Empty list")
last = foldl (\a x -> x) (error "last: Empty list")

Em várias línguas

Universalidade

Fold é uma função polimórfica . Para qualquer g tendo uma definição

 g [] = v
 g (x:xs) = f x (g xs)

então g pode ser expresso como

 g = foldr f v

Além disso, em uma linguagem preguiçosa com listas infinitas, um combinador de ponto fixo pode ser implementado via dobra, provando que as iterações podem ser reduzidas a dobras:

 y f = foldr (\_ -> f) undefined (repeat undefined)

Veja também

• Função agregada
• Operação binária iterada
• Catamorfismo , uma generalização de dobra
• Homomorfismo
• Mapa (função de ordem superior)
• Soma do prefixo
• Tipo de dados recursivo
• Operador de Redução
• Recursão estrutural

Referências

links externos

• "Funções de ordem superior - mapear, dobrar e filtrar"
• "Unidade 6: As funções de dobra de ordem superior"
• "Dobre em Tcl"
• "Construindo Homomorfismo de Lista a partir das Dobras Esquerda e Direita"
• "A dobra mágica"