Каково соотношение сгибов на Option, Either и т. Д. И сгиб на Traversable?

Question

Скалаз предоставляет метод с именем fold для различных ADT, таких как Boolean, Option[_], Validation[_, _], Either[_, _] и т. д. Этот метод в основном принимает функции, соответствующие всем возможным случаям для данного ADT. Другими словами, образец соответствия показан ниже:

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

эквивалентно:

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

Некоторые примеры:

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

В то же время, есть операция с тем же именем для Traversable[_] типы, которые пересекают коллекцию, выполняя определенную операцию над ее элементами и накапливая значение результата. Например,

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

Почему эти две операции идентифицированы с одинаковым именем - fold/ Катаморфизм? Я не вижу каких-либо сходств / отношений между ними. Что мне не хватает?

Answer 1

Я думаю, что проблема у вас в том, что вы видите эти вещи на основе их реализации, а не их типов. Рассмотрим это простое представление типов:

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

Option[A] = None
          | Some el: A

Теперь давайте рассмотрим Optionфолд:

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

Скоро Option, он сводит каждый возможный случай к некоторому значению в Bи верни это. Теперь давайте посмотрим то же самое для List:

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

Обратите внимание, однако, что у нас есть рекурсивный вызов там, на List[A], Мы должны это как-то сложить, но мы знаем fold[B] на List[A] всегда вернется Bтак что мы можем переписать это так:

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

Другими словами, мы заменили List[A] от Bпотому что сворачивание всегда будет возвращать B, учитывая тип подписи fold, Теперь давайте рассмотрим сигнатуру типа Scala (вариант использования) для foldRight:

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

Скажите, это вам что-то напоминает?

Answer 2

Если вы думаете о "сворачивании" как о "сжатии всех значений в контейнере посредством операции с начальным значением", и вы думаете о Option как о контейнере, который может иметь не более одного значения, то это начинает иметь смысл,

По факту, foldLeft имеет одинаковую подпись и дает точно такие же результаты, если вы используете его в пустом списке против None и в списке, содержащем только один элемент против Some:

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 также определяется на обоих List а также Option в стандартной библиотеке Scala с одной и той же подписью (я полагаю, что они оба наследуют ее от черты, на самом деле). И снова, вы получаете те же результаты в списке синглтона, что и в некоторых:

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

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

Я не уверен на 100% fold из Скалаза на Option/Either/ etc, вы подняли хороший вопрос. Похоже, что подпись и операция совершенно иные, чем у "сворачивания", к которому я привык.