[language-agnostic] fold-left 사용시기와 fold-right 사용시기를 어떻게 알 수 있습니까?

Program / 글쓴이

fold-left는 왼쪽으로 기울어 진 나무를 생성하고 fold-right는 오른쪽으로 기울어 진 나무를 생성한다는 것을 알고 있지만, 폴드를 위해 손을 뻗으면 어떤 종류의 폴드를 결정하려고 노력하는 동안 두통을 유발하는 생각에 빠지는 경우가 있습니다. 적절합니다. 나는 일반적으로 전체 문제를 풀고 내 문제에 적용되는 접기 기능의 구현을 단계별로 진행합니다.

그래서 제가 알고 싶은 것은 :

  • 왼쪽으로 접을 것인지 오른쪽으로 접을 것인지 결정하기위한 몇 가지 경험 규칙은 무엇입니까?
  • 내가 직면 한 문제를 고려하여 사용할 접기 유형을 신속하게 결정할 수있는 방법은 무엇입니까?

에 예가 있습니다 실시 예에 의한 스칼라 단일리스트에 요소리스트 목록을 연결하는 함수 호출 편평한 쓰기로 배를 사용 (PDF)은. 이 경우 오른쪽 접기가 올바른 선택이지만 (목록이 연결되는 방식을 고려할 때) 그 결론에 도달하기 위해 약간 생각해야했습니다.

폴딩은 (기능적) 프로그래밍에서 매우 일반적인 작업이므로 이러한 종류의 결정을 빠르고 자신있게 내릴 수 있기를 바랍니다. 그래서 … 팁이 있나요?

답변

접기를 중위 연산자 표기법 (사이에 쓰기)으로 전송할 수 있습니다.

이 예제에서는 누산기 함수를 사용하여 접기 x

fold x [A, B, C, D]

따라서

A x B x C x D

이제 연산자의 연관성에 대해 추론해야합니다 (괄호를 넣음으로써!).

왼쪽 연관 연산자 가있는 경우 다음 과 같이 괄호를 설정합니다.

((A x B) x C) x D

여기에서는 왼쪽 접기 를 사용합니다 . 예 (하스켈 스타일 의사 코드)

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

연산자가 오른쪽 연관 ( 오른쪽 접기 ) 인 경우 괄호는 다음과 같이 설정됩니다.

A x (B x (C x D))

예 : Cons-Operator

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

일반적으로 산술 연산자 (대부분의 연산자)는 왼쪽 연관이므로 foldl더 널리 사용됩니다. 그러나 다른 경우에는 중위 표기법 + 괄호가 매우 유용합니다.

답변

Olin Shivers 는 “foldl은 기본 목록 반복자”와 “foldr는 기본 목록 재귀 연산자”라고 말하며 차별화했습니다. foldl이 어떻게 작동하는지 살펴보면 :

((1 + 2) + 3) + 4

누적 기 (꼬리 재귀 반복에서와 같이)가 빌드되는 것을 볼 수 있습니다. 반대로 foldr는 다음을 진행합니다.

1 + (2 + (3 + 4))

기본 케이스 4 로의 순회를 볼 수 있고 거기에서 결과를 구축 할 수 있습니다.

그래서 저는 경험 법칙을 가정합니다. 목록 반복처럼 보이면 꼬리 재귀 형식으로 작성하기 쉬운 경우 foldl이 갈 길입니다.

그러나 실제로 이것은 사용중인 연산자의 연관성에서 가장 분명 할 것입니다. 왼쪽 연결이면 foldl을 사용하십시오. 오른쪽 연관 인 경우 foldr를 사용하십시오.

답변

다른 포스터는 좋은 답변을 받았고 이미 말한 내용을 반복하지 않겠습니다. 질문에 Scala 예제를 제공 했으므로 Scala 특정 예제를 제공하겠습니다. 으로 트릭은 이미 말했다하는 foldRight요구 보존 n-1스택 프레임을,n 목록의 길이를이 쉽게 스택 오버 플로우가 발생할 수 있습니다 – 그리고 심지어 꼬리 재귀이 당신을 절약 할 수있다.

A 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최소한 Scala에서를 사용하는 것 입니다. 그렇지 않으면 답변에 제공된 다른 조언을 따르십시오.).

답변

그것은 또한 주목할 가치가 있습니다 (그리고 이것이 명백한 것을 조금 언급하고 있음을 알고 있습니다), 교환 연산자의 경우 두 가지는 거의 동일합니다. 이 상황에서는 foldl이 더 나은 선택 일 수 있습니다.

foldl :
(((1 + 2) + 3) + 4)각 작업을 계산하고 누적 된 값을 앞으로 전달할 수 있습니다.

foldr :
(1 + (2 + (3 + 4)))스택 프레임을 열해야 1 + ?하고 2 + ?계산하기 전에 3 + 4, 다음 돌아가서 각각에 대한 계산을 할 필요가있다.

나는 이것이 실제로 차이를 만들지 여부를 말할 수있는 함수 언어 나 컴파일러 최적화에 대한 전문가로는 충분하지 않지만 교환 연산자와 함께 foldl을 사용하는 것이 확실히 더 깔끔해 보입니다.

답변