Haskell: foldr vs foldr1

Question

Nếu tôi có chức năng chèn này:

insert x []  = [x] 
insert x (h:t) 
    | x <= h  = x:(h:t) 
    | otherwise = h:(insert x t) 

này tạo ra một danh sách sắp xếp:

foldr insert [] [1,19,-2,7,43] 

nhưng điều này:

foldr1 insert [1,19,-2,7,43] 

sản xuất 'không thể xây dựng loại vô hạn: a0 = [a0] '

Tôi nhầm lẫn về lý do cuộc gọi thứ hai không thể hoạt động.

Tôi đã xem xét các định nghĩa cho cả hai foldr và foldr1 và đã truy tìm cả hai với các hàm số học đơn giản, nhưng tôi vẫn không thể đưa ra giải thích rõ ràng về lý do cuộc gọi thứ hai thất bại.

Answer 1

Vì foldr1 đang cố gắng để làm điều này:

insert 43 -7 

đó sẽ thất bại.

Answer 2

Loại foldr1 là (a -> a -> a) -> [a] -> a, tức là đối số và kết quả của hàm này có cùng loại. Tuy nhiên, insert có loại Ord a => a -> [a] -> [a]. Đối với foldr1 insert được nhập tốt, a và [a] phải cùng loại.

Nhưng điều này có nghĩa là a == [a] == [[a]] == [[[a]]] == ..., tức là, a là một loại vô số danh sách.

Answer 3

Hãy xem xét một số chữ ký loại.

foldr :: (a -> b -> b) -> b -> [a] -> b 
foldr1 :: (a -> a -> a) ->  [a] -> a 

Trong cả hai trường hợp, đối số đầu tiên là hàm của hai đối số.

• cho foldr1, hai đối số này phải có cùng loại (và kết quả có kiểu này cũng)
• cho foldr, hai đối số này có thể có các loại khác nhau (và kết quả có kiểu giống như thứ hai đối số)

Loại insert của bạn là gì?

Answer 4

Vấn đề là sau đây:

foldr sẽ làm theo cách này:

1. kết quả thiết lập để insert 43 []
2. kết quả thiết lập để insert 7 result
3. và vân vân

Đây rõ ràng công trinh.

Trong khi foldr1 sẽ cố gắng làm như sau:

1. kết quả thiết lập để insert 7 43
2. kết quả thiết lập để insert -2 result
3. , vv

mà chắc chắn là sai. Bạn có thể thấy, foldr1 yêu cầu các đối số cho hoạt động có cùng loại, không phải là trường hợp cho insert.

Answer 5

Tôi thích các câu trả lời dựa trên loại được đưa ra ở đây, nhưng tôi cũng muốn đưa ra một câu hỏi giải thích lý do tại sao chúng tôi không muốn điều này đánh máy. Hãy lấy nguồn của foldr1 để bắt đầu với:

foldr1   :: (a -> a -> a) -> [a] -> a 
foldr1 _ [x] = x 
foldr1 f (x:xs) = f x (foldr1 f xs) 

Bây giờ, hãy thử chạy chương trình của bạn.

foldr1 insert [1,19,-2,7,43] 
= { list syntax } 
foldr1 insert (1:[19,-2,7,43]) 
= { definition of foldr1 } 
insert 1 (foldr1 insert [19,-2,7,43]) 
= { three copies of the above two steps } 
insert 1 (insert 19 (insert (-2) (insert 7 (foldr1 insert [43])))) 
= { definition of foldr1 } 
insert 1 (insert 19 (insert (-2) (insert 7 43))) 

... Rất tiếc! Điều đó insert 7 43 sẽ không bao giờ hoạt động. =)