Платформа Haskell: вложенные функции и оптимизация

Question

Существует очень распространенная схема реализации многих функций на платформе haskell, которая меня беспокоит, но мне не удалось найти объяснения. Речь идет об использовании вложенных функций для оптимизации.

Причина, по которой вложенные функции в случаях, когда они направлены на создание хвостовой рекурсии, очень ясна для меня (как в length), но в чем цель, когда внутренняя функция имеет тот же тип, что и верхний уровень ? Это происходит, в примере, во многих функциях Data.Set module, как следующему:

-- | /O(log n)/. Is the element in the set? 
member :: Ord a => a -> Set a -> Bool 
member = go 
    where 
    STRICT_1_OF_2(go) 
    go _ Tip = False 
    go x (Bin _ y l r) = case compare x y of 
      LT -> go x l 
      GT -> go x r 
      EQ -> True 
#if __GLASGOW_HASKELL__ >= 700 
{-# INLINABLE member #-} 
#else 
{-# INLINE member #-} 
#endif 

Я подозреваю, что это может иметь что-то делать с запоминанием, но я не уверен.

---

редактировать: Так как dave4420 предполагает строгость, здесь есть определение для STRICT_1_OF_2 макрос, который можно найти в том же модуле:

-- Use macros to define strictness of functions. 
-- STRICT_x_OF_y denotes an y-ary function strict in the x-th parameter. 
-- We do not use BangPatterns, because they are not in any standard and we 
-- want the compilers to be compiled by as many compilers as possible. 
#define STRICT_1_OF_2(fn) fn arg _ | arg `seq` False = undefined 

Я понимаю, как этот макрос работает, но я до сих пор не вижу, почему go вместе с STRICT_1_OF_2(go) не следует перемещать на верхнем уровне вместо member.

Возможно, это не из-за оптимизации, а просто из-за стилистического выбора?

---

редактировать 2: Я добавил INLINABLE и INLINE часть из множества модулей. Я не думал, что с первого взгляда они могут что-то с этим сделать.

Answer 1

Непосредственное преимущество, имеющий INLINABLE (или INLINE) обертка вокруг местного работника специализация. Способ, которым member определен, на сайте вызова с фиксированным типом элемента, может быть отброшен словарь Ord, а соответствующая функция compare включена или по крайней мере передана как статический аргумент.

С непосредственно рекурсивным определением, member становится петлей выключателем и не встраивается, так называют сайт специализация не делаются - это было, по крайней мере, история до INLINABLE прагмы.

С INLINABLE прагма, места вызова специализации имеет место, словарь устранен, но у меня есть в нескольких попыток не удалось написать непосредственно рекурсивный member, что является столь же эффективным, как ток. Но с прагмой INLINE закон все еще стоит, петлевой выключатель не установлен; для member, что означает, что специализация не может быть использована для устранения словаря.

Возможно, больше не нужно писать функции в этом стиле, но это было, чтобы получить специализацию на сайте.

Answer 2

GHC не может встроить рекурсивные функции. Определен способ member, рекурсия ограничена go и member сама по себе не рекурсивна и может быть встроена.

Из GHC user guide:

GHC гарантирует, что встраивание не может продолжаться вечно: каждый взаимно рекурсивных группа разрезают одним или несколькими выключателями петли, которые не никогда встраиваемыми (см Тайны вкладки GHC, JFP 12 (4) июля 2002 года). GHC старается не выбирать функцию с помощью праймы INLINE в качестве петли , но если нет выбора, то даже функция INLINE может быть выбрана , и в этом случае прагма INLINE игнорируется. Например, для саморекурсивная функция, автоматический выключатель может быть только функцией , поэтому прагма INLINE всегда игнорируется.