Haskell platform: nested functions and optimization

Question

There's a very common pattern in the implementation of many functions in the haskell platform that bothers me, but I wasn't able to find an explanation. It's about the use of nested functions for optimization.

The reason for nested functions in where clauses when they aim to make tail recursion is very clear to me (as in length), but what is the purpose when the inner function has exactly the same type as the top-level one? It happens, in example, in many functions of the Data.Set module, like the following one:

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

I suspect it may have something to do with memoization, but I'm not sure.

---

edit: Since dave4420 suggests strictness, here is the definition for the STRICT_1_OF_2 macro that can be found in the same module:

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

I understand how this macro works, however I still do not see why go together with STRICT_1_OF_2(go) shouldn't be moved at top-level in place of member.

Maybe it's not because of an optimization, but simply because of a stylistic choice?

---

edit 2: I added the INLINABLE and INLINE part from the set module. I did not thought that they could have something to do with it at first glance.

Burcham

I suspect it is something to do with strictness analysis: that the compiler is expected to infer that the first argument to member must be evaluated but that the first argument to go will always already have been evaluated. But I'm not sure. – Sensualist

@dave4420: Thank you for your suggestion. I updated my question with some more infos about the strictness of the function, I hope this helps. – Burcham

I think it's purely a stylistic issue. But you might be able to make some minute gain by letting x be free in go. I don't like the style in which this has bee written, since it seems to imply that x gets seq:ed in every iteration. Also, it makes member strict in x when it doesn't have to be (but that's minor). – Braga

This is the an example of the worker wrapper style (see papers by Andy Gill and Graham Hutton), it can help the strictness analyser identify that loop variables are strict. – Leastways

Answer 1

One immediate benefit of having an INLINABLE (or INLINE) wrapper around the local worker is specialisation. The way that member is defined, at the call site, with a fixed element type, the Ord dictionary can be discarded and the appropriate compare function inlined or at least passed as a static argument.

With a directly recursive definition, member becomes a loop-breaker and isn't inlined, so call-site specialisation isn't done - that was, at least, the story before the INLINABLE pragma.

With an INLINABLE pragma, call site specialisation does take place, the dictionary is eliminated, but I have in a few attempts not managed to write a directly recursive member that is as efficient as the current. But with an INLINE pragma, the law still stands, a loop-breaker is not inlined; for member that means no call-site specialisation to eliminate the dictionary is possible.

So it may not be necessary anymore to write the functions in that style, but it was, to get call-site specialisation.

Congratulant

Answer 2

GHC cannot inline recursive functions. The way member is defined, recursion is confined to go and member itself is not recursive and can be inlined.

From the GHC user guide:

GHC ensures that inlining cannot go on forever: every mutually-recursive group is cut by one or more loop breakers that is never inlined (see Secrets of the GHC inliner, JFP 12(4) July 2002). GHC tries not to select a function with an INLINE pragma as a loop breaker, but when there is no choice even an INLINE function can be selected, in which case the INLINE pragma is ignored. For example, for a self-recursive function, the loop breaker can only be the function itself, so an INLINE pragma is always ignored.

Phalan

Thank you. With this I'm a step closer to understand, but I still do not get it. What's the point of declaring it INLINE to begin with, if all it does is call another non-inline function go? – Burcham

So, by defining a nested function we somehow allow inlining even for the recursive function member by giving GHC the chance to select go as a loop breaker, am I right? – Burcham

@Riccardo, Good point. There is some related information at hackage.haskell.org/trac/ghc/wiki/Inlining Maybe this clarifies it a bit. – Maidie

+1, thank you for the answer and the link. I'll accept Daniel's answer however, since it is more direct and comprehensive. – Burcham