scala - que - Doblar y doblar la diferencia del método izquierdo

planchadora automatica

Question

No estoy seguro de cuál es la diferencia entre fold y foldLeft en Scala.

La pregunta ¿ Diferencia entre fold y foldLeft o foldRight? tiene una respuesta que habla de ordenar. Eso es comprensible Pero todavía no entiendo por qué esto funciona (de REPL):

scala> Array("1","2","3").foldLeft(0)(_ + _.toInt)
res6: Int = 6

pero esto no:

scala> Array("1","2","3").fold(0)(_ + _.toInt)
<console>:8: error: value toInt is not a member of Any
Array("1","2","3").fold(0)(_ + _.toInt)
^

que significa este mensaje de error?

Esta línea de la documentación también es confusa para mí.

z - un elemento neutral para la operación de plegado; puede agregarse al resultado un número arbitrario de veces, y no debe cambiar el resultado (por ejemplo, Nil para la concatenación de la lista, 0 para la suma o 1 para la multiplicación).

¿Por qué se agregará un número arbitrario de veces ? Pensé que doblar funciona de manera diferente.

Answer 1

Diferencia general

Aquí están los prototipos de los métodos

fold[A1 >: A](z: A1)(op: (A1, A1) ⇒ A1): A1
foldLeft[B](z: B)(f: (B, A) ⇒ B): B

Entonces, para doblar, el resultado es de tipo A1 >: A lugar de cualquier B Por otra parte, como se especifica en el documento, para fold el orden no es

Acerca de su error

Al escribir scala> Array("1","2","3").fold(0)(_ + _.toInt) que 0 , un int es un subtipo de String . Esta es la razón por la cual el compilador arroja un error.

Acerca de la extraña z en doblez

Aquí tenemos que ver la implementation de fold para entender lo que sucede. Esto es lo que obtenemos:

def fold[A1 >: A](z: A1)(op: (A1, A1) => A1): A1 = foldLeft(z)(op)

Entonces, básicamente, fold es una implementación de foldleft con una restricción en el tipo de salida. Ahora podemos ver que z usará en la práctica de la misma manera que en foldleft . Entonces, podemos concluir que este comentario fue realizado porque nada garantiza ese comportamiento en futuras implementaciones. Ya lo podemos ver ahora, con parallels :

def fold[U >: T](z: U)(op: (U, U) => U): U = {
executeAndWaitResult(new Fold(z, op, splitter))
}

Answer 2

Como señala otra respuesta, el método de fold está principalmente allí para soportar un doblez paralelo. Puedes ver esto de la siguiente manera. Primero podemos definir un tipo de contenedor para enteros que nos permite hacer un seguimiento de las operaciones que se han realizado en sus instancias.

case class TrackInt(v: Int) {
val log = collection.mutable.Buffer.empty[Int]
def plus(that: TrackInt) = {
this.log += that.v
that.log += this.v
new TrackInt(this.v + that.v)
}
}

A continuación, podemos crear una colección paralela de estas cosas y un elemento de identidad:

val xs = (1 to 10).map(TrackInt(_)).par
val zero = TrackInt(0)

Primero probaremos foldLeft :

scala> xs.foldLeft(zero)(_ plus _)
res0: TrackInt = TrackInt(55)
scala> zero.log
res1: scala.collection.mutable.Buffer[Int] = ArrayBuffer(1)

Por lo tanto, nuestro valor cero solo se usa una vez, como era de esperar, ya que foldLeft realiza un doblez secuencial. A continuación, podemos borrar el registro e intentar fold :

scala> zero.log.clear()
scala> xs.fold(zero)(_ plus _)
res2: TrackInt = TrackInt(55)
scala> zero.log
res3: scala.collection.mutable.Buffer[Int] = ArrayBuffer(1, 6, 2, 7, 8)

Entonces, podemos ver que el doblez se ha paralelizado de tal manera que el valor cero se usa varias veces. Si ejecutamos esto de nuevo, es probable que veamos valores diferentes en el registro.

Answer 3

NOTA: podría estar completamente equivocado aquí. Mi scala es menos que perfecto.

Creo que la diferencia está en la firma de los métodos:

def fold[A1 >: A](z: A1)(op: (A1, A1) ⇒ A1): A1

vs

def foldLeft[B](z: B)(op: (B, T) ⇒ B): B

En resumen, fold se define como operar en algún tipo A1 que es un supertipo del tipo de matriz, que para su matriz de cadenas el compilador define como "Cualquiera" (probablemente porque necesita un tipo que pueda almacenar su String o un int-notice que el método combinado pasado a fold Fold toma dos parámetros del mismo tipo?) Eso es también lo que significa la documentación cuando se trata de z- la implementación de Fold podría ser tal que combine tus entradas en paralelo, por ejemplo:

"1" + "2" --/
--> 3 + 3 -> 6
"3" + *z* --/

Por otro lado, foldLeft opera en tipo B (no restringido) y solo le pide que proporcione un método combinador que tome un parámetro de tipo B y otro del tipo de su matriz (String, en su caso) y produzca un B.

Answer 4

No estoy familiarizado con Scala, pero la biblioteca de colecciones de Scala tiene un diseño similar al de Haskell. Esta respuesta se basa en Haskell y probablemente también sea precisa para Scala.

Debido a que foldLeft procesa sus entradas de izquierda a derecha, puede tener diferentes tipos de entrada y salida. Por otro lado, fold puede procesar sus entradas en varios órdenes y, por lo tanto, todas las entradas y salidas deben tener el mismo tipo. Esto es más fácil de ver al expandir las expresiones de doblez. foldLeft opera en un orden específico:

Array("1","2","3").foldLeft(0)(_ + _.toInt)
= ((0 + "1".toInt) + "2".toInt) + "3".toInt

Tenga en cuenta que los elementos de la matriz nunca se utilizan como el primer parámetro de la función de combinación. Siempre aparecen a la derecha del + .

fold no garantiza un orden específico. Podría hacer varias cosas, como:

Array("1","2","3").fold(0)(_ + _.toInt)
= ((0 + "1".toInt) + "2".toInt) + "3".toInt
or (0 + "1".toInt) + ("2" + "3".toInt).toInt
or "1" + ("2" + ("3" + 0.toInt).toInt).toInt

Los elementos de matriz pueden aparecer en cualquiera de los parámetros de la función de combinación. Pero su función de combinación espera que su primer argumento sea un int. Si no respetas esa restricción, ¡terminas agregando cadenas a los enteros! Este error es capturado por el sistema de tipo.

El elemento neutro se puede introducir varias veces porque, en general, se implementa un doblez paralelo dividiendo la entrada y ejecutando múltiples pliegues secuenciales. Un doblez secuencial introduce el elemento neutral una vez. Imagina una ejecución particular de Array(1,2,3,4).fold(0)(_ + _) donde la matriz se divide en dos matrices separadas, y estas se doblan secuencialmente en dos subprocesos. (Por supuesto, la función de fold real no escinde la matriz en múltiples matrices). Un hilo ejecuta Array(1,2).fold(0)(_ + _) , computando 0 + 1 + 2 . El otro hilo ejecuta Array(3,4).fold(0)(_ + _) , computando 0 + 3 + 4 . Finalmente, las sumas parciales de los dos hilos se suman. Tenga en cuenta que el elemento neutro, 0 , aparece dos veces.

Answer 5

Tal como lo define Scala, foldLeft es una operación lineal, mientras que fold es una operación en árbol. Por ejemplo:

List(1,2,3,4,5).foldLeft(0)(_ + _)
// This is the only valid order of operations
0+1 = 1
1+2 = 3
3+3 = 6
6+4 = 10
10 + 5 = 15
15 // done
List(1,2,3,4,5).fold(0)(_ + _)
// This is valid
0+1 = 1 0+3 = 3 0+5 = 5
1+2 = 3 3+4 = 7 5
3 + 7=10 5
10 + 5 = 15
15 // done

Para permitir descomposiciones de árbol arbitrarias de una lista secuencial, debe tener un cero que no hace nada (para poder agregarlo donde lo necesite en el árbol) y debe crear el mismo tipo de cosas que toma como sus argumentos binarios para que los tipos no cambien en usted según cómo descomponga el árbol.

(Ser capaz de evaluar como un árbol es bueno para la paralelización. Si desea poder transformar su tiempo de salida sobre la marcha, necesita un operador de combinación y un valor de inicio estándar-transforma-secuencia-elemento-a-deseado -type funciona igual que foldLeft tiene. Scala tiene esto y lo llama aggregate , pero de alguna manera esto es más parecido a foldLeft que fold es).

Answer 6

El error. Obtiene un error en tiempo de compilación porque la firma del fold solo permite doblar valores del tipo que es el supertipo del tipo de los valores en la colección, y el único supertipo de String (su tipo de colección) e Int (el tipo de su elemento cero proporcionado) es Any . Por lo tanto, se deduce que el tipo del resultado de fold es Any , y Any no tiene un método toInt .

Tenga en cuenta que las dos versiones de fold tienen diferentes firmas:

fold[A1 >: A](z: A1)(op: (A1, A1) => A1): A1
foldLeft[B](z: B)(f: (B, A) => B): B

¿Por qué tienen diferentes firmas? Esto es porque fold podría implementarse en paralelo, como es el caso con colecciones paralelas. Cuando múltiples procesadores se doblan sobre los valores en las colecciones, cada uno de los procesadores toma un subconjunto de elementos de tipo A y produce el valor doblado de tipo A1 , aplicando op . Los resultados producidos por esos procesadores se deben combinar en un valor final de plegado, esto se hace usando la función op , que hace exactamente eso.

Ahora, tenga en cuenta que esto no se puede hacer utilizando f en foldLeft , ya que cada uno de los procesadores produce un valor plegado de tipo B Varios valores de tipo B no pueden combinarse usando f , porque f solo combina el valor B con otro valor de tipo A ; no hay correspondencia entre los tipos A y B

Ejemplo. En su ejemplo, suponga que el 1er procesador toma los elementos "1", "2" y el segundo toma el elemento "3" . El primero producirá el valor doblado 3 , y el segundo producirá otro valor doblado 3 . Ahora tienen que combinar sus resultados para obtener el valor final doblado; esto es imposible, porque el cierre _ + _.toInt solo sabe cómo combinar un Int y String , y no 2 valores Int .

Para situaciones donde estos tipos difieren, use aggregate , en el que debe definir cómo combinar dos valores de tipo B :

def aggregate[B](z: B)(seqop: (B, A) => B, combop: (B, B) => B): B

El combop anterior define cómo hacer el paso final cuando el resultado del doblez y los elementos en la colección tienen diferentes tipos.

El elemento neutro Como se describió anteriormente, múltiples procesadores pueden doblar sobre subconjuntos de elementos en la colección. Cada uno de ellos comenzará su valor plegado al agregar el elemento neutral.

En el siguiente ejemplo:

List(1, 2, 3).foldLeft(4)(_ + _)

siempre devuelve 10 = 4 + 1 + 2 + 3 .

Sin embargo, 4 no debe usarse con fold , ya que no es un elemento neutral:

List(1, 2, 3).fold(4)(_ + _)

Lo anterior puede regresar (4 + 1 + 2) + (4 + 3) = 14 o (4 + 1) + (4 + 2) + (4 + 3) = 18 . Si no usas el elemento neutral para el fold , los resultados no son deterministas. De la misma manera, puede usar el Nil como elemento neutral, pero no como una lista no vacía.