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

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

10 голосов
/ 17 декабря 2011

Scalaz предоставляет метод с именем 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 / катаморфизм? Я не вижу каких-либо сходств / отношений между ними. Чего мне не хватает?

Ответы [ 2 ]

7 голосов
/ 17 декабря 2011

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

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

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

5 голосов
/ 17 декабря 2011

Если вы думаете о «сворачивании» как о «сжатии всех значений в контейнере с помощью операции с начальным значением», и вы рассматриваете 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 от Scalaz на Option / Either / etc,Вы подняли хороший вопрос там.Кажется, что он имеет совершенно другую сигнатуру и операцию, чем "сворачивание", к которому я привык.

...