Como saber quando usar a dobra para a esquerda e quando usar a dobra para a direita?

Estou ciente de que a dobra para a esquerda produz árvores inclinadas para a esquerda e a dobra para a direita produz árvores com inclinação para a direita, mas quando procuro uma dobra, às vezes me encontro atolado em pensamentos que induzem a dor de cabeça tentando determinar que tipo de dobra é apropriado. Eu geralmente acabo resolvendo todo o problema e percorrendo a implementação da função de dobra conforme se aplica ao meu problema.

Então, o que eu quero saber é:

• Quais são algumas regras básicas para determinar se dobrar para a esquerda ou direita?
• Como posso decidir rapidamente que tipo de dobra usar, considerando o problema que estou enfrentando?

Há um exemplo em Scala por Exemplo (PDF) de usar uma dobra para escrever uma função chamada nivelar, que concatena uma lista de listas de elementos em uma única lista. Nesse caso, uma dobra certa é a escolha adequada (dada a forma como as listas são concatenadas), mas tive que pensar um pouco sobre isso para chegar a essa conclusão.

Visto que dobrar é uma ação comum na programação (funcional), gostaria de poder tomar esse tipo de decisão com rapidez e confiança. Então ... alguma dica?

Você pode transferir uma dobra para uma notação de operador infixo (escrevendo no meio):

Este exemplo dobra usando a função de acumulador x

fold x [A, B, C, D]

assim é igual

A x B x C x D

Agora você só precisa raciocinar sobre a associatividade do seu operador (colocando parênteses!).

Se você tiver um operador associativo à esquerda , você definirá os parênteses como este

((A x B) x C) x D

Aqui, você usa uma dobra esquerda . Exemplo (pseudocódigo estilo haskell)

foldl (-) [1, 2, 3] == (1 - 2) - 3 == 1 - 2 - 3 // - is left-associative

Se o seu operador for associativo à direita ( dobra direita ), os parênteses seriam definidos assim:

A x (B x (C x D))

Exemplo: Cons-Operator

foldr (:) [] [1, 2, 3] == 1 : (2 : (3 : [])) == 1 : 2 : 3 : [] == [1, 2, 3]

Em geral, os operadores aritméticos (a maioria dos operadores) são associativos à esquerda, portanto, foldlsão mais difundidos. Mas nos outros casos, notação infixa + parênteses é bastante útil.

Olin Shivers os diferenciou dizendo "foldl é o iterador fundamental da lista" e "foldr é o operador fundamental de recursão da lista". Se você observar como o foldl funciona:

((1 + 2) + 3) + 4

você pode ver o acumulador (como em uma iteração recursiva de cauda) sendo construído. Em contraste, foldr continua:

1 + (2 + (3 + 4))

onde você pode ver o percurso até o caso base 4 e construir o resultado a partir daí.

Portanto, proponho uma regra prática: se parece uma iteração de lista, uma que seria simples de escrever na forma recursiva de cauda, ​​foldl é o caminho a seguir.

Mas, na verdade, isso provavelmente ficará mais evidente pela associatividade dos operadores que você está usando. Se eles forem associativos à esquerda, use foldl. Se eles forem associativos à direita, use foldr.

Outros pôsteres deram boas respostas e não vou repetir o que já disseram. Como você deu um exemplo de Scala em sua pergunta, darei um exemplo específico de Scala. Como Tricks já disse, a foldRightprecisa preservar os n-1frames da pilha, onde nestá o comprimento da sua lista e isso pode facilmente levar a um estouro de pilha - e nem mesmo a recursão de cauda poderia salvá-lo disso.

A List(1,2,3).foldRight(0)(_ + _)seria reduzido a:

1 + List(2,3).foldRight(0)(_ + _)        // first stack frame
    2 + List(3).foldRight(0)(_ + _)      // second stack frame
        3 + 0                            // third stack frame 
// (I don't remember if the JVM allocates space 
// on the stack for the third frame as well)

enquanto List(1,2,3).foldLeft(0)(_ + _)reduziria para:

(((0 + 1) + 2) + 3)

que pode ser calculado iterativamente, como feito na implementação deList .

Em uma linguagem estritamente avaliada como Scala, um foldRightpode facilmente explodir a pilha de listas grandes, enquanto um foldLeftnão.

Exemplo:

scala> List.range(1, 10000).foldLeft(0)(_ + _)
res1: Int = 49995000

scala> List.range(1, 10000).foldRight(0)(_ + _)
java.lang.StackOverflowError
        at scala.List.foldRight(List.scala:1081)
        at scala.List.foldRight(List.scala:1081)
        at scala.List.foldRight(List.scala:1081)
        at scala.List.foldRight(List.scala:1081)
        at scala.List.foldRight(List.scala:1081)
        at scala.List.foldRight(List.scala:1081)
        at scala.List.foldRight(List.scala:1081)
        at scala.List.foldRight(List.scala:1081)
        at scala.List.foldRig...

Minha regra é, portanto - para operadores que não têm uma associatividade específica, sempre use foldLeft, pelo menos em Scala. Caso contrário, siga os outros conselhos fornecidos nas respostas;).

Também é importante notar (e eu percebo que isso está afirmando um pouco o óbvio), no caso de um operador comutativo os dois são praticamente equivalentes. Nesta situação, um foldl pode ser a melhor escolha:

foldl: (((1 + 2) + 3) + 4)pode calcular cada operação e transportar o valor acumulado para a frente

foldr: (1 + (2 + (3 + 4)))precisa que um frame de pilha seja aberto para 1 + ?e 2 + ?antes de calcular 3 + 4, então ele precisa voltar e fazer o cálculo para cada um.

Não sou especialista o suficiente em linguagens funcionais ou otimizações de compiladores para dizer se isso realmente fará diferença, mas certamente parece mais limpo usar um foldl com operadores comutativos.