解压缩的概括是什么？

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]).它可以使用一些着名的实例来实现吗？[]例如,functor实例(,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

但我还没有真正探索过这一点设计空间.