plataforma Haskell: funciones anidadas y optimización

Question

Hay un patrón muy común en la implementación de muchas funciones en la plataforma haskell que me molesta, pero no pude encontrar una explicación. Se trata del uso de funciones anidadas para la optimización.

La razón de funciones anidadas en las cláusulas WHERE cuando su objetivo es hacer que la recursión de cola es muy claro para mí (como en length), pero lo que es el objetivo cuando la función interior tiene exactamente el mismo tipo que el de alto nivel uno ? Sucede, en el ejemplo, en muchas funciones del Data.Set module, como la siguiente:

-- | /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 

sospecho que puede tener algo que ver con memoization, pero no estoy seguro.

---

edición: Desde dave4420 sugiere rigor, aquí es la definición para el STRICT_1_OF_2 macro que se pueden encontrar en el mismo módulo:

-- 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 

entiendo cómo funciona esta macro funciona, sin embargo todavía no veo por qué go junto con STRICT_1_OF_2(go) no deben moverse al nivel superior en lugar de member.

Tal vez no sea por una optimización, sino simplemente por una elección estilística.

---

edición 2: He añadido la parte INLINABLE y INLINE desde el módulo de conjunto. No pensé que podrían tener algo que ver con eso a primera vista.

Answer 1

Un beneficio inmediato de tener un INLINABLE (o INLINE) envoltorio sobre el trabajador local es la especialización. La forma en que se define member, en el sitio de la llamada, con un tipo de elemento fijo, el diccionario Ord se puede descartar y la función compare correspondiente está en línea o al menos aprobada como un argumento estático.

Con una definición recursiva directa, member se convierte en un bucle automático y no se colocarán en línea, por lo que llaman el lugar especialización no se hace - que era, al menos, la historia antes de la INLINABLE pragma.

Con una INLINABLE pragma, la especialización sitio de llamada tiene lugar, el diccionario se elimina, pero tengo en unos pocos intentos no logró escribir un directamente recursiva member que es tan eficiente como el actual. Pero con un pragma INLINE, la ley sigue en pie, un interruptor automático no está incluido; para member eso significa que no es posible especializar al sitio de llamada para eliminar el diccionario.

Puede que ya no sea necesario escribir las funciones en ese estilo, pero sí para obtener una especialización en el sitio de llamada.

Answer 2

GHC no puede alinear funciones recursivas. La forma en que se define member, la recursión se limita a go y member no es recursiva y puede estar en línea.

Desde el GHC user guide:

GHC asegura que la expansión en línea no puede seguir para siempre: cada grupo mutuamente recursivo se corta por uno o más interruptores de bucle que se Nunca inline (ver Secretos del revestimiento interior GHC, JFP 12 (4) julio de 2002). GHC trata de no seleccionar una función con un pragma LÍNEA como un bucle interruptor, pero cuando no hay otra opción, incluso una función en línea puede ser seleccionado, en cuyo caso se ignora el pragma EN LÍNEA. Por ejemplo, para una función recursiva, el interruptor automático solo puede ser la función , por lo que siempre se ignora un pragma INLINE.