Реєстр бібліотекаря

Іноді нам хочеться поєднати послідовність в одне значення, а іноді хочеться побачити кожне проміжне значення, яке поєднання утворює дорогою. Factor розділяє їх на два інструменти: reduce (у sequences) для згортки в одне значення, і кумулятивну родину в 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

Ненульове початкове значення і власний комбінатор - це ті частини reduce, до яких sum і product не дістаються. Наприклад, найбільше значення в послідовності, з типовим значенням, якщо жодне значення його не перевищує:

USING: math.order ;

{ 3 1 -4 5 -2 } 0 [ max ] reduce .   ! => 5
{ -3 -1 -4 }    0 [ max ] reduce .   ! => 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 споживає послідовність у значення. produce (у sequences) іде в інший бік: породжує послідовність із початкового значення, раз за разом перевіряючи та роблячи крок:

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 розгортає значення до послідовності.