# Is there a programming language where any arbitrary recursive function can be fused?

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?

• 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. – Andrej Bauer Apr 23 '14 at 11:09
• 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 ? – MaiaVictor Apr 23 '14 at 16:18