为隐藏变量添加Monoid约束及ZipList的Applicative实例实现疑问

最近在啃《Haskell Book》的Applicative章节，写自定义ZipList'的Applicative实例时，发现一开始的思路绕了弯路，现在重新梳理了实现方案；同时还碰到了给隐藏变量添加Monoid约束的相关疑问，先把原来的代码框架贴出来：

data List a = Nil | Cons a (List a) deriving (Eq, Show)
newtype ZipList' a = ZipList' (List a) deriving (Eq, Show)
instance Applicative ZipList' where
  pure a = ZipList' (Cons a Nil)
  ZipList' Nil <*> _ = ZipList' Nil
  _ <*> ZipList' Nil = ZipList' Nil
  (ZipList' (Cons a bs)) <*> (ZipList' (Cons a' bs')) = (...的内容)

调整后的Applicative实例实现 #

我一开始犯了个典型错误：把pure实现成只包含单个元素的List，但ZipList的核心语义是逐元素函数应用，如果pure只提供一个元素，那和任何更长的ZipList'结合时都会提前终止，完全不符合预期。

后来调整了思路，先实现一个生成无限重复元素的辅助函数，然后基于它来实现pure；(<*>)则处理两个List的逐元素配对应用，遇到空列表就停止：

data List a = Nil | Cons a (List a) deriving (Eq, Show)
newtype ZipList' a = ZipList' (List a) deriving (Eq, Show)

-- 生成无限重复元素的自定义List
repeat' :: a -> List a
repeat' x = Cons x (repeat' x)

-- 解开ZipList'包装的辅助函数
getZipList' :: ZipList' a -> List a
getZipList' (ZipList' l) = l

instance Applicative ZipList' where
  -- pure生成无限重复当前元素的ZipList'，符合ZipList的语义
  pure a = ZipList' (repeat' a)
  -- 空列表和任何列表结合都返回空
  ZipList' Nil <*> _ = ZipList' Nil
  _ <*> ZipList' Nil = ZipList' Nil
  -- 逐元素应用函数，递归处理剩余列表
  ZipList' (Cons f fs) <*> ZipList' (Cons x xs) =
    ZipList' $ Cons (f x) (getZipList' $ ZipList' fs <*> ZipList' xs)

这样调整后，pure出来的ZipList'可以和任意长度的ZipList'正常结合，比如pure (+1) <*> ZipList' (Cons 1 (Cons 2 Nil))会得到ZipList' (Cons 2 (Cons 3 Nil))，完全符合Applicative的法则。

关于隐藏变量的Monoid约束问题 #

一开始我纠结“给隐藏变量加Monoid约束”，后来想明白：如果只是实现Applicative实例，完全不需要Monoid约束，因为Applicative的核心操作和Monoid无关。

但如果是想给ZipList'添加Monoid实例，或者需要在某些场景下合并多个ZipList'，这时候才需要考虑约束——不过约束不是针对隐藏的List类型，而是针对元素类型a。比如我们想实现“逐元素合并”的Monoid行为（而不是拼接List），就需要a是Monoid：

instance Monoid a => Monoid (ZipList' a) where
  -- mempty是无限重复元素的mempty
  mempty = ZipList' (repeat' mempty)
  -- mappend逐元素用Monoid的mappend合并，取较短列表的长度
  mappend (ZipList' xs) (ZipList' ys) = ZipList' (zipWithMappend xs ys)
    where zipWithMappend Nil _ = Nil
          zipWithMappend _ Nil = Nil
          zipWithMappend (Cons x xs') (Cons y ys') = Cons (x `mappend` y) (zipWithMappend xs' ys')

这里的约束Monoid a是为了让每个元素都能被合并，而不是给隐藏的List加约束——毕竟List本身的Monoid是拼接，但这不符合ZipList'的逐元素语义。

内容的提问来源于stack exchange，提问作者tesserakt