是否可以將呈現的情況優化爲一個循環？

假設我有兩個函數f :: [a] -> b和g :: [a] -> c。我有以下兩個問題：是否可以將呈現的情況優化爲一個循環？

如果我執行(f &&& g) xs其中xs :: [a]，如果兩個f和g涉及循環，有可能是編譯器這兩個循環優化成一個？（請注意，我不是問一些具體的Haskell編譯是否實現了這一點。我想知道這樣的事情是否是可能）
可以從Traverse型類的幫助traverse功能我有這樣的優化大意如下的內容：
```
traverse (someCombinator f g) xs 
```

2012-02-08 missingfaktor

我認爲像1中的優化可以由超級編譯器執行。 – Landei 2012-02-08 13:23:37

這在理論上是可以優化的代碼，但非常非常困難的，因爲f和g可能會消耗不同數量的輸入列表中。只有當它們消耗相同數量時，或者g總是會消耗比f更多的列表（反之亦然），纔有可能執行優化。停機問題阻止編譯器檢測複雜代碼中的這些情況。

只有在簡單的情況下，其中兩個fg和使用foldr內部，例如，那會是可能的，無需進一步內省進行瑣碎優化。

的traverse功能將不會幫助你在這裏，因爲這裏是實現someCombinator（你怎麼想的a的多次調用轉換成一個[a]沒有嚴重的黑客沒有合理的辦法嗎？然後你是回到開始的地方無論如何）。

你唯一的選擇就是讓f和g到文件夾，使他們有簽名f :: a -> b -> b和g :: a -> c -> c，這意味着的b和c值可以逐步計算。然後，您可以使用\ a -> f a *** g a來獲取您可以在常規（在此情況下）摺疊中使用的文件夾。

來源

2012-02-08 10:50:45 dflemstr

很棒的回答。非常感謝！我發佈這個問題，因爲我想檢查是否我在[這個線程]中說（http://stackoverflow.com/questions/9162256/cartesian-product-traverse-in-scalaz/9162706#9162706）（在答案和在評論中）是正確的。 – missingfaktor 2012-02-08 11:59:55

是否可以將呈現的情況優化爲一個循環？

回答

相關問題