Tại sao gấp trái mong đợi (a -> b -> a) thay vì (b -> a -> a)?

Question

Tôi tự hỏi tại sao hàm được mong đợi bằng dấu ngoặc kép lại có chữ ký loại a -> b -> a thay vì b -> a -> a. Có quyết định thiết kế nào đằng sau điều này không?

Trong Haskell, ví dụ, tôi phải viết foldl (\xs x -> x:xs) [] xs để đảo ngược danh sách thay vì ngắn hơn foldl (:) [] xs (có thể với b -> a -> a). Mặt khác, có những trường hợp sử dụng yêu cầu tiêu chuẩn a -> b -> a. Trong Scala, điều này có thể được thêm vào: xs.foldLeft(List.empty[Int]) ((xs, x) => xs:+x) có thể được viết là xs.foldLeft(List.empty[Int]) (_:+_).

Các trường hợp sử dụng tương ứng xảy ra đòi hỏi chữ ký loại nhất định thay vì chữ ký thay thế, hoặc có quyết định nào khác dẫn đến thiết kế gấp trái trong Haskell và Scala (và có thể là nhiều ngôn ngữ khác)?

Answer 1

Về mặt lý thuyết mà nói, một lần đúng, nói foldr f z [1..4] thay thế một danh sách các hình thức sau đây

: 
/\ 
1 : 
/\ 
    2 : 
    /\ 
    3 : 
    /\ 
     4 [] 

với giá trị của một biểu thức có dạng sau

f 
/\ 
1 f 
/\ 
    2 f 
    /\ 
    3 f 
    /\ 
     4 z 

Nếu chúng ta để biểu diễn này biểu thức trên một dòng, tất cả các dấu ngoặc đơn sẽ liên kết với bên phải, do đó tên phải gấp: (1 `f` (2 `f` (3 `f` (4 `f` z)))). Một nếp gấp bên trái đôi theo nghĩa nào đó với một nếp gấp bên phải. Đặc biệt, chúng tôi muốn cho hình dạng của biểu đồ tương ứng cho một lần trái là một hình ảnh phản chiếu của đó cho một lần trái, như trong những điều sau đây:

 f 
    /\ 
     f 4 
    /\ 
    f 3 
/\ 
    f 2 
/\ 
z 1 

Nếu chúng ta viết ra sơ đồ này trên một dòng duy nhất, chúng ta sẽ nhận được một biểu thức mà tất cả các sư ngoặc sang bên trái, mà jibes tốt với tên của một lần trái:

((((z `f` 1) `f` 2) `f` 3) `f` 4) 

Nhưng chú ý rằng trong sơ đồ gương này, kết quả đệ quy của màn hình đầu tiên được cấp cho f làm đối số đầu tiên, trong khi mỗi phần tử của danh sách được cung cấp dưới dạng đối số thứ hai, tức là các đối số được cấp cho f theo thứ tự ngược so với các nếp gấp bên phải.

Answer 2

Vì bạn viết (a /: bs) cho foldLeft ở dạng ngắn; đây là một toán tử đẩy a thông qua tất cả các bs, do đó, nó là tự nhiên để viết hàm theo cùng một cách (ví dụ: (A,B) => A). Lưu ý rằng foldRight thực hiện theo thứ tự khác.

Answer 3

Chữ ký loại là foldl :: (a -> b -> a) -> a -> [b] -> a; nó là tự nhiên cho hàm kết hợp để có giá trị ban đầu ở bên trái, bởi vì đó là cách nó kết hợp với các phần tử của danh sách. Tương tự như vậy, bạn sẽ nhận thấy foldr có cách khác. Biến chứng trong định nghĩa ngược lại của bạn là bởi vì bạn đang sử dụng một biểu thức lambda nơi flip sẽ đẹp hơn: foldl (flip (:)) [] xs, cũng có sự tương đồng dễ chịu giữa các khái niệm lật và ngược lại.

Answer 4

Giả sử bạn có này:

List(4, 2, 1).foldLeft(8)(_/_) 

Đó là giống như:

((8/4)/2)/1 

Xem cách các tham số đầu tiên luôn luôn là te ắc?Việc có các tham số trong thứ tự này làm cho cú pháp trình giữ chỗ (gạch dưới) một bản dịch trực tiếp thành biểu thức được mở rộng.