Почему foldr использует вспомогательную функцию?

Объясняя foldr новичкам Haskell, каноническое определение

foldr            :: (a -> b -> b) -> b -> [a] -> b
foldr _ z []     =  z
foldr f z (x:xs) =  f x (foldr f z xs)

Но в GHC.Base, foldr определяется как

foldr k z = go
          where
            go []     = z
            go (y:ys) = y `k` go ys

Кажется, это определение - оптимизация скорости, но я не понимаю, почему использование вспомогательной функции go сделает ее быстрее. Исходные комментарии (см. Здесь) указывают на inlining, но я также не вижу, как это определение улучшит inlining.

Ответ 1

Я могу добавить некоторые важные сведения о системе оптимизации GHC.

Наивное определение foldr проходит вокруг функции. Там есть накладные расходы при вызове функции - особенно когда функция не известна во время компиляции. Было бы неплохо встраивать определение функции, если она известна во время компиляции.

Есть трюки, доступные для выполнения этой вставки в GHC - и это их пример. Во-первых, foldr должен быть встроен (я получу, почему позже). foldr наивная реализация рекурсивна, поэтому не может быть встроена. Таким образом, преобразование работника/обертки применяется к определению. Рабочий является рекурсивным, но оберткой нет. Это позволяет foldr быть встроенным, несмотря на рекурсию по структуре списка.

Когда foldr встроен, он также создает копию всех своих локальных привязок. Это более или менее прямая текстовая вставка (по модулю некоторого переименования, и происходит после дезаурингового прохода). Здесь все становится интересным. go является локальным связыванием, и оптимизатор заглядывает внутрь него. Он замечает, что он вызывает функцию в локальной области, которую он называет k. GHC часто удаляет переменную k полностью и просто заменяет ее выражением k. А потом, если приложение функции поддается инлайн-инлайн, оно может быть включено в это время - удаление накладных расходов для полного вызова функции первого класса.

Посмотрим на простой, конкретный пример. Эта программа будет эхо-строку ввода со всеми завершающими символами 'x':

dropR :: Char -> String -> String
dropR x r = if x == 'x' && null r then "" else x : r

main :: IO ()
main = do
    s <- getLine
    putStrLn $ foldr dropR "" s

Во-первых, оптимизатор будет встроить определение foldr и упростить, что приведет к созданию кода, который выглядит примерно так:

main :: IO ()
main = do
    s <- getLine
    -- I'm changing the where clause to a let expression for the sake of readability
    putStrLn $ let { go [] = ""; go (x:xs) = dropR x (go xs) } in go s

И это то, что позволяет преобразование work-wrapper. Я собираюсь пропустить оставшиеся шаги, но должно быть очевидно, что GHC теперь может встроить определение dropR, устраняя служебные данные вызова функции. Именно здесь выигрывает большая производительность.

Ответ 2

GHC не может встроить рекурсивные функции, поэтому

foldr            :: (a -> b -> b) -> b -> [a] -> b
foldr _ z []     =  z
foldr f z (x:xs) =  f x (foldr f z xs)

не может быть встроен. Но

foldr k z = go
      where
        go []     = z
        go (y:ys) = y `k` go ys

не является рекурсивной функцией. Это нерекурсивная функция с локальным рекурсивным определением!

Это означает, что, как пишет @bheklilr, в map (foldr (+) 0) foldr может быть встроен и, следовательно, f и z заменены на (+) и 0 в новом go, и отлично могут произойти такие вещи, как распаковка промежуточного значения.

Ответ 3

Как говорится в комментариях:

-- Inline only in the final stage, after the foldr/cons rule has had a chance
-- Also note that we inline it when it has *two* parameters, which are the
-- ones we are keen about specialising!

В частности, обратите внимание на "мы встраиваем его, когда у него есть два параметра, которые мы очень интересуемся специализацией!"

Это говорит о том, что когда foldr становится inlined, он становится вложенным только для конкретного выбора f и z, а не для выбора списка, сложенного. Я не эксперт, но, похоже, это позволит встроить его в такие ситуации, как

map (foldr (+) 0) some_list

так что строка inline происходит в этой строке, а не после map. Это делает его оптимизируемым в большем количестве ситуаций и более легко. Вся вспомогательная функция делает маску 3-го аргумента, поэтому {-# INLINE #-} может выполнить свою задачу.

Ответ 4

Одна крошечная важная деталь, не упомянутая в других ответах, заключается в том, что GHC, учитывая определение функции, например

f x y z w q = ...

не может встроить f, пока не будут применены все аргументы x, y, z, w и q. Это означает, что часто бывает полезно использовать преобразование employee/wrapper для отображения минимального набора аргументов функции, которые должны применяться до того, как может произойти вложение.