使用通用元組函數一次傳遞多個摺疊

Question

如何編寫一個函數，該函數使用ai -> b -> ai類型的函數的元組並返回一個函數，該函數使用元素類型爲ai的元組的元素，並將每個元素組合爲b元素進入ai一個新的元組的：

即簽名應該像

f :: (a1 -> b -> a1, a2 -> b -> a2, ... , an -> b -> an) -> 
    (a1, a2, ... , an) -> 
    b -> 
    (a1, a2, ... , an) 

使得：

f (min, max, (+), (*)) (1,2,3,4) 5 = (1, 5, 8, 20) 

的這點是讓我可以寫：

foldlMult' t = foldl' (f t) 

然後像做：

foldlMult' (min, max, (+), (*)) (head x, head x, 0, 0) x 

做多褶皺一個通行證。 GHC擴展是可以的。

Answer 1

如果我正確理解您的示例，則類型爲ai -> b -> ai，而不是您第一次寫入的ai -> b -> a。我們將其重寫爲a -> ri -> ri，只是因爲它幫助我思考。

首先要觀察的是這種對應關係：

(a -> r1 -> r1, ..., a -> rn -> rn) ~ a -> (r1 -> r1, ..., rn -> rn) 

這允許你寫這兩個函數，這是逆：

pullArg :: (a -> r1 -> r1, a -> r2 -> r2) -> a -> (r1 -> r1, r2 -> r2) 
pullArg (f, g) = \a -> (f a, g a) 

pushArg :: (a -> (r1 -> r1, r2 -> r2)) -> (a -> r1 -> r1, a -> r2 -> r2) 
pushArg f = (\a -> fst (f a), \a -> snd (f a)) 

第二個觀察：種形式ri -> ri的有時也被稱爲自同態，並且這些類型中的每一個都具有組合作爲關聯操作和身份函數作爲標識的幺半羣。該Data.Monoid包有此包裝爲：

newtype Endo a = Endo { appEndo :: a -> a } 

instance Monoid (Endo a) where 
    mempty = id 
    mappend = (.) 

這使您可以重寫前面pullArg這樣：

pullArg :: (a -> r1 -> r1, a -> r2 -> r2) -> a -> (Endo r1, Endo r2) 
pullArg (f, g) = \a -> (Endo $ f a, Endo $ g a) 

三觀察：二類羣的產品也是一個獨異，按本例如也Data.Monoid：

instance (Monoid a, Monoid b) => Monoid (a, b) where 
    mempty = (mempty, mempty) 
    (a, b) `mappend` (c, d) = (a `mappend` c, b `mappend d) 

同樣，對於任何數量的參數的元組。

第四觀察：What are folds made of?答：folds are made of monoids!

import Data.Monoid 

fold :: Monoid m => (a -> m) -> [a] -> m 
fold f = mconcat . map f 

這fold距離Data.Foldable的foldMap專業化，因此在現實中，我們不需要去定義它，我們就可以導入它的更一般的版本：

foldMap :: (Foldable t, Monoid m) => (a -> m) -> t a -> m 

如果fold與Endo，這與從右邊的摺疊。從左側摺疊，要與Dual (Endo r)幺折：

myfoldl :: (a -> Dual (Endo r)) -> r -> -> [a] -> r 
myfoldl f z xs = appEndo (getDual (fold f xs)) z 


-- From `Data.Monoid`. This just flips the order of `mappend`. 
newtype Dual m = Dual { getDual :: m } 

instance Monoid m => Monoid (Dual m) where 
    mempty = Dual mempty 
    Dual a `mappend` Dual b = Dual $ b `mappend` a 

記住我們pullArg功能？讓我們來修改它多一點，因爲你從左邊摺疊：

pullArg :: (a -> r1 -> r1, a -> r2 -> r2) -> a -> Dual (Endo r1, Endo r2) 
pullArg (f, g) = \a -> Dual (Endo $ f a, Endo $ g a) 

而這一點，我要求，你f的2元組版本，或者至少同構於它。你可以重構你的摺疊功能到形式a -> Endo ri，然後執行：

let (f'1, ..., f'n) = foldMap (pullArgn f1 ... fn) xs 
in (f'1 z1, ..., f'n zn) 

也值得一讀：Composable Streaming Folds，這是這些想法進一步闡述。

Answer 2

對於直接的方法，你可以定義Control.Arrow的(***)和(&&&)的等價物明確，對於每一個N（如N == 4）：

prod4 (f1,f2,f3,f4) (x1,x2,x3,x4) = (f1 x1,f2 x2,f3 x3,f4 x4) -- cf (***) 
call4 (f1,f2,f3,f4) x   = (f1 x, f2 x, f3 x, f4 x) -- cf (&&&) 
uncurry4 f  (x1,x2,x3,x4) = f x1 x2 x3 x4 

然後，

foldr4 :: (b -> a1 -> a1, b -> a2 -> a2, 
      b -> a3 -> a3, b -> a4 -> a4) 
     -> (a1, a2, a3, a4) -> [b] 
     -> (a1, a2, a3, a4)      -- (f .: g) x y = f (g x y) 
foldr4 t z xs = foldr (prod4 . call4 t) z xs  -- foldr . (prod4 .: call4) 
       -- f x1 (f x2 (... (f xn z) ...)) -- foldr . (($) .: ($)) 

所以元組的foldr4的功能是你想要的翻轉版本。測試：

前奏曲>克XS = foldr4（最小，最大，（+），（*））（頭XS，頭XS，0，1）XS
前奏曲> G [1..5]
（1,5,15,120）

foldl4'是一個調整了。由於

foldr f z xs == foldl (\k x r-> k (f x r)) id xs z 
foldl f z xs == foldr (\x k a-> k (f a x)) id xs z 

我們

foldl4, foldl4' :: (t -> a -> t, t1 -> a -> t1, 
        t2 -> a -> t2, t3 -> a -> t3) 
       -> (t, t1, t2, t3) -> [a] 
       -> (t, t1, t2, t3) 
foldl4 t z xs = foldr (\x k a-> k (call4 (prod4 t a) x)) 
         (prod4 (id,id,id,id)) xs z 
foldl4' t z xs = foldr (\x k a-> k (call4 (prod4' t a) x)) 
         (prod4 (id,id,id,id)) xs z 
prod4' (f1,f2,f3,f4) (x1,x2,x3,x4) = (f1 $! x1,f2 $! x2,f3 $! x3,f4 $! x4) 

我們甚至已經得到了類型，你想，對於元組的功能。

必須使用更嚴格的prod4版本才能在foldl4'的早期強制使用參數。