Recursive functions and constant parameter closures (inlining/strictness analyzer question)

Tyson Whitehead twhitehead at
Thu May 29 23:48:11 EDT 2008

main = print $ foldl' (+) 0 [1..]


foldl' f y xs = foldl' y xs
    where foldl' y []     = y
          foldl' y (x:xs) = foldl' (f y x) xs

runs indefinitely with very little memory consumption, while

foldl' f y [] = y
foldl' f y (x:xs) = foldl' f (f y x) xs

rapidly consumes all the machine's memory and dies.

Running ghc with  -ddump-stranal shows the outer foldl' of the first 
gets inlined into main as a call to the following specialized version of 
the inner foldl':

foldl'_sSY [ALWAYS LoopBreaker Nothing] :: GHC.Num.Integer
                                           -> [GHC.Num.Integer]
                                           -> GHC.Num.Integer
[Arity 2
 Str: DmdType SS]
foldl'_sSY =
  \ (y_aj7 [ALWAYS Just S] :: GHC.Num.Integer)
    (ds_dQl [ALWAYS Just S] :: [GHC.Num.Integer]) ->
    case ds_dQl of wild_XH [ALWAYS Just A] {
      [] -> y_aj7;
      : x_aja [ALWAYS Just S] xs_ajb [ALWAYS Just S] ->
        foldl'_sSY (GHC.Num.plusInteger y_aj7 x_aja) xs_ajb

Doing the same with the second foldl' shows it to remains non-inlined 
and fully polymorphic:

foldl'_sQN [ALWAYS LoopBreaker Nothing] :: forall t_auW t_av2.
                                           (t_av2 -> t_auW -> t_av2) -> 
t_av2 -> [t_auW] -> t_av2
[Arity 3
 Str: DmdType LLS]
foldl'_sQN =
  \ (@ t_auW)
    (@ t_av2)
    (f_aj0 [ALWAYS Just L] :: t_av2 -> t_auW -> t_av2)
    (y_aj1 [ALWAYS Just L] :: t_av2)
    (ds_dQg [ALWAYS Just S] :: [t_auW]) ->
    case ds_dQg of wild_XK [ALWAYS Just A] {
      [] -> y_aj1;
      : x_aj5 [ALWAYS Just L] xs_aj6 [ALWAYS Just S] ->
        foldl'_sQN @ t_auW @ t_av2 f_aj0 (f_aj0 y_aj1 x_aj5) xs_aj6

Forcing it inline with {-# INLINE foldl' #-} just specialized it:

foldl'_sSS [ALWAYS LoopBreaker Nothing] :: (GHC.Num.Integer
                                            -> GHC.Num.Integer
                                            -> GHC.Num.Integer)
                                           -> GHC.Num.Integer
                                           -> [GHC.Num.Integer]
                                           -> GHC.Num.Integer
[Arity 3
 Str: DmdType LLS]
foldl'_sSS =
  \ (f_aj0 [ALWAYS Just L] :: GHC.Num.Integer
                              -> GHC.Num.Integer
                              -> GHC.Num.Integer)
    (y_aj1 [ALWAYS Just L] :: GHC.Num.Integer)
    (ds_dQg [ALWAYS Just S] :: [GHC.Num.Integer]) ->
    case ds_dQg of wild_XI [ALWAYS Just A] {
      [] -> y_aj1;
      : x_aj5 [ALWAYS Just L] xs_aj6 [ALWAYS Just S] ->
        foldl'_sSS f_aj0 (f_aj0 y_aj1 x_aj5) xs_aj6

I thought this was interesting.  Is it to be expected?  Am I right in 
interpreting this to mean it was just too much for the strictness 
analyzer.  I believe the first ultimately produces significantly 
superior code, so should one always write their recursive functions such 
that the constant (functional?) parameters are first captured in a closure?

In that vein, would it be useful if the compiler automatically 
transformed the second into the first?

Thanks!  -Tyson

More information about the Glasgow-haskell-users mailing list