Возможно ли, чтобы представленный случай был оптимизирован в один цикл? - PullRequest
Новая
       33

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

6 голосов
/ 08 февраля 2012

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

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

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

    traverse (someCombinator f g) xs

1 Ответ

9 голосов
/ 08 февраля 2012

Теоретически возможно оптимизировать этот код, но это очень и очень сложно, потому что 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, чтобы получить папку, которую вы можете использовать в обычном (прямо в этом случае) сгибе.

...