如何为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)

首先是id法失败了:

?> 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的问题.

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方法？因为它与in的行为相同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)

毕竟,我们只是想找到一个我们的财产不能容纳的清单.