Что такое фьюжн в Хаскеле?

Question

Время от времени я замечал в документации по Haskell следующее: (например, в Data.Text):

Подлежит слиянию

Что такое фьюжн и как его использовать?

Answer 1

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

Хаскель чистый

Поскольку 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?

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

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

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

А также... Data.Text?

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

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

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

осложнения

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

 reverse (reverse xs) = xs

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

---

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

Answer 2

ТЛ;ДР:

Слияние для промежуточных структур данных — то же самое, что встраивание для функций.

Это метод оптимизации, выполняемый компилятором. Компилятору может потребоваться поддержка некоторых (иногда написанных вручную) правил преобразования, чтобы объединить больше вещей, чем только очевидные вещи.

---

Во многих императивных языках могут быть встроены только функции/подпрограммы. В Haskell можно сделать больше: встраивание функций может создавать такие забавные ситуации:

      case (if a==b then Just 42 else Nothing) of
    Just x -> print x
    Nothing -> return ()

Результат теперь будет благодаря Fusion:

      if a==b then print 42 else return ()

Чтобы чаще использовать эту оптимизацию, возможно, потребуется существование некоторых правил преобразования , например, т.е.

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

...так что и здесь можно сплавиться. Мы тогда говорим, чтоmap fиmap gвmap f . map gтакже слияние, и не только очевидным способом создания списка и его потребления, но и более глубоким: междуfиg.

Также см. https://wiki.haskell.org/GHC_optimisations#Fusion .