适用于ZipList的实现

Question

[这来自《第一原理》中Haskell的练习。练习是为Applicative实现ZipList'，这类似于Prelude的ZipList。这本书有这个提示

检查前奏提供可以满足您需求的功能。一开始带字母z，另一个带字母r。你在找从这些功能中获取灵感，而不是直接在使用自定义列表类型（而非提供的列表类型）时重复使用它们前奏列表类型。

我猜以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开头的函数。我觉得这应该是repeat，因为它也可以在无限列表上使用。

编辑：我在Robin Zigmond发表评论后考虑了一下。此实现应满足适用法律。

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)

repeat' :: a -> List a
repeat' x = Cons x $ repeat' x

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' $ repeat' x
  (ZipList' fs) <*> (ZipList' xs) = ZipList' $ zipWith' ($) fs xs

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的定义）变形。