Tại sao nếp gấp được xác định theo cách lạ trong vợt?

Question

Trong Haskell, giống như trong nhiều ngôn ngữ chức năng khác, hàm foldl được định nghĩa sao cho, ví dụ: foldl (-) 0 [1,2,3,4] = -10.

Điều này là ổn, bởi vì foldl (-) 0 [1, 2,3,4], theo định nghĩa, ((((0 - 1) - 2) - 3) - 4).

Nhưng, trong Racket, (foldl - 0 '(1 2 3 4)) là 2, vì vợt "thông minh" tính toán như thế này: (4 - (3 - (2 - (1 - 0)))), mà thực sự là 2.

Tất nhiên, nếu chúng ta định nghĩa phụ trợ chức năng lật, như thế này:

(define (flip bin-fn) 
    (lambda (x y) 
    (bin-fn y x))) 

sau đó chúng ta có thể trong vợt đạt được các hành vi tương tự như trong Haskell: thay vì (foldl - 0 '(1 2 3 4)) chúng ta có thể viết: (foldl (flip -) 0 '(1 2 3 4))

câu hỏi đặt ra là: tại sao foldl trong vợt được định nghĩa theo cách kỳ quặc (phi tiêu chuẩn và không trực quan), khác với bất kỳ ngôn ngữ nào khác?

Answer 1

Từ vợt documentation, mô tả của foldl:

(foldl proc init lst ...+) → any/c 

Hai điểm đáng chú ý cho câu hỏi của bạn được đề cập:

các lsts đầu vào nằm ngang từ trái sang phải

Và

foldl xử lý lsts trong không gian liên tục

Tôi sẽ suy đoán về cách thực hiện cho rằng có thể trông như thế nào, với một danh sách duy nhất để đơn giản:

(define (my-foldl proc init lst) 
    (define (iter lst acc) 
    (if (null? lst) 
     acc 
     (iter (cdr lst) (proc (car lst) acc)))) 
    (iter lst init)) 

Như bạn có thể nhìn thấy , các yêu cầu về truyền tải từ trái sang phải và không gian liên tục được đáp ứng (chú ý đến đệ quy đuôi trong iter), nhưng yêu cầu đối số cho proc chưa bao giờ được chỉ định trong mô tả. Do đó, kết quả của cách gọi mã trên sẽ là:

(my-foldl - 0 '(1 2 3 4)) 
> 2 

Nếu chúng ta đã xác định thứ tự của các đối số cho proc theo cách này:

(proc acc (car lst)) 

Sau đó, kết quả sẽ là:

(my-foldl - 0 '(1 2 3 4)) 
> -10 

Quan điểm của tôi là, tài liệu dành cho foldl không đưa ra bất kỳ giả định nào về thứ tự đánh giá của các đối số cho proc, chỉ h để đảm bảo rằng không gian cố định được sử dụng và các phần tử trong danh sách được đánh giá từ trái sang phải.

Là một mặt lưu ý, bạn có thể nhận được để đánh giá mong muốn cho biểu hiện của bạn bằng cách đơn giản viết này:

(- 0 1 2 3 4) 
> -10 

Answer 2

vợt của foldl và foldr (và cũng SRFI-1'sfold và fold-right) có tài sản mà

(foldr cons null lst) = lst 
(foldl cons null lst) = (reverse lst) 

Tôi suy đoán thứ tự đối số đã được chọn vì lý do đó.

Answer 3

• Định nghĩa Haskell là không thống nhất. Trong vợt, chức năng cho cả hai nếp gấp có cùng thứ tự các đầu vào, và do đó bạn chỉ có thể thay thế foldl bằng foldr và nhận được kết quả tương tự. Nếu bạn làm điều đó với phiên bản Haskell bạn sẽ nhận được một kết quả khác (thường là) - và bạn có thể thấy điều này trong các loại khác nhau của hai.

  (Trong thực tế, tôi nghĩ rằng để làm một so sánh thích hợp, bạn nên tránh những đồ chơi ví dụ số nơi cả hai biến kiểu là số nguyên.)

• này có sản phẩm phụ đẹp nơi bạn đang khuyến khích để chọn foldl hoặc foldr theo sự khác biệt ngữ nghĩa của chúng. Tôi đoán là với thứ tự của Haskell bạn có thể chọn theo các hoạt động. Bạn có một ví dụ tốt cho điều này: bạn đã sử dụng foldl vì bạn muốn trừ từng số - và đó là một lựa chọn "hiển nhiên" dễ dàng bỏ qua thực tế là foldl thường là một lựa chọn tồi trong ngôn ngữ lười biếng.

• Một khác biệt nữa là phiên bản Haskell bị hạn chế hơn phiên bản Racket theo cách thông thường: nó hoạt động trên chính xác một danh sách đầu vào, trong khi Racket có thể chấp nhận bất kỳ số danh sách nào. Điều này làm cho nó quan trọng hơn để có một thứ tự đối số thống nhất cho hàm đầu vào). Cuối cùng, giả sử Racket phân biệt từ "nhiều ngôn ngữ chức năng khác", vì gấp nằm ngoài một thủ thuật mới, và Racket có nguồn gốc lớn hơn Haskell (hoặc các ngôn ngữ khác). Câu hỏi do đó có thể đi theo cách khác: tại sao Haskell là foldl được xác định theo cách lạ? (Và không, (-) không phải là một lý do tốt.)

lịch sử cập nhật:

Từ này có vẻ làm phiền mọi người một lần nữa và một lần nữa, tôi đã làm một chút legwork. Đây không phải là dứt khoát trong bất kỳ cách nào, chỉ cần đoán thứ hai của tôi. Vui lòng chỉnh sửa điều này nếu bạn biết nhiều hơn hoặc thậm chí tốt hơn, gửi email cho những người có liên quan và hỏi. Cụ thể, tôi không biết ngày mà các quyết định này được đưa ra, vì vậy danh sách sau đây theo thứ tự thô.

• Đầu tiên là Lisp và không đề cập đến "gấp" bất kỳ loại nào. Thay vào đó, Lisp có reduce rất không đồng nhất, đặc biệt nếu bạn xem xét loại của nó. Ví dụ: :from-end là đối số từ khóa xác định xem đó là quét trái hay phải và, nó sử dụng các chức năng tích lũy khác nhau có nghĩa là loại bộ tích lũy phụ thuộc vào từ khóa đó.Điều này là ngoài các hack khác: thường là giá trị đầu tiên được lấy từ danh sách (trừ khi bạn chỉ định một :initial-value). Cuối cùng, nếu bạn không chỉ định một :initial-value và danh sách trống, nó sẽ thực sự áp dụng hàm trên đối số 0 để có kết quả.

  Tất cả điều này có nghĩa là reduce thường được sử dụng cho những gì tên của nó gợi ý: giảm danh sách giá trị thành một giá trị duy nhất, trong đó hai loại thường giống nhau. Kết luận ở đây là nó phục vụ một loại mục đích tương tự để gấp, nhưng nó không gần như hữu ích như cấu trúc lặp lại danh sách chung mà bạn nhận được với gấp. Tôi đoán rằng điều này có nghĩa rằng không có mối quan hệ mạnh mẽ giữa reduce và các hoạt động lần sau.

• Ngôn ngữ có liên quan đầu tiên theo sau Lisp và có nếp gấp phù hợp là ML. Sự lựa chọn đã được thực hiện ở đó, như đã nêu trong câu trả lời của newacct dưới đây, là để đi với uniform types version (tức là, những gì Racket sử dụng).

• Tham chiếu tiếp theo là Bird & Wadler's ItFP (1988), sử dụng different types (như trong Haskell). Tuy nhiên, họ note in the appendix rằng Miranda có cùng loại (như trong Vợt).

• Miranda sau trên switched the argument order (ví dụ: được chuyển từ lệnh Racket sang lệnh Haskell). Cụ thể, văn bản đó cho biết:

  CẢNH BÁO - định nghĩa này của nếp gấp khác với các phiên bản cũ hơn của Miranda. Cái ở đây cũng giống như ở Bird và Wadler (1988). Định nghĩa cũ đã có hai args của `op 'đảo ngược.

• Haskell đã lấy rất nhiều thứ từ Miranda, bao gồm các loại khác nhau. (Nhưng tất nhiên tôi không biết ngày tháng nên có lẽ sự thay đổi của Miranda là do Haskell.) Trong mọi trường hợp, rõ ràng vào thời điểm này là không có sự đồng thuận, do đó câu hỏi đảo ngược ở trên nắm giữ.

• OCaml đi với sự chỉ đạo Haskell và sử dụng different types

• Tôi đoán rằng "Làm thế nào để thiết kế Programs" (aka HtDP) được viết vào khoảng thời gian này, và họ đã chọn same type. Tuy nhiên, không có động lực hoặc giải thích - và thực tế, sau bài tập đó, nó đơn giản được đề cập là one of the built-in functions.

  Thực hiện vợt của fold operations là, tất nhiên, "tích hợp" được đề cập ở đây.

• Sau đó, đến SRFI-1 và lựa chọn là sử dụng phiên bản cùng loại (như Racket). Đây quyết định was question bởi John David Stone, người chỉ vào một bình luận trong SRFI nói rằng

  Lưu ý: MIT Đề án và Haskell lật trật tự arg F cho họ reduce và fold chức năng.

  Olin sau addressed this: tất cả các ông nói là:

  Điểm tốt, nhưng tôi muốn thống nhất giữa hai chức năng. nhà nước có giá trị đầu tiên: srfi-1, SML nhà nước có giá trị cuối cùng: Haskell

  Lưu ý đặc biệt sử dụng của mình nhà nước có giá trị, điều này cho thấy một cái nhìn, nơi các loại phù hợp là một điểm có thể quan trọng hơn thứ tự nhà điều hành.

Answer 4

"khác so với trong bất kỳ ngôn ngữ khác"

Như một phản ví dụ, Standard ML (ML là một ngôn ngữ chức năng rất cũ và ảnh hưởng) 's foldl cũng làm việc theo cách này: http://www.standardml.org/Basis/list.html#SIG:LIST.foldl:VAL