Compilers like GHC for Haskell use inlining as one of its most important optimising tools. Doing that is not possible for recursive functions, in general. A few techniques have been developed to amend this problem, such as Stream Fusion, which allow the combination of list consuming/producing functions. Those techniques require specialised, specific algorithms and only work for a restricted set of recursive functions.

My question is: what determines which recursive functions can, and which recursive functions can not be fused that way? Is there a programming system with well-behaved recursion where any arbitrary function could be fused this way?

  • $\begingroup$ Any recursive function can be implemented alternatively as a non-recursive function. After all, hardware does not know about recursion, yet GHC manages to compile recursive functions to machine code. Concretely, you can turn any recursive function into a fancy while loop which implements the call stack of the original recursive function by hand. (Which is what GHC compiler does to convert Haskell to machine code.) So perhaps I do not understand your question because you have a particular method in mind ("fusion"). It would help to say a few words about it in your question. $\endgroup$ – Andrej Bauer Apr 23 '14 at 11:09
  • $\begingroup$ I don't understand what you mean. Please tell your technique to fuse functions such as g in evens [] = []; evens (x:xs) = (if even x then x else []) ++ evens xs; doubles [] = []; doubles (x:xs) = x*2 + doubles xs; g a = doubles (evens a) - what is your algorithm to find that g [] = []; g a = (if even x then x*2 else []) ++ g xs ? $\endgroup$ – MaiaVictor Apr 23 '14 at 16:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.