Что такое обобщение unzip?

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 

, но я еще не изучил этот фрагмент проектного пространства.