Что такое слияние в Haskell?

Ответ 1

В целом, слияние относится к преобразованиям, целью которых является избавление от промежуточных структур данных. Вы платите функциональные вызовы, которые приводят к расточительному распределению памяти во что-то более эффективное. Это на самом деле ИМО одно из самых больших применений Haskell, являющееся чистым. И вам в значительной степени не нужно ничего делать, чтобы получить его, он поставляется бесплатно через компилятор GHC.

Haskell является чистым

Поскольку Haskell является чистым, мы получаем эту ссылку под названием ссылочной прозрачности, которая (по ссылке) означает, что выражение всегда оценивает тот же результат в любом контексте " ¹. Это означает, что я могу делать очень общие манипуляции с программным уровнем без изменения того, что программа будет выводить. Например, даже не зная, что x, y, z и w, я всегда знаю, что

 ((x ++ y) ++ z) ++ w

будет оценивать то же, что и

 x ++ (y ++ (z ++ w))

но второй на практике будет включать меньше распределений памяти (поскольку x ++ y требует перераспределения всего префикса выходного списка).

Переписать правила

На самом деле, существует такая оптимизация, которую мы можем сделать, и, поскольку Haskell является чистым, мы можем просто просто перемещать целые выражения (заменяя x, y, z или w для фактических списков или выражений, которые оценивают списки в приведенном выше примере, ничего не меняет). Это становится довольно механическим процессом.

Кроме того, оказывается, что вы можете придумать много эквивалентов для функций более высокого порядка (Теоремы бесплатно!). Например,

map f (map g xs) = map (f . g) xs

независимо от того, что f, g и xs (обе стороны семантически равны). И все же, в то время как две стороны этого уравнения производят одинаковый вывод значения, левая сторона всегда хуже по эффективности: она выделяет пространство для промежуточного списка map g xs, который немедленно отбрасывается. Мы хотели бы сообщить компилятору, когда он встречается с чем-то вроде map f (map g xs), замените его на map (f . g) xs. И для GHC, то есть через переписать правила:

{-# RULES     "map/map"    forall f g xs.  map f (map g xs) = map (f.g) xs #-}

f, g и xs могут быть сопоставлены с любыми выражениями, а не только с переменными (поэтому что-то вроде map (+1) (map (*2) ([1,2] ++ [3,4])) преобразуется в map ((+1) . (*2)) ([1,2] ++ [3,4]). (Не существует подходящего способа поиска правил перезаписи, поэтому я составил список). В этой статье объясняется мотивация и выполнение правил перезаписи GHC.

Итак, как GHC оптимизирует map?

Собственно, не совсем. Дело выше короткое сокращение fusion. Название рода подразумевает недостаток: он недостаточно масштабируется и раздражает отладки. В итоге вы должны написать тонну специальных правил для всех аранжировок одних и тех же общих функций. Затем вы надеетесь, что повторное применение правил перезаписи упростит ваши выражения.

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

Вероятно, самая передовая из этих систем - stream fusion, нацеленная на коиндуктивные последовательности (в основном ленивые последовательности, такие как списки). Отметьте этот тезис и этот документ (который на самом деле довольно как реализуется пакет vector). Например, в vector ваш код сначала преобразуется в промежуточную форму с Stream и Bundle s, оптимизируется в этой форме, а затем преобразуется обратно в векторы.

И... Data.Text?

Data.Text использует слияние потоков, чтобы минимизировать количество распределений памяти, которые происходят (я думаю, что это особенно важно для строгого варианта). Если вы посмотрите источник, вы увидите, что функции "subject to fusion" фактически управляют Stream s (они имеют общий вид unstream . (stuff manipulating stream) . stream), а для преобразования Stream s существует пучок RULES прагм. В конце концов, любая комбинация этих функций должна быть сплавлена ​​так, что должно произойти только одно распределение.

Итак, что мне нужно убрать для ежедневного кодирования?

Единственный реальный способ узнать, когда ваш код подлежит слиянию, - это хорошее понимание правил перезаписи и понимание того, как работает GHC. Тем не менее, есть одна вещь, которую вы должны сделать: попытайтесь использовать нерекурсивные функции более высокого порядка, когда это возможно, поскольку они могут быть (по крайней мере пока, но в целом всегда будут более) легко сливаться.

Осложнения

Поскольку слияние в Haskell происходит посредством повторного применения правил перезаписи, достаточно убедить себя в правильности каждого правила перезаписи, чтобы знать, что вся "плавленная" программа выполняет то же, что и ваша оригинальная программа. За исключением случаев, связанных с завершением программ. Например, можно подумать, что

 reverse (reverse xs) = xs

но это явно неверно, так как head $ reverse (reverse [1..]) не закончится, но head [1..] будет. Дополнительная информация из Haskell Wiki.

¹ Это действительно верно только при условии, что в этих контекста выражение поддерживает тот же тип.