foldRight與foldLeft相當於非對易關聯操作嗎？

在一個在線課程中指出foldLeft和foldRight對於關聯和交換的運營商是等效的。foldRight與foldLeft相當於非對易關聯操作嗎？

其中一位學生堅持認爲，這些操作員只需要關聯。所以這個屬性應該適用於像函數組合和矩陣乘法這樣的操作。

至於我可以告訴關聯的操作，是不可交換不會產生相同結果foldLeft和foldRight除非z是中性的，並且操作以這樣的方式積累的操作數的順序保持不變。在一般情況下，IMO的操作必須是可交換的。

list.foldLeft(z)(operation) == list.foldRight(z)(operation)

所以，foldLeft和foldRight等同應該operation是同時聯想和交換還是不夠operation進行關聯？

來源

2017-02-28 Anthony Accioly

函數必須是交換和關聯。

如果我們的功能是f，我們的元素是x1到x4，則：

foldLeft是f(f(f(x1, x2), x3), x4)

foldRight是f(x1, f(x2, f(x3, x4)))

讓我們用普通的功能，這是可交換的，但沒有關聯（(a + b)/2 == (b + a)/2）：

scala> def avg(a: Double, b: Double): Double = (a + b)/2 
avg: (a: Double, b: Double)Double 

scala> (0 until 10).map(_.toDouble).foldLeft(0d)(avg) 
res4: Double = 8.001953125 

scala> (0 until 10).map(_.toDouble).foldRight(0d)(avg) 
res5: Double = 0.9892578125

編輯：我錯過了只有關聯vs只交換的船。請參閱@ jwvy關於關聯但不可交換函數的字符串連接示例。

來源

2017-02-28 18:25:37 Tim

好的。將引用@ jwvh的字符串連接。 – Tim

String級聯（「ABC」 +「XYZ」）是締合性，但不可交換和foldLeft/foldRight將初始/零元件放置在所產生的串的相對端。如果該零元素不是空字符串，那麼結果是不同的。

來源

2017-02-28 18:25:49 jwvh

foldLeft是(...(z op x1)... op xn) foldRight是x1 op (x2 op (... xn op z)...) 所以op需求是可交換和關聯兩個是在一般情況下，相當於

來源

2017-02-28 18:26:06 radumanolescu

至少有三個相關的情況下有獨立的答案：

在op: (B, A) -> B或op: (A, B) -> B的一般情況下，如在foldLeft和foldRight的簽名中，結合性和交換性都不是定義。
如果B >: A和z是op: (B, B) -> B和op雙面身份是締然後List[A]類型的所有L，L.foldLeft(z)(op)返回相同的結果作爲L.foldRight(z)(op)。

這是密切相關的事實，如果B >: A和op: (B, B) -> B然後，如果op是關聯的，對類型的所有LList[A]L.reduceLeft(op)返回相同的結果L.reduceRight(op)。
如果B >: A，和op: (B, B) -> B既是締和交換然後List[A]類型的所有L和B類型的z，L.foldLeft(z)(op)返回相同的結果作爲L.foldRight(z)(op)。

來源

2017-03-01 07:17:48 Elroch

foldRight與foldLeft相當於非對易關聯操作嗎？

回答

相關問題