haskell - Why does foldr use a helper function? -

haskell - Why does foldr use a helper function? -

in explaining foldr haskell newbies, canonical definition is

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

but in ghc.base, foldr defined as

foldr k z = go go [] = z go (y:ys) = y `k` go ys

it seems definition optimization speed, don't see why using helper function go create faster. source comments (see here) mention inlining, don't see how definition improve inlining.

i can add together of import details ghc's optimization system.

the naive definition of foldr passes around function. there's inherent overhead in calling function - when function isn't known @ compile time. it'd nice able inline definition of function if it's known @ compile time.

there tricks available perform inlining in ghc - , illustration of them. first, foldr needs inlined (i'll why later). foldr's naive implementation recursive, cannot inlined. worker/wrapper transformation applied definition. worker recursive, wrapper not. allows foldr inlined, despite recursion on construction of list.

when foldr inlined, creates re-create of of local bindings, too. it's more or less direct textual inlining (modulo renaming, , happening after desugaring pass). things interesting. go local binding, , optimizer gets within it. notices calls function in local scope, names k. ghc remove k variable entirely, , replace look k reduces to. , afterwards, if function application amenable inlining, can inlined @ time - removing overhead of calling first-class function entirely.

let's @ simple, concrete example. programme echo line of input trailing 'x' characters removed:

dropr :: char -> string -> string dropr x r = if x == 'x' && null r "" else x : r main :: io () main = s <- getline putstrln $ foldr dropr "" s

first, optimizer inline foldr's definition , simplify, resulting in code looks this:

main :: io () main = s <- getline -- i'm changing clause allow look sake of readability putstrln $ allow { go [] = ""; go (x:xs) = dropr x (go xs) } in go s

and that's thing worker-wrapper transformation allows.. i'm going skip remaining steps, should obvious ghc can inline definition of dropr, eliminating function phone call overhead. big performance win comes from.

haskell fold