¿Cuál es la relación entre la opción de doblar, o bien, etc. y doblar en Traversable?

Question

Scalaz proporciona un método denominado fold para diversos ADTs tales como Boolean, Option[_], Validation[_, _], Either[_, _] etc. Este método toma básicamente funciones correspondientes a todos los casos posibles para que, dada ADT. En otras palabras, una coincidencia de patrón muestra a continuación:

x match { 
    case Case1(a, b, c) => f(a, b, c) 
    case Case2(a, b) => g(a, b) 
    . 
    . 
    case CaseN => z 
} 

es equivalente a:

x.fold(f, g, ..., z) 

Algunos ejemplos:

scala> (9 == 8).fold("foo", "bar") 
res0: java.lang.String = bar 

scala> 5.some.fold(2 *, 2) 
res1: Int = 10 

scala> 5.left[String].fold(2 +, "[" +) 
res2: Any = 7 

scala> 5.fail[String].fold(2 +, "[" +) 
res6: Any = 7 

Al mismo tiempo, hay una operación con la misma nombre para los tipos Traversable[_], que atraviesa la colección realizando cierta operación en sus elementos, y acumulando el valor del resultado. Por ejemplo,

scala> List(2, 90, 11).foldLeft("Contents: ")(_ + _.toString + " ") 
res9: java.lang.String = "Contents: 2 90 11 " 

scala> List(2, 90, 11).fold(0)(_ + _) 
res10: Int = 103 

scala> List(2, 90, 11).fold(1)(_ * _) 
res11: Int = 1980 

¿Por qué estas dos operaciones identificadas con el mismo nombre - fold/catamorphism? No veo ninguna similitud/relación entre los dos. ¿Qué me estoy perdiendo?

Answer 1

Creo que el problema que está teniendo es que ve estas cosas en función de su implementación, no de sus tipos. Considere esta simple representación de tipos:

List[A] = Nil 
     | Cons head: A tail: List[A] 

Option[A] = None 
      | Some el: A 

Ahora, vamos a considerar Option 's se pliegan:

fold[B] = (noneCase: => B, someCase: A => B) => B 

Así, en Option, reduce todos los casos posibles de algún valor en B, y devolver eso. Ahora, vamos a ver lo mismo para List:

fold[B] = (nilCase: => B, consCase: (A, List[A]) => B) => B 

Nótese, sin embargo, que tenemos una llamada recursiva allí, en List[A]. Tenemos a veces que de alguna manera, pero sabemos fold[B] en un List[A] siempre devolverá B, por lo que se puede reescribir así:

fold[B] = (nilCase: => B, consCase: (A, B) => B) => B 

En otras palabras, reemplazado List[A] por B, porque doblándola siempre devolverá a B, dada la firma de tipo fold. Ahora, vamos a ver de (caso de uso) Scala tipo de firma para foldRight:

foldRight[B](z: B)(f: (A, B) ⇒ B): B 

Di, qué te recuerda a algo?

Answer 2

Si piensa en "plegar" como "condensando todos los valores en un contenedor mediante una operación, con un valor inicial", y piensa en una Opción como un contenedor que puede tener como máximo un valor, entonces este comienza a tener sentido.

De hecho, foldLeft tiene la misma firma y le da exactamente los mismos resultados si se utiliza en una lista vacía contra ninguno, y en una lista con un solo elemento vs Algunos:

scala> val opt : Option[Int] = Some(10) 
opt: Option[Int] = Some(10) 

scala> val lst : List[Int] = List(10) 
lst: List[Int] = List(10) 

scala> opt.foldLeft(1)((a, b) => a + b) 
res11: Int = 11 

scala> lst.foldLeft(1)((a, b) => a + b) 
res12: Int = 11 

fold es también se define en List y Option en la biblioteca estándar de Scala, con la misma firma (creo que ambos lo heredan de un rasgo, de hecho). Y de nuevo, se obtienen los mismos resultados en una lista unitaria como en algunos:

scala> opt.fold(1)((a, b) => a * b) 
res25: Int = 10 

scala> lst.fold(1)((a, b) => a * b) 
res26: Int = 10 

no estoy 100% seguro de la fold de Scalaz en Option/Either/etc, que plantean un buen punto allí. Parece tener una firma y una operación bastante diferentes del "plegado" al que estoy acostumbrado.