Is it possible for the presented case to be optimized into one loop?

Question

Suppose I have two functions f :: [a] -> b and g :: [a] -> c. I have the following two questions:

1. If I perform (f &&& g) xs where xs :: [a], and if both f and g involve loops, is it possible for the compiler to optimize these two loops into one? (Please note that I am not asking whether some specific Haskell compiler implements this. I want to know whether such a thing is possible.)

2. Can the traverse function from Traverse type class help me have such an optimization with something along the following lines:

   traverse (someCombinator f g) xs
   

Answer 1

It is theoretically possible to optimize this code, but very very difficult, because f and g might consume different amounts of the input list. Only when they consume the same amount, or g always consumes more of the list than f (or vice versa), would it be possible to perform the optimization. The Halting Problem prevents a compiler from detecting such conditions in complex code.

Only in simple cases, where both f and g use foldr internally, for example, would it be possible to perform trivial optimizations without further introspection.

The traverse function will not help you here, because there is no reasonable way of implementing someCombinator (How do you want to transform multiple calls of a's into one [a] without serious hacks? And then you are back where you started anyways).

Your only real option is to make f and g into folders, so that they have the signatures f :: a -> b -> b and g :: a -> c -> c, meaning that the value of b and c can be computed incrementally. You can then use \ a -> f a *** g a to get a folder that you can use in a conventional (right- in this case) fold.