Czy foldRight jest odpowiednikiem foldLeft, biorąc pod uwagę nieprzyswajalną operację asocjacyjną?

Question

W kursie internetowym stwierdzono, że foldLeft i foldRight są równoważne dla operatorów, którzy są asocjacyjny i przemienny.

Jeden z uczniów jest nieugięty, że tacy operatorzy muszą być jedynie stowarzyszeni. Tak więc ta właściwość powinna być prawdziwa dla operacji takich jak skład funkcji i mnożenie macierzy.

ile można powiedzieć asocjacyjny operacji, które nie są przemienne nie będą równoważne wyniki dla foldLeft i foldRight chyba z jest obojętny, a operacja jest gromadzona w taki sposób, że kolejność argumentów pozostaje nienaruszone. IMO operacja musi być przemienna w przypadku ogólnym.

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

Więc dla foldLeft i foldRight za równoważne powinny operation być jednocześnie asocjacyjne i przemienne, czy jest to wystarczające dla operation być asocjacyjne?

Answer 1

Funkcja musi być zarówno komutatywna, jak i asocjatywna.

Jeśli nasza funkcja jest f, a nasze elementy są x1 do x4, a następnie:

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

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

Użyjmy średnią funkcję, która jest przemienne, ale nie asocjacyjne ((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 

EDYCJA: Brakowało mi łodzi tylko asocjacyjnej, a tylko przemiennej. Zobacz przykład @ jwvy w przypadku konkatenacji łańcuchów dla funkcji asocjacyjnej, ale nie przemiennej.

Answer 2

String konkatenacji („abc” + „xyz”), ale nie jest łączne przemienne foldLeft/foldRight umieści początkowej/zero elementu na przeciwległych końcach łańcucha wynikowego. Jeśli ten element zerowy nie jest pusty, wyniki są różne.

Answer 3

foldLeft jest (...(z op x1)... op xn) foldRight jest x1 op (x2 op (... xn op z)...) tak więc op musi być przemienne i asocjacyjne dla dwóch za równoważne w przypadku ogólnym

Answer 4

Istnieją co najmniej trzy istotne sprawy z oddzielnymi odpowiedzi:

1. W ogólnym przypadku, gdy op: (B, A) -> B lub op: (A, B) -> B, podobnie jak w podpisach foldLeft i foldRight, ani asocjatywność, ani komutatywność nie są określone.

2. Jeśli B >: A i z jest dwustronny tożsamość z op: (B, B) -> B i op jest asocjacyjne następnie dla wszystkich L typu List[A], L.foldLeft(z)(op) zwraca taki sam rezultat jak L.foldRight(z)(op).

   Jest to ściśle związane z faktem, że jeśli B >: A i op: (B, B) -> B następnie, jeśli op jest łączne dla wszystkich L typu List[A]L.reduceLeft(op) zwraca taki sam rezultat jak L.reduceRight(op).

3. Jeśli B >: A i op: (B, B) -> B jest zarówno asocjacyjne i przemienne następnie dla wszystkich L typu List[A] i z typu B, L.foldLeft(z)(op) zwraca taki sam rezultat jak L.foldRight(z)(op).