Is it possible for the presented case to be optimized in one cycle?

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

  • If I execute (f &&& g) xs where xs :: [a] , and if both f and g are connected by loops, is it possible for the compiler to optimize these two loops into one? (Note that I am not asking if any particular Haskell compiler implements. I want to know if this is possible.)

  • Can the traverse function from a class like traverse help me to have this kind of optimization with something in the following lines:

     traverse (someCombinator fg) xs 
+6
source share
1 answer

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

Only in simple cases when, for example, f and g use foldr internally, could trivial optimizations be possible without further introspection.

The traverse function will not help you here, because there is no reasonable way to implement someCombinator (How do you want to convert several calls of a to one [a] without serious hacks? And then you returned to where you still started).

The 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 , which means that the value of b and c can be calculated step by step, then you can use \ a -> fa *** ga to get a folder that you can use in a normal (in this case) dump.

+9
source

Source: https://habr.com/ru/post/907924/


All Articles