사서의 장부

때로는 시퀀스를 값 하나로 합치고 싶을 때가 있고, 때로는 그 과정에서 만들어지는 모든 중간 값을 보고 싶을 때가 있어요. Factor는 이 둘을 두 가지 도구로 나눠요. 값 하나로 접어 내리는 sequences의 reduce와, 누적 형태를 위한 math.statistics의 누적 함수군이에요.

reduce: 일반적인 접기

reduce ( seq init quot: ( prev elt -- next ) -- result )

reduce는 시퀀스를 한 번에 하나씩 훑으면서 누적되는 결과(누산기)를 함께 들고 다니다가, 인자를 두 개 받는 콰테이션에 넘겨요. 콰테이션은 지금까지의 누산기와 다음 원소를 받고, 스택에 남긴 값이 새로운 누산기가 돼요.

USING: math sequences ;

{ 1 2 3 4 } 0 [ + ] reduce .         ! => 10
{ 1 2 3 4 } 1 [ * ] reduce .         ! => 24

0이 아닌 초깃값과 직접 만든 결합 함수는 sum과 product로는 닿을 수 없는 reduce의 부분이에요. 예를 들어, 그 값을 넘어서는 원소가 없을 때를 대비한 기본값을 두고 시퀀스의 최댓값을 구할 수 있어요:

USING: math.order ;

{ 3 1 -4 5 -2 } 0 [ max ] reduce .   ! => 5
{ -3 -1 -4 }    0 [ max ] reduce .   ! => 0

초깃값 0도 비교에 참여해요. 모든 원소가 0보다 작으면 0이 결과가 되기 때문에, 값이 전부 음수인 시퀀스도 임의의 가장 작은 값이 아니라 0을 만들어 내요.

누적 연산

때로는 마지막 결과가 아니라 모든 중간 결과가 필요할 때가 있어요. math.statistics의 누적 함수군은 입력과 길이가 같은 시퀀스를 반환하는데, 각 위치에는 그 위치에서 끝나는 앞부분을 누적한 값이 들어 있어요:

cum-sum     ( seq -- newseq )    ! running total
cum-product ( seq -- newseq )    ! running product
cum-min     ( seq -- newseq )    ! running minimum
cum-max     ( seq -- newseq )    ! running maximum

USING: math.statistics ;

{ 3 1 4 1 5 9 2 6 } cum-sum .        ! => { 3 4 8 9 14 23 25 31 }
{ 1 2 3 4 } cum-product .            ! => { 1 2 6 24 }
{ 3 1 4 1 5 9 2 6 } cum-min .        ! => { 3 1 1 1 1 1 1 1 }
{ 3 1 4 1 5 9 2 6 } cum-max .        ! => { 3 3 4 4 5 9 9 9 }

유용한 패턴은 누적 연산을 연쇄하는 거예요. 한 연산의 출력이 그 자체로 시퀀스라서 다음 연산에 바로 넣을 수 있죠. 덕분에 "누적 요약의 누적 요약"을 단어 두 개로 표현할 수 있어요. 조합은 자유로워요. 각 단계가 무엇을 요약하는지에 따라 짝을 지어 주면 돼요.

produce: 펼치기

reduce는 시퀀스를 값 하나로 소비해요. sequences의 produce는 반대 방향으로 움직여요. 초깃값에서 시작해 검사와 갱신을 반복하면서 시퀀스를 생성하죠:

produce ( pred quot -- seq )

각 반복은 먼저 현재 상태에 술어 pred를 실행해요. 결과가 참이면 quot를 호출해서 다음 원소를 만들고 상태를 갱신해요. pred가 f를 반환하면 반복을 멈추고, 그동안 모은 원소를 반환해요.

고전적인 예로 피보나치 수열이 있어요(각 수는 앞의 두 수를 더한 값이에요). 누적되는 상태는 (a, b)라는 쌍이에요. 각 단계는 b를 내보내고, 쌍을 (b, a + b)로 바꿔요:

USING: kernel math sequences ;

! Fibonacci numbers strictly below 100:
0 1 [ dup 100 < ] [ tuck + over ] produce 2nip .
! => { 1 1 2 3 5 8 13 21 34 55 89 }

누적되는 상태가 값 두 개에 걸쳐 있어서, 본문에서는 쌍을 다음 단계로 진행시키려고 tuck(kernel에 있어요. 맨 위 값을 두 번째 값 아래로 복사하는 세 요소 셔플이에요)을 쓰고, 마지막에는 2nip(역시 kernel에 있고, nip에 대응하는 두 요소 버전이에요)으로 정리해요. 호출을 왼쪽에서 오른쪽으로 읽어 보면:

• 술어 [ dup 100 < ]는 쌍의 맨 위 값(다음에 내보낼 수)을 살펴보고, 그 값이 아직 상한보다 작은 동안 계속해요.
• 본문 [ tuck + over ]는 상태를 (b, a + b)로 진행시키고 b를 내보내요. 그러면 스택에는 값 세 개가 남아요. 아래에는 새로운 쌍이, 맨 위에는 내보낸 수가 있어요.
• produce가 멈춘 뒤에는 꼬리에 남은 값 두 개(마지막 쌍)를 2nip로 버려서, 만들어진 시퀀스만 남겨요.

produce는 reduce의 정확한 쌍대예요. reduce가 시퀀스를 값 하나로 접어 내린다면, produce는 값 하나에서 시퀀스를 펼쳐 올려요.