Como você sabe quando usar a tampa para a esquerda e quando usar a tampa para a direita?

Question

Estou ciente de que a tampa esquerda produz esquerda-inclinar-se árvores e dobre-direito produz direita-inclinar-se árvores, mas quando eu chegar para uma dobra, às vezes fico atolado na indução de dor de cabeça pensamento tentando determinar qual o tipo de dobra é apropriado.Eu, geralmente, acabam desenrolar todo o problema e percorrendo a aplicação da dobra função de como ela se aplica para o meu problema.

Então, o que eu quero saber é:

• Quais são algumas das regras de ouro para determinar se dobrar para a esquerda ou dobre para a direita?
• Como eu posso decidir rapidamente qual o tipo de dobra para uso dado o problema que eu estou enfrentando?

Há um exemplo em Scala por Exemplo (PDF) da utilização de uma dobra para escrever uma função chamada achatar que concatena uma lista de elemento de listas em uma única lista.Nesse caso, o direito de dobra é a opção mais adequada (dada a forma como as listas são concatenados), mas eu tinha que pensar um pouco para chegar a essa conclusão.

Desde o dobramento é uma acção em comum (funcional) de programação, eu gostaria de ser capaz de fazer estes tipos de decisões com rapidez e confiança.Então...alguma dica?

Answer 1

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

Este exemplo dobra usando a função acumuladora x

fold x [A, B, C, D]

Assim é igual a

A x B x C x D

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

Se você tem um associativa à esquerda operador, você definirá os parênteses como este

((A x B) x C) x D

Aqui, você usa um dobra esquerda. Exemplo (pseudocódigo no estilo Haskell)

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

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

A x (B x (C x D))

Exemplo: Consultador

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 associados à esquerda, então foldl é mais difundido. Mas, por outros casos, a notação de infix + parênteses é bastante útil.

Answer 2

Olin Arrepios diferenciado-los dizendo "foldl fundamental a lista iterador" e "foldr é fundamental lista de recursão operador." Se você olhar como foldl funciona:

((1 + 2) + 3) + 4

você pode ver o acumulador (como em um rabo-iteração recursiva) que está sendo construído.Em contraste, foldr receitas:

1 + (2 + (3 + 4))

onde você pode ver o transversal para o caso base, 4 e construir o resultado de lá.

Então eu proponho uma regra de ouro:se ele se parece com uma lista de iteração, um que fosse simples escrever recursiva forma, foldl é o caminho a percorrer.

Mas realmente esta será, provavelmente, ser mais evidente a partir da associatividade ' a dos operadores que você está usando.Se eles são deixados-associativa, use foldl.Se eles estão certos-associativa, use foldr.

Answer 3

Outros pôsteres deram boas respostas e não vou repetir o que eles já disseram. Como você deu um exemplo de Scala em sua pergunta, darei um exemplo específico do Scala. Como Truques já disse, um foldRight precisa preservar n-1 quadros de pilha, onde n é a duração da sua lista e isso pode facilmente levar a um estouro de pilha - e nem mesmo a recursão da cauda pode salvá -lo disso.

UMA List(1,2,3).foldRight(0)(_ + _) reduziria para:

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 iterativamente calculado, como feito no implementação de List.

Em uma linguagem estritamente avaliada como scala, um foldRight pode facilmente explodir a pilha para grandes listas, enquanto um foldLeft não vai.

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 geral é, portanto - para operadores que não têm uma associativa específica, sempre use foldLeft, pelo menos em Scala. Caso contrário, vá com outros conselhos dados nas respostas;).

Answer 4

It's also worth noting (and I realise this is stating the obvious a bit), in the case of a commutative operator the two are pretty much equivalent. In this situation a foldl might be the better choice:

foldl: (((1 + 2) + 3) + 4) can calculate each operation and carry the accumulated value forward

foldr: (1 + (2 + (3 + 4))) needs a stack frame to be opened for 1 + ? and 2 + ? before calculating 3 + 4, then it needs to go back and do the calculation for each.

I'm not enough of an expert on functional languages or compiler optimisations to say whether this is will actually make a difference but it certainly seems cleaner to use a foldl with commutative operators.