Может ли GHC действительно никогда не включать карту, scanl, foldr и т.д.?

Ответ 1

В самом деле, GHC в настоящее время не может выполнять встроенные рекурсивные функции. Однако:

• GHC будет по-прежнему специализироваться на рекурсивных функциях. Например, данный

  fac :: (Eq a, Num a) => a -> a
  fac 0 = 1
  fac n = n * fac (n-1)
  
  f :: Int -> Int
  f x = 1 + fac x
  

  GHC обнаружит, что fac используется в типе Int -> Int и генерирует специализированную версию fac для этого типа, которая использует быструю целочисленную арифметику.

  Эта специализация происходит автоматически внутри модуля (например, если fac и f определены в том же модуле). Для кросс-модульной специализации (например, если f и fac определены в разных модулях), отметьте специализированную функцию INLINABLE pragma:

  {-# INLINABLE fac #-}
  fac :: (Eq a, Num a) => a -> a
  ...
  

• Существуют ручные преобразования, которые делают функции нерекурсивными. Методом наименьшей мощности является преобразование статического аргумента , которое применяется к рекурсивным функциям с аргументами, которые не меняются при рекурсивных вызовах (например, функции порядка, такие как map, filter, fold*). Это преобразование превращается в

  map f []     = []
  map f (x:xs) = f x : map f xs
  

  в

  map f xs0 = go xs0
    where
      go []     = []
      go (x:xs) = f x : go xs
  

  чтобы вызов типа

   g :: [Int] -> [Int]
   g xs = map (2*) xs
  

  будет иметь map inlined и стать

   g [] = []
   g (x:xs) = 2*x : g xs
  

  Это преобразование применяется к функциям Prelude, таким как foldr и foldl.

• Методы Fusion также делают многие функции нерекурсивными и более мощными, чем статическое преобразование аргументов. Основным подходом для списков, который встроен в Prelude, является shortcut fusion. Основной подход состоит в том, чтобы записать как можно больше функций как нерекурсивные функции, которые используют foldr и/или build; то вся рекурсия фиксируется в foldr, и для foldr существуют специальные ПРАВИЛА.

  Преимущество этого слияния в принципе легко: избегайте ручной рекурсии, предпочитая библиотечные функции, такие как foldr, map, filter и любые функции в этот список. В частности, написание кода в этом стиле создает код, который "одновременно быстр и изящен".

• Современные библиотеки, такие как text и vector используйте поток слияния за кулисами. Дон Стюарт написал пару сообщений в блоге (1, 2), демонстрируя это в действии в ныне устаревшей библиотеке uvector, но те же принципы применяются к тексту и вектору.

  Как и с быстрым слиянием, использование потокового слияния в тексте и векторе в принципе легко: избегайте ручной рекурсии, предпочитая библиотечные функции, которые были помечены как "подлежащие слиянию".

• Продолжается работа по совершенствованию GHC для поддержки встраивания рекурсивных функций. Это подпадает под общий заголовок суперкомпиляции, и недавняя работа над этим, по-видимому, была проведена Max Bolingbroke и Нейл Митчелл.

Ответ 2

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

Рассмотрим Data.List.map. Базовый пакет определяет map как

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

Этот map является саморекурсивным, поэтому GHC не будет его встроить.

Однако base также определяет следующие правила перезаписи:

{-# RULES
"map"       [~1] forall f xs.   map f xs                = build (\c n -> foldr (mapFB c f) n xs)
"mapList"   [1]  forall f.      foldr (mapFB (:) f) []  = map f
"mapFB"     forall c f g.       mapFB (mapFB c f) g     = mapFB c (f.g) 
  #-}

Это заменяет использование map через foldr/build fusion, тогда, если функция не может быть сплавлена, заменяет ее исходным map. Поскольку слияние происходит автоматически, это не зависит от того, как пользователь знает об этом.

Как доказательство того, что все это работает, вы можете изучить, что GHC производит для конкретных входных данных. Для этой функции:

proc1 = sum . take 10 . map (+1) . map (*2)

eval1 = proc1 [1..5]
eval2 = proc1 [1..]

при компиляции с -O2, GHC объединяет все proc1 в одну рекурсивную форму (как видно на выходе ядра с помощью -ddump-simpl).

Конечно, существуют ограничения на то, что могут сделать эти методы. Например, наивная средняя функция mean xs = sum xs / length xs легко преобразуется вручную в одну складку, и существуют рамки, которые могут делать это автоматически, однако на не существует известного способа автоматического перевода между стандартными функциями и фьюжн-картой. Поэтому в этом случае пользователь должен знать ограничения кода, созданного компилятором.

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

Ответ 3

для саморекурсивной функции, автоматический выключатель цикла может быть только самой функцией, поэтому прагма INLINE всегда игнорируется.

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

Тем не менее, не все это резко ограничивает нашу способность писать код, который одновременно быстрый и элегантный?

Существуют определенные методы, которые могут сделать рекурсивные вызовы намного, намного быстрее, чем их нормальная ситуация. Например, оптимизация хвостового вызова fooobar.com/info/3525/... Wiki