解壓縮的泛化是什麼？

Question

我從列表中知道的大多數方法實際上是一些衆所周知的類型類的特例。的方法的一些實例和相關類型的類：

• map :: (a -> b) -> [a] -> [b]和Functor
• foldr :: (a -> b -> b) -> b -> [a] -> b和Foldable
• forM :: Monad m => [a] -> (a -> m b) -> m [b]和Traversable
• concat :: [[a]] -> [a]和Monad

也許這樣的例子不勝枚舉（赦免雙關語）。

我想知道unzip :: [(a, b)] -> ([a], [b])背後的「深層含義」。它可以使用一些着名的實例[]和例如(,a)的函數實例來實現嗎？或者其他一些情況？理想情況下，我想要使用這種類型的抽象函數：SomeClass m => unzip :: m (a, b) -> (m a, m b)。有沒有一個班會做這個工作？

Answer 1

您可以簡單地採取第一和第二突出：

gunzip :: Functor f => f (a, b) -> (f a, f b) 
gunzip ps = (fmap fst ps, fmap snd ps) 

但需要注意的是gunzip穿越ps兩次不同於通常zip的列表，所以它的麻煩，因爲ps不是第一遍住宿後收集垃圾在內存中，這導致大列表上的內存泄漏。

Answer 2

直觀上，unzip'函數具有推倒保持(a,b)的結構，然後構建它到該結構的兩個副本，其中第一個包含a並且其包含b第二。

一個可能的推廣，在另一個答案已經提到的，是

unzip' :: (Functor t) => t (a, b) -> (t a, t b) 
unzip' xs = (fmap fst xs, fmap snd xs) 

這符合該法案，但一個缺點是，它的初始結構越過兩次 - 一次每次調用fmap。

---

的Foldable類描述可以遍歷，構建一個結果，因爲我們去的結構。我們可以利用這個屬性來確保我們只傳遞一次初始結構（一次調用foldr），但我們仍然需要知道如何再次構建結構的副本。

的MonadPlus型類提供的方法來得到一個空的結構，並結合了兩種結構（有點像高階Monoid） -

class Monad m => MonadPlus m where 
    mzero :: m a 
    mplus :: m a -> m a -> m a 

有了這個，我們可以寫

import Control.Monad 
import Data.Foldable (foldr) 

unzip' :: (Foldable t, MonadPlus m) => t (a, b) -> (m a, m b) 
unzip' = foldr f (mzero, mzero) 
    where 
    f (a,b) (as, bs) = (mplus (return a) as, mplus (return b) bs) 

然後我們可以做像

>> unzip' [(1,2), (3,4)] :: ([Int], [Int]) 
([1,3],[2,4]) 

而且

>> unzip' (Right (1,2)) :: ([Int], Maybe Int) 
([1],Just 2) 

---

最終的一個想法 - 這是一個有點醜，我們需要調用mplus (return a) as。這可能是更好的類似

class Listish m where 
    null :: m a 
    cons :: a -> m a -> m a 

但我沒有真正探索這一點的設計空間。