Mối quan hệ của nếp gấp trên Tùy chọn, v.v. và gấp trên Traversable là gì?

Question

Scalaz cung cấp một phương thức có tên fold cho các ADT khác nhau như Boolean, Option[_], Validation[_, _], Either[_, _] v.v. Phương pháp này về cơ bản có chức năng tương ứng với tất cả các trường hợp có thể cho ADT đã cho. Nói cách khác, một mô hình phù hợp hiển thị dưới đây:

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

tương đương với:

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

Một số ví dụ:

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 

Cùng lúc đó, có một hoạt động với cùng tên cho các loại Traversable[_], di chuyển qua bộ sưu tập thực hiện một số thao tác nhất định trên các phần tử của nó và tích lũy giá trị kết quả. Ví dụ,

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 

Tại sao hai hoạt động này xác định với cùng tên - fold/catamorphism? Tôi không thấy bất kỳ điểm tương đồng/quan hệ nào giữa hai người. Tôi đang thiếu gì?

Answer 1

Tôi nghĩ rằng vấn đề bạn đang gặp phải là bạn thấy những điều này dựa trên việc triển khai, chứ không phải kiểu của chúng. Xem xét trình bày đơn giản này các loại:

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

Option[A] = None 
      | Some el: A 

Bây giờ, chúng ta hãy xem xét Option 's gấp:

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

Vì vậy, trên Option, nó làm giảm mọi trường hợp có thể để một số giá trị trong B, và trở về đó. Bây giờ, chúng ta hãy xem điều tương tự cho List:

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

Lưu ý, tuy nhiên, chúng ta có một cuộc gọi đệ quy ở đó, trên List[A]. Chúng ta phải gấp rằng bằng cách nào đó, nhưng chúng ta biết fold[B] trên List[A] sẽ luôn luôn trả B, vì vậy chúng ta có thể viết lại nó như thế này:

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

Nói cách khác, chúng tôi thay thế List[A] bởi B, vì gấp nó sẽ luôn luôn trở lại a B, có chữ ký loại fold. Bây giờ, hãy xem chữ ký loại Scala's (use case) cho foldRight:

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

Nói, điều đó nhắc bạn về điều gì đó?

Answer 2

Nếu bạn nghĩ "gấp" là "cô đặc tất cả các giá trị trong vùng chứa thông qua thao tác, với giá trị hạt" và bạn nghĩ tùy chọn là vùng chứa có thể có nhiều nhất một giá trị, thì bắt đầu có ý nghĩa.

Trong thực tế, foldLeft có chữ ký giống nhau và mang đến cho bạn một cách chính xác kết quả tương tự nếu bạn sử dụng nó trên một danh sách trống vs None, và trên một danh sách với chỉ có một yếu tố vs Một số:

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 là cũng được định nghĩa trên cả hai số List và Option trong thư viện chuẩn Scala, có cùng chữ ký (tôi tin rằng cả hai đều thừa kế từ một đặc điểm, trên thực tế). Và một lần nữa, bạn sẽ có được kết quả tương tự trên một danh sách singleton như trên một số:

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

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

Tôi không chắc chắn về fold từ Scalaz 100% trên Option/Either/etc, bạn nâng cao một điểm tốt ở đó. Nó dường như có một chữ ký và hoạt động khá khác với "gấp" mà tôi từng sử dụng.