Tại sao init là một phần chức năng?

Question

theo Haskell 2010 report, init được định nghĩa như sau:

init    :: [a] -> [a] 
init [x]   = [] 
init (x:xs)  = x : init xs 
init []   = error "Prelude.init: empty list" 

base-4.4.1.0 định nghĩa nó tương tự. Đối với tôi, có vẻ như nó hoàn toàn có thể chấp nhận và trực quan để có:

init [] = [] 

có thể làm cho init tổng chức năng. Kể từ khi định nghĩa này được đưa vào báo cáo haskell 2010, tôi đoán rằng có những đối số cho nó. Đó có phải là trường hợp hay nó được định nghĩa theo cách đó vì truyền thống và khả năng tương thích ngược?

Answer 1

Lý do tương tự tail [] không phải là []; nó phá vỡ các bất biến mà xác định các chức năng này. Chúng tôi có thể xác định head và tail bằng cách nói rằng nếu head và tail được xác định cho một giá trị xs, thì xs ≡ head xs : tail xs.

Như Niklas đã chỉ ra, bất biến chúng tôi muốn xác định init và last là xs ≡ init xs ++ [last xs]. Đúng là last cũng không được xác định trên danh sách trống, nhưng tại sao nên last được xác định nếu init không thể? Cũng giống như sai nếu một trong số head hoặc tail được xác định trên đầu vào trong khi số khác không được, init và last là hai mặt của cùng một đồng tiền, chia danh sách thành hai giá trị tương đương với giá trị ban đầu.

Đối với một cái nhìn "thực tế" hơn (mặc dù có khả năng suy luận về các chương trình về bất biến hữu ích về các hoạt động mà họ sử dụng có rất lợi ích thiết thực!), Một thuật toán có sử dụng init có thể sẽ không cư xử một cách chính xác trên một danh sách trống và nếu init hoạt động theo cách đó, nó sẽ hoạt động để ẩn các lỗi được tạo. Tốt hơn là nên bảo đảm an toàn cho các đầu vào của nó để xem xét các trường hợp cạnh như danh sách trống khi được sử dụng, đặc biệt là khi không rõ ràng giá trị được đề xuất để trả lại trong các trường hợp đó là hợp lý.

Dưới đây là một previous Stack Overflow question về head và tail, bao gồm cả lý do tại sao tail [] không chỉ trở []; các câu trả lời sẽ giúp giải thích tại sao những bất biến này lại quan trọng đến thế.

Answer 2

Thật là khủng khiếp khi có init [] = [], đặc biệt là nó sẽ phá vỡ các bất biến quan trọng như xs == init xs ++ [last xs] và length xs == 1 + length (init xs) và do đó ẩn lỗi.

Answer 3

Bởi vì tôi tìm thấy những câu hỏi thú vị, tôi quyết định viết ra những suy nghĩ của tôi về đề tài này:

logic

Giả sử chúng ta định nghĩa init xs là "danh sách, rằng, nếu bạn đặt last xs trên nó cuối cùng, tương đương với xs.Điều này tương đương với: init xs là danh sách không có phần tử cuối cùng của nó.Đối với xs == [], không tồn tại thành phần cuối cùng, do đó, init [] phải không xác định.

Bạn có thể thêm một trường hợp đặc biệt cho điều này, như trong "nếu xs là danh sách rỗng, sau đó init xs là danh sách rỗng, nếu không init xs là danh sách, rằng, nếu bạn đặt last xs về kết thúc của nó, là bình đẳng đến xs ". Chú ý cách này tiết kiệm hơn và ít sạch hơn. Chúng tôi giới thiệu thêm sự phức tạp, nhưng những gì cho?

Intuitive

init [1,2,3,4] == [1,2,3] 
init [1,2,3] == [1,2] 
init [1,2]  == [1] 
init [1]  == [] 
init []  == ?? 

Lưu ý cách chiều dài của danh sách ở phía bên tay phải của các phương trình giảm cùng với chiều dài của phía bên trái. Với tôi, loạt bài này không thể được tiếp tục một cách hợp lý, bởi vì danh sách ở phía bên phải sẽ phải có một kích thước tiêu cực!

thực

Như những người khác đã chỉ ra, việc xác định một trường hợp đặc biệt xử lý cho init hoặc tail để xem danh sách rỗng như một cuộc tranh cãi, có thể giới thiệu khó chỗ sai sót trong những tình huống mà các chức năng có thể không có hợp lý kết quả cho danh sách trống, nhưng vẫn không tạo ra ngoại lệ cho nó!

Hơn nữa, tôi có thể nghĩ không có thuật toán nào thực sự là lợi thế khi có init [] đánh giá là [], vậy tại sao lại giới thiệu độ phức tạp thêm? Lập trình là tất cả về sự đơn giản và đặc biệt là Haskell là tất cả về sự tinh khiết, bạn sẽ không đồng ý?

Answer 4

Vấn đề thực sự ở đây là init, như được định nghĩa, không thể hoạt động; đó là chức năng một phần vốn có, giống như head và tail. Tôi không vui mừng về việc có bao nhiêu chức năng cố tình một phần tồn tại trong các thư viện chuẩn, nhưng đó là một vấn đề khác.

Kể từ init như được đưa ra không thể được vớt, chúng tôi có hai lựa chọn:

• Hãy giải thích rằng đó là một bộ lọc trên danh sách đưa ra, giữ tất cả các yếu tố mà không phải là yếu tố cuối cùng, và từ bỏ bất biến đối với length và last. Điều này có thể được viết là reverse . drop 1 . reverse, điều này gợi ý khái quát hóa rõ ràng. Chúng tôi cũng có thể giới thiệu một đối tác tương tự cho take nếu muốn.

• Nhận ra rằng init xác định một phần chức năng và cung cấp cho đúng loại, [a] -> Maybe [a]. Lỗi sau đó có thể được thay thế chính xác bằng Nothing.

Answer 5

Đó là truyền thống. Vào thời điểm đó, họ đã lựa chọn tùy ý, và bây giờ mọi người quen với nó.

Họ đã thực hiện init tương tự như last, để cả hai đều không thành công trên danh sách trống. (tail và head là một cặp khác như thế.)

Nhưng họ có thể đã chọn điều ngược lại, như bạn đề xuất. Prelude có thể dễ dàng chứa hàm tail' = drop 1, cũng như hàm init' phù hợp, cho phép danh sách trống.Tôi không nghĩ rằng đây sẽ là vấn đề - tôi không thuyết phục bởi tất cả các cuộc nói chuyện về bất biến và định lý tự do. Nó chỉ có nghĩa là init' là một chút không giống với bạn đồng hành của nó last; đó là tất cả.

(last và head là một câu chuyện khác: chữ ký của họ là [a] -> a, vì vậy họ phải trả lại một phần tử, và họ không thể đưa ra một ra khỏi không khí mỏng Ngược lại, các loại init và tail là tất nhiên [a] -> [a]. , có nghĩa là họ có thể và thực hiện các danh sách trống.)