推導（（）foldr相似）的類型

Question

我試圖手動派生的（（）foldr相似。）

(.) ::(b1 -> c1) -> (a1 -> b1) -> a1 -> c1 
foldr :: (a2 -> b2 -> b2) -> b2 -> [a2] -> b2 

然後類型：

b1 = a2 -> b2 -> b2 
c1 = b2 -> [a2] -> b2 

匹配我得到的類型：

((a2 -> b2 -> b2) -> (b2 -> [a2] -> b2)) -> (a1 -> (a2 -> b2 -> b2)) -> a1 -> (b2 -> [a2] -> b2) 

但是後來我對如何減少這個表達感到困惑。

任何幫助？

Thansks，
Sebastián。

Answer 1

您正確計算出(.)的類型(.) foldr。該(.)應用於一個參數（foldr），這樣你就可以扔掉((a2 -> b2 -> b2) -> (b2 -> [a2] -> b2))什麼仍然是(.) foldr類型：

(a1 -> a2 -> b2 -> b2) -> a1 -> (b2 -> [a2] -> b2) 

確保foldr可以有型((a2 -> b2 -> b2) -> (b2 -> [a2] -> b2))你把它扔掉了。如果你有相應的權利，這張支票不會失敗，但這是一個很好的理智檢查。

Answer 2

如果我們有

(.) :: (b -> c) -> (a -> b) -> (a -> c) 
foldr :: (x -> y -> y) -> y -> [x] -> y 

那麼對於(.) foldr，該b -> c擁有的foldr類型排隊，所以

b    -> c 
(x -> y -> y) -> (y -> [x] -> y) 

這意味着

b ~ (x -> y -> y) 
c ~ (y -> [x] -> y) 

所以代回在：

--     b      c 
(.) foldr :: (a -> (x -> y -> y)) -> (a -> (y -> [x] -> y)) 

由於->是左關聯的，我們可以刪除多餘的括號：

(.) foldr :: (a -> x -> y -> y) -> (a -> y -> [x] -> y) 

如果你願意，你可以更進一步與

(.) foldr :: (a -> x -> y -> y) -> a -> y -> [x] -> y 

因此，如果我們問GHCI什麼類型是，我們得到

> :t (.) foldr 
(.) foldr :: (a -> a1 -> b -> b) -> a -> b -> [a1] -> b 

其中a ~ a，a1 ~ x和b ~ y，所以我們已經得出正確的答案。