Qual è la relazione tra fold su Option, o etc e fold su Traversable?

Question

Scalaz fornisce un metodo denominato fold per vari ADT come Boolean, Option[_], Validation[_, _], Either[_, _] ecc. Questo metodo utilizza fondamentalmente le funzioni corrispondenti a tutti i casi possibili per quello determinato ADT. In altre parole, una partita modello mostrato sotto:

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

è equivalente a:

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

Alcuni esempi:

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 

Allo stesso tempo, c'è un'operazione con la stessa nome per i tipi Traversable[_], che attraversa la raccolta eseguendo determinate operazioni sui suoi elementi e accumulando il valore del risultato. Ad esempio,

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 

Perché questi due operazioni identificato con lo stesso nome - fold/catamorphism? Non riesco a vedere alcuna somiglianza/relazione tra i due. Cosa mi manca?

Answer 1

Penso che il problema che si sta verificando è che si vedono queste cose in base alla loro implementazione, non ai loro tipi. Considerate questo semplice rappresentazione di tipi:

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

Option[A] = None 
      | Some el: A 

Ora, consideriamo Option 's si piegano:

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

Così, Option, riduce ogni possibile caso di un certo valore in B, e restituire quello. Ora, vediamo la stessa cosa per List:

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

Si noti, tuttavia, che abbiamo una chiamata ricorsiva lì, sul List[A]. Dobbiamo piegare che in qualche modo, ma sappiamo fold[B] su un List[A] restituirà sempre B, in modo che possiamo riscrivere così:

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

In altre parole, abbiamo sostituito List[A] da B, perché piegandolo tornerà sempre a B, data la firma del tipo di fold. Ora, vediamo (caso d'uso) di Scala tipo di firma per foldRight:

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

Dire, fa che si ricorda qualcosa?

Answer 2

Se si pensa di "piegare" come "condensare tutti i valori in un contenitore tramite un'operazione, con un valore di inizializzazione" e si pensa a un'opzione come a un contenitore che può avere al massimo un valore, questo inizia a dare un senso.

Infatti, foldLeft ha la stessa firma e ti dà esattamente gli stessi risultati se lo si utilizza su una lista vuota vs Nessuno, e su una lista con un solo elemento vs Alcuni:

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 è definito anche su entrambi List e Option nella libreria standard di Scala, con la stessa firma (credo che entrambi ereditino da un tratto, in effetti). E ancora, si ottiene gli stessi risultati in un elenco Singleton come su alcuni:

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

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

io non sono al 100% sicuro circa la fold da Scalaz su Option/Either/etc, si alza un buon punto lì. Sembra avere una firma e un funzionamento abbastanza diversi dal "pieghevole" a cui sono abituato.