Suppose I have two functions f :: [a] -> b
and g :: [a] -> c
. I have the following two questions:
If I perform
(f &&& g) xs
wherexs :: [a]
, and if bothf
andg
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.)Can the
traverse
function fromTraverse
type class help me have such an optimization with something along the following lines:traverse (someCombinator f g) xs
It is theoretically possible to optimize this code, but very very difficult, because
f
andg
might consume different amounts of the input list. Only when they consume the same amount, org
always consumes more of the list thanf
(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
andg
usefoldr
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 implementingsomeCombinator
(How do you want to transform multiple calls ofa
's into one[a]
without serious hacks? And then you are back where you started anyways).Your only real option is to make
f
andg
into folders, so that they have the signaturesf :: a -> b -> b
andg :: a -> c -> c
, meaning that the value ofb
andc
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.