왼쪽 왼쪽을 언제 사용하고 언제 접을 수있는시기를 어떻게 알 수 있습니까?

StackOverflow https://stackoverflow.com/questions/1446419

문제

나는 왼쪽 왼쪽이 왼쪽의 나무를 생산하고 폴드 오른쪽이 오른쪽 나무를 생산한다는 것을 알고 있습니다. 그러나 접는 나무에 도달하면 때때로 두통을 유발하는 생각에 푹 빠지는 것을 발견합니다. 적절합니다. 나는 보통 전체 문제를 풀고 내 문제에 적용되는 폴드 기능의 구현을 밟게됩니다.

그래서 내가 알고 싶은 것은 다음과 같습니다.

  • 왼쪽을 접거나 오른쪽으로 접을 것인지 결정하기위한 경험 규칙은 무엇입니까?
  • 내가 직면 한 문제가 주어지면 어떤 유형의 접을 수 있는지 어떻게 신속하게 결정할 수 있습니까?

예제가 있습니다 예제 별 스칼라 (PDF)는 폴드를 사용하여 Flatten이라는 함수를 작성하여 요소 목록 목록을 단일 목록으로 연결합니다. 이 경우 올바른 접이식은 올바른 선택입니다 (목록이 연결되는 방식이 주어지면) 그러나 그 결론에 도달하기 위해 약간 생각해야했습니다.

폴딩은 (기능적) 프로그래밍에서 공통적 인 행동이기 때문에 이러한 종류의 결정을 빠르고 자신있게 결정할 수 있기를 원합니다. 그래서 ... 어떤 팁?

도움이 되었습니까?

해결책

접기를 디스 픽스 연산자 표기법으로 전송할 수 있습니다 (사이에 쓰기) :

이 예제는 축합기 기능을 사용하여 접 힙니다 x

fold x [A, B, C, D]

따라서 동일합니다

A x B x C x D

이제 당신은 당신의 운영자의 연관성에 대해 추론해야합니다 (괄호를 넣어!).

당신이있는 경우 좌심 관련성 연산자, 이와 같은 괄호를 설정합니다

((A x B) x C) x D

여기, 당신은 a를 사용합니다 왼쪽 접기. 예제 (Haskell 스타일 의사 코드)

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

운영자가 올바른 연관성 인 경우 (오른쪽 접기), 괄호는 다음과 같이 설정됩니다.

A x (B x (C x D))

예 : 상담 자

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

일반적으로 산술 연산자 (대부분의 연산자)는 좌회전이므로 foldl 더 널리 퍼져 있습니다. 그러나 다른 경우에는 Infix 표기법 + 괄호가 매우 유용합니다.

다른 팁

Olin Shivers "Foldl은 기본 목록 반복자"이고 "Foldr는 기본 목록 재귀 연산자"라고 말함으로써 차별화되었습니다. Foldl의 작동 방식을 보면 :

((1 + 2) + 3) + 4

테일 리퍼 시브 반복에서와 같이 축합기가 구축되는 것을 볼 수 있습니다. 대조적으로, Foldr는 다음과 같습니다.

1 + (2 + (3 + 4))

기본 케이스 4의 횡단을보고 그 결과를 쌓을 수 있습니다.

그래서 나는 경험의 규칙을 제시합니다. 목록 반복처럼 보인다면, 꼬리 수반 형태로 간단 할 것입니다.

그러나 실제로 이것은 아마도 당신이 사용하는 운영자의 연관성에서 가장 분명 할 것입니다. 그들이 왼쪽 관련이라면 Foldl을 사용하십시오. 그들이 올바른 연관성이라면 Foldr을 사용하십시오.

다른 포스터는 좋은 답변을 받았으며 이미 말한 것을 반복하지 않을 것입니다. 귀하의 질문에 Scala 예제를 제시 한대로 Scala 구체적인 예를 제공하겠습니다. 처럼 트릭 이미 말했습니다 foldRight 보존해야합니다 n-1 스택 프레임, 위치 n 목록의 길이이며 이것은 스택 오버플로로 쉽게 이어질 수 있으며 꼬리 재귀조차도 이것으로부터 당신을 절약 할 수 없습니다.

ㅏ List(1,2,3).foldRight(0)(_ + _) 감소 할 것입니다 :

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)

동안 List(1,2,3).foldLeft(0)(_ + _) 감소 할 것입니다 :

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

반복적으로 계산할 수 있으며 구현 List.

엄격하게 평가 된 언어에서 Scala, a foldRight 큰 목록을 위해 스택을 쉽게 날릴 수 있지만 foldLeft 습관.

예시:

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...

그러므로 나의 경험 법칙은 - 특정 연관성이없는 운영자에게는 항상 사용하십시오. foldLeft, 적어도 스칼라에서. 그렇지 않으면, 답변에 주어진 다른 조언을 가지고 가십시오;).

또한 주목할만한 가치가 있습니다 (그리고 이것이 분명한 점을 진술하고 있음을 알고 있습니다), 정류 연산자의 경우 두 사람은 거의 동일합니다. 이 상황에서 폴드가 더 나은 선택 일 수 있습니다.

Foldl :(((1 + 2) + 3) + 4) 각 작업을 계산하고 누적 된 값을 발전시킬 수 있습니다.

foldr :(1 + (2 + (3 + 4))) 스택 프레임이 열려야합니다 1 + ? 그리고 2 + ? 계산하기 전에 3 + 4, 그런 다음 돌아가서 각각의 계산을 수행해야합니다.

나는 기능적 언어 나 컴파일러 최적화에 대한 전문가가 충분하지 않아서 이것이 실제로 차이가 될지 여부를 말하지만 정류 연산자와 함께 폴드를 사용하는 것이 더 깨끗해 보입니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top