Оптимизации со складками

Question

Мне просто любопытно, есть ли какие-либо (только полиморфные) первого порядка оптимизации со складками.

Для карт есть обезлесение: map g (map f ls) => map (g . f) ls и rev (map f ls) => rev_map f ls (быстрее в Окамле).

Но Fold настолько мощен, что кажется, не поддается никакой оптимизации.

Answer 1

Очевидные:

fold_left f acc (List.map g li) => fold_left (fun acc x -> f acc (g x)) acc li
fold_right f li acc => fold_left f acc li (* if (f,acc) is a monoid *)

Вас может заинтересовать классическая статья на тему «Функциональное программирование с помощью бананов, линз, конвертов и колючей проволоки».Однако остерегайтесь того, что оно является техническим и имеет непроницаемую запись.

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.41.125

Редактировать: моя первая версия первого правила была неверной, отредактирована благодаря vincent-hugot.

Answer 2

Вы можете использовать вырубку лесов на сгибах.Фактически, map/map fusion является частным случаем этого.

Хитрость заключается в том, чтобы заменить построение списка специальной функцией build:

build :: (forall b. (a -> b -> b) -> b -> b) -> [a]
build g = g (:) []

Теперь, используя стандартное определениеиз foldr

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr c n []     = n
foldr c n (x:xs) = c x (foldr c n xs)

У нас есть следующий эквивалент:

foldr c n (build g) == g c n

(На самом деле это верно только при определенных, но распространенных обстоятельствах. Подробнее см. "Правильность"сокращенного слияния ").

Если вы напишите свой список производящих функций (включая map), используя build, а ваши потребители - foldr, то указанное выше равенство может удалить большинство промежуточныхсписки.Понимания списка Хаскелла переводятся в комбинации build и foldr.

Недостатком этого подхода является то, что он не может обрабатывать левые сгибы. Stream Fusion прекрасно справляется с этой задачей.Он выражает производителей списков и преобразователи как потоки (типы данных с коиндуктивностью, вроде итераторов).Вышеуказанная статья очень удобочитаема, поэтому я рекомендую взглянуть.

В статье о бананах, упомянутой gasche, более подробно рассказывается о видах складок и их эквивалентах.

Наконец, есть «Алгебра программирования» Берда и Мура , в которой упоминаются такие преобразования, как , объединяющие две складки в одну .

Answer 3

Если вам интересно углубиться в теорию, я предлагаю вам прочитать кое-что о катаморфизмах , анаморфизмах и хиломорфизмах . Хотя теория категорий, которая ее окружает, может показаться немного пугающей, концепция не так уж сложна.

Катаморфизмы - это функции, которые потребляют рекурсивные структуры данных и выдают какое-то значение. Анаморфизмы - это функции, которым дано некоторое значение (своего рода начальное число) , создающее рекурсивные структуры данных. В частности, foldr и build, упомянутые в других ответах, являются функциями для построения катаморфизмов и анаморфизмов в списках. Но эта концепция может быть применена в основном к любой рекурсивной структуре данных, такой как различные виды деревьев и т. Д.

Теперь, если вы строите рекурсивную структуру данных с анаморфизмом, а затем используете ее с катаморфизмом, вы получите то, что называется гиломорфизмом. В таком случае вам на самом деле не нужна промежуточная структура. Вы можете пропустить его создание и уничтожение. Это часто называют вырубка леса .

---

Относительно map: эта функция интересна тем, что является одновременно катаморфизмом и анаморфизмом:

• map потребляет список и производит что-то; но также
• map создает список, потребляющий что-то.

Таким образом, вы можете рассматривать композицию из двух карт map f . map g как композицию анаморфизма (map g) с катаморфизмом (map f), образующего гиломорфизм. Таким образом, вы можете оптимизировать (вырубить), не создавая промежуточный список.

Если быть точным: вы могли бы написать map двумя способами, один используя foldr, а другой используя build:

mapAna :: (a -> b) -> [a] -> [b]
mapAna f xs = build (mapAna' f xs)

mapAna' :: (a -> b) -> [a] -> (b -> c -> c) -> c -> c
mapAna' f []       cons nil = nil
mapAna' f (x : xs) cons nil = (f x) `cons` (mapAna' f xs cons nil)


mapCata :: (a -> b) -> [a] -> [b]
mapCata f xs = foldr (\x ys -> f x : ys) [] xs

и состав map f (map g zs) как mapCata f (mapAna g zs), что после некоторых упрощений и применения foldr c n (build g) == g c n приводит к map (f . g).