list - 如何为 ziplist 创建应用实例？

Question

我想为我的自定义列表实现一个 Applicative 实例。

import Test.QuickCheck
import Test.QuickCheck.Checkers
import Test.QuickCheck.Classes


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

instance Eq a => EqProp (List a) where (=-=) = eq

instance Functor List where
  fmap _ Nil = Nil
  fmap f (Cons a Nil) = (Cons (f a) Nil)
  fmap f (Cons a as) = (Cons (f a) (fmap f as))

main = do
  let trigger = undefined :: List (Int, String, Int)
  quickBatch $ applicative trigger


instance Arbitrary a => Arbitrary (List a)  where
  arbitrary = sized go
    where go 0 = pure Nil
          go n = do
            xs <- go (n - 1)
            x  <- arbitrary
            return (Cons x xs)

instance Applicative List where
  pure x = (Cons x Nil)
  Nil <*> _ = Nil
  _ <*> Nil = Nil
 (Cons f fs) <*> (Cons a as) = (Cons (f a) (fs <*> as))

这会产生以下错误:

λ> main
applicative:
  identity:     *** Failed! Falsifiable (after 3 tests): 
Cons 0 (Cons (-1) Nil)
  composition:  *** Failed! Falsifiable (after 3 tests): 
Cons <function> (Cons <function> Nil)
Cons <function> (Cons <function> Nil)
Cons 1 (Cons (-2) Nil)
  homomorphism: +++ OK, passed 500 tests.
  interchange:  +++ OK, passed 500 tests.
  functor:      *** Failed! Falsifiable (after 3 tests): 
<function>
Cons (-2) (Cons (-1) Nil)

首先是身份证法失效:

λ> Cons id Nil <*> Cons 0 (Cons (-1) Nil)
Cons 0 Nil

我该如何解决这个问题？ pure 采用 a 而不是 List a 所以我看不到如何在 List 上匹配并保留嵌套列表结构。

合成法则也失败了，这并不奇怪:

λ> (Cons "b" Nil) <*> (Cons "c" Nil)

<interactive>:295:7:
    Couldn't match expected type ‘[Char] -> b’
                with actual type ‘[Char]’
    Relevant bindings include
      it :: List b (bound at <interactive>:295:1)
    In the first argument of ‘Cons’, namely ‘"b"’
    In the first argument of ‘(<*>)’, namely ‘(Cons "b" Nil)’
    In the expression: (Cons "b" Nil) <*> (Cons "c" Nil)

编辑:因为我得到了很好的答案来实现 ziplists 的应用程序，所以我将问题更改为关于 ziplists。

Answer 1

为您的ZipList - 类似方法，我们期望以下左恒等式保持:

pure id <*> someList = someList

为此，pure无法返回单元素列表，因为这将立即停止:

(Cons id Nil) <*> Cons 1 (Cons 2 Nil)
  = Cons (id 1) (Nil <*> Cons 2 Nil)
  = Cons 1 Nil

这不是左身份的预期结果。如果 pure不能只返回一个元素列表，它应该返回多少？答案是:无限:

repeatList :: a -> List a
repeatList x = let c = Cons x c in c

为什么我称它为 ZipList方法？因为它与 Control.Applicative.ZipList 中的行为相同, 可以通过 zipWith 激发:

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

现在你的实例是

instance Applicative List where
  pure  = repeatList
  (<*>) = zipWithList ($)

然而，checkers由于您的EqProb，无法检查此实例例如，因为 pure f <*> pure x == pure (f x) (同态)导致检查无限列表。不过，您可以提供一个替代方案。例如，您可以获取任意数量的元素并进行比较:

prop_sameList :: Eq a => (Int, Int) -> List a -> List a -> Property
prop_sameList bounds xs ys = forAll (choose bounds) $ \n -> 
  takeList n xs `eq` takeList n ys

takeList :: Int -> List a -> List a
takeList _ Nil = Nil
takeList n (Cons x xs)
 | n <= 0    = Nil
 | otherwise = Cons x (takeList (n - 1) xs)

那么，如果你想至少比较 1000最多10000元素，你可以使用:

instance Eq a => EqProb (List a) where
  (=-=) = prop_sameList (1000, 10000)

毕竟，我们只是想找到一个我们的属性不持有的列表。