哈斯克爾：foldr相似VS foldr1

Question

如果我有這樣的插入功能：

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

這將產生一個排序列表：

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

但這：

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

產生「不能構造無限型：a0 = [a0]'

我很困惑爲什麼第二個電話無法工作。

我已經看過foldr和foldr1的定義，並且都使用簡單的算術函數進行了描述，但我仍然無法爲第二次調用失敗提出明確的解釋。

Answer 1

因爲foldr1正在努力做到這一點：

insert 43 -7 

將失敗。

Answer 2

foldr1的類型是(a -> a -> a) -> [a] -> a，即該函數的參數和結果具有相同的類型。但是，insert的型號爲Ord a => a -> [a] -> [a]。對於foldr1 insert正確類型，a和[a]必須是相同的類型。

但是這意味着a == [a] == [[a]] == [[[a]]] == ...，即a是一種無限多的列表。

Answer 3

我們來看看一些類型簽名。

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

在這兩種情況下，第一個參數都是兩個參數的函數。

• 爲foldr1，這兩個參數必須具有相同的類型（和結果具有這種類型的也）
• 爲foldr，這兩個參數可能具有不同類型（和結果具有相同類型的第二參數）

什麼是您的insert的類型？

Answer 4

是以下問題：

foldr會做這樣的：

1. 結果設置爲insert 43 []
2. 結果設置爲insert 7 result
3. 等

這顯然作品。

而foldr1將努力做到以下幾點：

1. 結果設置爲insert 7 43
2. 結果集insert -2 result
3. 等

這肯定是不對的。您可以看到，foldr1要求操作的參數是相同類型的，而insert則不是這種情況。

Answer 5

我喜歡這裏給出的基於類型的答案，但我也想給出一個操作解釋爲什麼我們不希望這種類型檢查。讓我們的foldr1源頭入手：

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

現在，讓我們嘗試運行您的程序。

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))) 

......哎呀！ insert 7 43永遠不會工作。 =）