Fold (функція вищого порядку)

У функційному програмуванні термін fold (також відомий як reduce, accumulate, aggregate, compress або inject) позначає сімейство функцій вищого порядку, які аналізують рекурсивну структуру даних і за допомогою заданої операції об’єднання рекурсивно обробляють її складові частини, поступово формуючи значення, що повертається. Зазвичай fold отримує на вхід функцію-об'єднувач, вузол структури даних (наприклад, верхній елемент дерева), а також, можливо, деякі значення за замовчуванням, які використовуються в певних умовах. Потім fold систематично поєднує елементи ієрархії структури даних, використовуючи цю функцію.

Fold певною мірою є дуальним до unfold, яка бере початкове значення і застосовує функцію корекурсивно для поступової побудови корекурсивної структури даних. У той час як fold рекурсивно розкладає структуру, замінюючи її результатами застосування функції об'єднання до термінальних значень і результатів рекурсії (це називається катаморфізмом), unfold діє навпаки й реалізує анаморфізм.

Функція-об'єднувач та початкове значення

• Якщо функція-об'єднувач є несиметричною відносно типів своїх аргументів (наприклад (a → b) → b), тобто тип результату відрізняється від типу елементів структури, то початкове значення є необхідним.
• Якщо функція-об'єднувач є магмою, тобто є симетричною відносно типів своїх аргументів ((a → a) → a), то початкове значення не є необхідним, і замість нього можна використати значення початкового вузла.

Обхід структури даних

Список — лінійна структура даних, що дозволяє обхід елементів у двох напрямках. Тому існує 2 варіанти функції fold: foldl та foldr.

Обхід від голови до хвоста списку.

Обхід від хвоста до голови списку.

Для дерев існує декілька варіантів обходу, тому є декілька варіантів функції fold, а також функція-об'єднувач може бути тернарною.

Див. також

• Функція вищого порядку
• Filter (функція вищого порядку)
• Map (функція вищого порядку)

Джерела

• А. Філд, П. Харрісон Функціональне програмування: Пер. з англ. - М.: Мир, 1993. - 637 с, іл. ISBN 5-03-001870-0.