Czy możliwe jest zoptymalizowanie prezentowanej obudowy w jedną pętlę?

Question

Załóżmy, że mam dwie funkcje: f :: [a] -> b i g :: [a] -> c. Mam następujące dwa pytania:

1. Gdybym wykonać (f &&& g) xs gdzie xs :: [a], a jeśli zarówno f i g obejmować pętle, czy to możliwe, że kompilator zoptymalizować te dwie pętle do jednego? (Należy pamiętać, że ja nie pytam czy jakiś specyficzny kompilator Haskell realizuje to. Chcę wiedzieć, czy coś takiego jest możliwe.)

2. Czy funkcja traverse z Traverse typu klasy pomoc mi mieć taką optymalizację z coś wzdłuż następujących linii:

   traverse (someCombinator f g) xs 
   

Answer 1

teoretycznie jest to możliwe, aby zoptymalizować ten kod, ale bardzo, bardzo trudne, ponieważ f i g może konsumować różne ilości listy wejściowej. Tylko wtedy, gdy zużyją tę samą ilość, lub g zawsze zużywa więcej z listy niż f (lub odwrotnie), byłoby to możliwe do przeprowadzenia optymalizacji. Problem zatrzymania uniemożliwia kompilatorowi wykrycie takich warunków w złożonym kodzie.

Tylko w prostych przypadkach, w których zarówno wewnętrznie, na przykład f, jak i g można użyć wewnętrznie, możliwe byłoby dokonanie drobnych optymalizacji bez dalszej introspekcji.

Funkcja traverse nie pomoże tutaj, bo nie ma rozsądny sposób wdrażania someCombinator (Jak chcesz przekształcić wiele połączeń z a „s w jednym [a] bez poważnych hacki? A potem z powrotem, gdzie rozpoczął tak czy inaczej).

Jedyną realną opcją jest, aby f i g w folderach, tak, że mają podpisy f :: a -> b -> b i g :: a -> c -> c, co oznacza, że ​​wartość b i c mogą być obliczane narastająco. Następnie można użyć numeru \ a -> f a *** g a, aby uzyskać folder, którego można użyć w zwykłym (w tym przypadku) folderze.