Racket : foldr을 사용하여 foldl을 작성하는 방법

Question

나는 현재 시험 준비 중이고 foldr로 foldl을 작성하는 것이 좋은 테스트가 될 것이라고 생각합니다. 여하튼

, 난 알고 (foldl F 형베이스 LST) 반환 (f를 XN (FX LST되면서 (N-1)... (F X1에 기재) (X1,... XN)

그래서 나는 현재하고있는 것은 이것이다 :.

(define (foldl/w/foldr f base lst) 

(foldr (lambda (x y) (f y (f x base))) base lst))) 

이하지 않습니다 잘 작동, 나는 계속 할 수 있겠군요 오전

Answer 1

사용 하스켈의 documentation 출발점으로 (코멘트에 @soegaard에서 언급 한 바와 같이), 여기에 사용 라켓 구문이 문제에 대한 작업 솔루션입니다 : 예를 들어

(define (foldl/w/foldr f base lst) 
    ((foldr (λ (ele acc) (λ (x) (acc (f ele x)))) 
      identity 
      lst) 
    base)) 

:

(foldl/w/foldr cons '() '(1 2 3 4 5)) 
=> '(5 4 3 2 1) 
(foldl/w/foldr + 0 '(1 2 3 4 5)) 
=> 15 

이것을 이해하는 열쇠는 값이 아닌 지연 계산을 사용하여 람다을 누적하는 것이며 결국에는 계산을 시작하기 위해 기본 값을 전달하는 모든 람다 체인을 호출합니다. 또한 identity 절차가 첫 번째 누산기로 사용되며 더 많은 램버스가 누적됩니다. 예를 들어,이 호출 :

(foldl/w/foldr + 0 '(1 2)) 

로 평가 될 것인가는 다음과

((lambda (x)    ; this lambda is the value returned by foldr 
    ((lambda (x) 
     (identity (+ 1 x))) ; add first element in the list (this gets executed last) 
    (+ 2 x)))    ; add second element in the list (this gets executed first) 
0) ; at the end, we invoke the chain of lambdas starting with the base value 
=> 3 

Answer 2

나는 리스프 프로그래머가 아니다, 그래서 이것은 아마도 문법적으로 완벽하지하지만

와 비슷할 것입니다.

foldl f a l = (foldr (lambda (h p) (lambda (x) (p (f x h)))) 
        l 
        (lambda (x) (x)) 
        a)) 

트릭은 결과 값 대신 함수를 누적하는 것입니다. foldr에 네 개의 인수를 적용합니다.이 경우에는 일반 foldr이 함수를 반환하기 때문에 "a"가 인수로 사용됩니다.