공통점
재귀적 프로시저로 구현이 가능하다.
차이점
재귀적 프로세스 vs 반복적 프로세스
모두 재귀적 프로시저로 구현가능 하지만, foldLeft 는 반복적 프로세스를 만든다. 재귀의 이전 단계에서의 계산이 다음 함수를 호출할때 인자로 주어지기 때문에 메모리에 별도의 연산을 기억할 필요가 없다.
foldRight의 경우에는 재귀적 프로세스를 만든다. 즉, 메모리에 별도의 연산을 기억하고 있다가, 종결 조건을 만나면 모두 평가된다. 예를 들어, 숫자로 이루어진sequence의 모든 수를 더하는 덧셈을 재귀적 프로세스로 구현하면 다음과 같다.
(define (sum sequence)
(if (null? sequence)
0
(let ((head (car sequence)) (tail (cdr sequence))
(+ head (sum tail))))위에처럼 + head 부분을 메모리에 가지고 있다가 한번에 평가하게 된다.
연산의 결합방향
실제 연산이 수행되는 방향으로 이름을 파악하면 된다. foldRight 는 실제 연산이 sequence의 마지막 원소부터 수행된다. 메모리에 기억된 연산자 부분이 가장 나중에 실행됨을 생각하면 쉽다.
foldLeft의 경우에는 sequence 의 첫번째 원소부터 시작된다.
결합 연산을 f 라고 하고, sequence를 (1, 2, 3, 4)이라 하고, 둘을 비교해보자.
- foldRight:
(f 1 (f 2 (f 3 4)) - foldLeft:
(f (f (f 1 2) 3) 4)
