haskell - 为自定义 ZipList 实现 Applicative

Question

这来自Haskell from First Principles一书中的练习。本练习是为 ZipList' 实现 Applicative，这类似于 Prelude 的 ZipList。书上有这个提示

Check Prelude for functions that can give you what you need. One starts with the letter z, the other with the letter r. You’re looking for inspiration from these functions, not to be able to directly reuse them as you’re using a custom List type, not the Prelude provided list type.

我猜测以 z 开头的函数是 zipWith，但我不知道以 r 开头的函数。

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

zipWith' :: (a -> b -> c) -> List a -> List b -> List c
zipWith' _ Nil _ = Nil
zipWith' _ _ Nil = Nil
zipWith' f (Cons x xs) (Cons y ys) = Cons (f x y) (zipWith' f xs ys)

newtype ZipList' a = ZipList' (List a)
  deriving (Eq, Show)

instance Functor ZipList' where
  fmap f (ZipList' xs) = ZipList' $ fmap f xs

instance Applicative ZipList' where
  pure x = ZipList' $ Cons x Nil
  (ZipList' fs) <*> (ZipList' xs) = ZipList' $ zipWith' ($) fs xs

这通过了书中的一个测试用例，但我想知道是否有更好的方法来实现它，因为我没有使用以r开头的函数。我有一种感觉，这应该是重复，因为它也应该在无限列表上工作。

Answer 1

阅读原始帖子下的线程，我得出一个结论，该帖子的作者试图证明该实现满足法律( fmap f xs = (pure f) <*> xs ):

让我们尝试将其证明为经典恒等式，摆脱包装。因此，让我们用右手工作:

(pure f) <*> xs = (repeat' f) <*> xs = zipWith' ($) (repeat' f) xs ;

就身份而言，证明 zipWith' ($) (repeat' f) xs等于 fmap f xs就足够了。

它们相同的原因非常明显:

length (zipWith op xs ys) == min (length xs) (length ys) ; (在 xs 和 ys 均为无限的情况下，无法计算此表达式)。

自 repeat' f是无限的，length $ zipWith' ($) (repeat' f) xs事实上，length xs (在这里，这样的值是否存在实际上并不重要:索引的存在就足够了)。 xs 的每个元素应用于相同的函数 f ，这是重复的。正如您所看到的，大小被保留，并且每个元素都通过常量函数变形，这就是 fmap 的定义。 .