Vui lòng giải thích bằng tiếng Anh đơn giản nhất, không có biệt ngữ nhất có thể, "tài sản phổ quát của nếp gấp"?

Question

Tôi đang làm việc thông qua "Real World Haskell", dẫn đến một tệp PDF miễn phí có tên là "A tutorial on the universality and expressiveness of fold". Nó làm cho điểm mà một "nếp gấp" là "phổ quát". Tôi đang đấu vật với định nghĩa "phổ quát" của mình, và muốn nghe từ những người đã đầu tư thời gian để tiêu hóa nó: Hãy giải thích bằng tiếng Anh đơn giản, khó hiểu nhất, "tài sản phổ quát của nếp gấp"? "Thuộc tính phổ quát" này là gì và tại sao lại quan trọng?

Cảm ơn.

Answer 1

(Chế độ biệt ngữ tắt :-)

Thuộc tính chung chỉ là cách chứng minh hai biểu thức bằng nhau. (Đó là những gì có nghĩa là các thuật ngữ "chứng minh nguyên tắc".) Thuộc tính phổ quát nói rằng nếu bạn có thể chứng minh hai phương trình này

g []  = v 
g (x:xs) = f x (g xs) 

sau đó bạn có thể kết luận phương trình thêm

g = fold f v 

Trò chuyện cũng đúng, nhưng đó là tầm thường để chỉ hiển thị bằng cách mở rộng định nghĩa của fold. Các tài sản phổ quát là một tài sản sâu hơn nhiều (đó là một cách biệt ngữ nói rằng nó ít rõ ràng lý do tại sao nó là sự thật.)

Lý do nó là thú vị để làm điều này ở tất cả là nó cho phép bạn tránh bằng chứng bằng cảm ứng, đó là hầu như luôn luôn đáng để tránh.

Answer 2

giấy xác định hai thuộc tính:

g []  = v 
g (x : xs) = f x (g xs) 

và sau đó nói rằng fold không chỉ một hàm thỏa mãn các thuộc tính, nhưng là chỉ chức năng thỏa mãn những tài sản. rằng nó là duy nhất trong vấn đề đó là những gì làm cho nó 'phổ quát' theo nghĩa mà bài báo đang sử dụng.

Answer 3

Thuộc tính gấp có nghĩa là nó là một hàm đệ quy danh sách, tương đương với tất cả các hàm đệ quy danh sách khác, miễn là bạn cung cấp cho nó các tham số đúng.

Thuộc tính này có thuộc tính này bởi vì nó chấp nhận làm tham số, các chức năng sẽ được áp dụng cho các mục trong danh sách.

Ví dụ, nếu chúng ta viết một hàm sum đơn giản:

sum []   = 0 
sum (head:tail) = head + (sum tail) 

sau đó chúng tôi thực sự có thể viết nó như là một chức năng lần thay vào đó, bằng cách thông qua trong (+) điều hành mà chúng tôi muốn sử dụng để kết hợp các mặt hàng:

sum list = foldl (+) 0 list 

Vì vậy, bất kỳ chức năng nào hoạt động đơn giản và đệ quy trên danh sách đều có thể được viết lại dưới dạng hàm gấp. Tương đương đó là tài sản mà nó nắm giữ. Tôi tin rằng anh ta gọi đặc tính phổ quát, bởi vì nó hoạt động trên tất cả các thuật toán danh sách tuyến tính đệ quy này, mà không có ngoại lệ. Và như ông giải thích, lý do tài sản này rất hữu ích, là bởi vì chúng tôi có thể hiển thị tất cả các thuật toán khác thực sự tương đương với gấp, bằng cách chứng minh điều gì đó về nếp gấp, chúng tôi cũng chứng minh nó cho tất cả các thuật toán khác.

cá nhân tôi thấy các chức năng lần khó hiểu, vì vậy đôi khi tôi đã sử dụng của riêng tôi mà trông như thế này:

-- forall - A kind of for next loop 
-- list is list of things to loop through 
-- f is function to perform on each thing 
-- c is the function which combines the results of f 
-- e is the thing to combine to when the end of the list is reached 
forall :: [a] -> (a->b) -> (b->b->b) -> b -> b 
forall [] f c e = e 
forall (x:xs) f c e = c (f x) (forall xs f c e) 

(Đây thực sự là một chút mạnh mẽ hơn foldl vì nó có tính năng bổ sung của việc áp dụng chức năng f cho từng mục trong danh sách.)

Không ai chứng minh được gì về chức năng của tôi. Nhưng điều đó không quan trọng, bởi vì tôi có thể chỉ ra rằng chức năng của tôi thực sự là một hàm gấp:

forall l f c e = foldl c e (map fn l) 

Và vì thế tất cả những thứ đã được chứng minh về nếp gấp, cũng được chứng minh là đúng cho chức năng của tôi, và tất cả các công dụng của nó trong suốt chương trình của tôi. (Lưu ý chúng tôi thậm chí không cần xem xét loại chức năng c nào được cung cấp trong mỗi cuộc gọi khác nhau đến forall và foldl, không quan trọng!)

Answer 4

Tôi vừa tìm thấy mục nhập mới (đối với tôi) trên Wikipedia, " Universal Property ". Nó làm sáng tỏ một TÔN của ánh sáng về câu hỏi này. Here's the link: Từ đó, tôi (tenatively) kết luận như sau:

1. Mặc dù bạn có thể nghĩ đến 100 cách khác nhau để đi bộ qua một danh sách, tính toán trên đường đi, và sản xuất một giá trị cuối cùng trong danh sách, tất cả 100 những cách đó là isomorphic (có nghĩa là cuối cùng, chúng giống nhau). Thực sự chỉ có một cách để giảm một danh sách thành một giá trị, và đó là FOLD.
2. Fold cũng là "giải pháp hiệu quả nhất" để giảm danh sách thành một giá trị duy nhất. Hoặc bạn có thể nói, giải pháp "yếu tố" hoặc "đơn giản nhất" nhất.

Cùng với nhau, có vẻ như, 2 điểm đó nắm bắt được ý nghĩa của thuật ngữ "tài sản chung".

Answer 5

Mặc dù có thể hơi khó theo dõi mà không đọc các bài viết trước trong chuỗi giải thích các thuộc tính phổ quát từ quan điểm phân loại, bài này đưa ra giải thích chi tiết về thuộc tính chung của nếp gấp, cũng như bản đồ và bộ lọc.

http://jeremykun.com/2013/09/30/the-universal-properties-of-map-fold-and-filter/

Mặc dù tôi vẫn chưa viết nó, followup sẽ khái quát này (và làm cho nó đơn giản hơn nhiều để hiểu, mặc dù trừu tượng hơn) để "gấp giống như" hoạt động trên cấu trúc dữ liệu chung.

Xem bài này để biết thêm về những gì thuộc tính phổ quát là: http://jeremykun.com/2013/05/24/universal-properties/

Và vào đây để liên kết đến tất cả các bài viết trong loạt bài này: http://jeremykun.com/main-content/

Thật ra, câu trả lời chấp nhận hiện nay là cách dễ nhất để hiểu những gì thuộc tính phổ quát nói về nếp gấp. Các bài báo được liên kết ở trên chỉ đơn giản là đưa ra một mô tả kỹ thuật chi tiết hơn thông qua lý thuyết danh mục không có trong bài báo được đề cập đến. Tuy nhiên, tôi không đồng ý với tuyên bố trong câu trả lời được chấp nhận, rằng tài sản phổ quát là một tài sản sâu hơn nhiều so với tuyên bố không có biệt ngữ. Thuộc tính phổ quát của nếp gấp là chính xác cùng một tuyên bố, chỉ đóng hộp thành ngôn ngữ của các đối tượng ban đầu và cuối cùng theo bản chất phân tích mọi thứ với lý thuyết thể loại. Phân tích này có giá trị chính xác vì sự tổng quát tự nhiên của nó.