Можно ли оптимизировать представленный случай в один цикл?

Question

Предположим, у меня есть две функции f :: [a] -> b а также g :: [a] -> c, У меня есть следующие два вопроса:

1. Если я выполню (f &&& g) xs где xs :: [a] и если оба f а также g задействовать циклы, возможно ли компилятору оптимизировать эти два цикла в один? (Обратите внимание, что я не спрашиваю, реализует ли это какой-то конкретный компилятор Haskell. Я хочу знать, возможно ли такое.)

2. Может ли traverse функция от Traverse класс type помогите мне провести такую ​​оптимизацию с чем-то вроде следующего:

   traverse (someCombinator f g) xs
   

Answer 1

Теоретически возможно оптимизировать этот код, но очень и очень сложно, потому что f а также g может потреблять различное количество входного списка. Только когда они потребляют одинаковое количество, или g всегда потребляет больше списка, чем f (или наоборот), было бы возможно выполнить оптимизацию. Проблема остановки препятствует тому, чтобы компилятор обнаружил такие условия в сложном коде.

Только в простых случаях, когда оба f а также g использование foldr например, внутренне можно было бы выполнить тривиальные оптимизации без дальнейшего самоанализа.

traverse функция здесь не поможет, потому что нет разумного способа реализации someCombinator (Как вы хотите преобразовать несколько вызовов aв один [a] без серьезных взломов? И тогда вы вернетесь, где вы начали в любом случае).

Ваш единственный реальный вариант - сделать f а также g в папки, чтобы у них были подписи f :: a -> b -> b а также g :: a -> c -> cЭто означает, что значение b а также c может быть вычислено постепенно. Вы можете использовать \ a -> f a *** g a чтобы получить папку, которую вы можете использовать в обычном (прямо в этом случае) сгибе.