list - 测试我的代码时出现大索引问题

Question

我正在尝试学习Haskell，我想写一个递归函数并且不使用任何库函数。功能

nth ::Integer -> [a ] -> Maybe a

获取一个索引 n 和一个元素列表，并返回列表的第 n 个元素(如果索引有效)或 Nothing 如果索引无效。

我的代码:

nth :: Integer -> [a] -> Maybe a
nth a [] = Nothing
nth a (x:xs) |a == 1 = Just x 
             |fromIntegral (length xs) < a = Nothing 
             |a==0 = Nothing
             | otherwise = nth (a-1) xs  

我想对我的代码做这个测试:

spec = do

    describe "nth" $ do
        it "for valid indexes it behaves like (!!)" $
            property $ \n xs -> n < 0 || (fromInteger n) >= length (xs::[Integer]) || Lists.nth n xs == Just (xs!!(fromInteger n))
        it "for negative indexes it returns Nothing" $
            property $ \n xs -> n >= 0 || Lists.nth n (xs::[Integer]) == Nothing
        it "for too large indexes it returns Nothing" $
            property $ \n xs -> (fromInteger n) < length xs || Lists.nth n (xs::[Integer]) == Nothing

但是每次我做测试的时候都会出错

  for valid indexes it behaves like (!!) FAILED [1]
    for negative indexes it returns Nothing
      +++ OK, passed 100 tests.
    for too large indexes it returns Nothing FAILED [2]

1) Lists.nth for valid indexes it behaves like (!!)
       Falsified (after 5 tests and 5 shrinks):
         0
         [0]

  To rerun use: --match "/Lists/nth/for valid indexes it behaves like (!!)/"

  ./ListsSpec.hs:23:9: 
  2) Lists.nth for too large indexes it returns Nothing
       Falsified (after 38 tests):
         1
         [0]

Answer 1

您的函数存在一些问题。第一种情况(表现像 (!!) )失败的原因是因为 (!!) :: Int -> [a] -> a使用从零开始的索引，而您的函数似乎使用从一开始的索引。这意味着您将因此需要减少给函数的索引。

此外，在您的函数中，您对 n 进行了比较和 fromIntegral (length xs) .自 xs是列表的 tail，检查不正确，因为在某些情况下它永远不会考虑最后一个元素。确实:

Prelude> nth 2 [0, 2]
Nothing

此外，使用 length 通常不是一个好主意在每次 迭代中。 length在 O(n) 中运行，这意味着您的算法现在在 O(n²) 中运行，因此随着列表的增长，这很容易将开始花费大量时间。

解决这个问题的更短、更优雅的方法可能是:

nth :: Integral i => i -> [a] -> Maybe a
nth 1 (x:_) = Just x
nth i (_:xs) | i < 1 = Nothing
             | otherwise = nth (i-1) xs
nth _ [] = Nothing

因此我们有四种情况:如果索引是 1并且列表是非空的，我们返回列表的头部，包裹在 Just 中.如果索引不是一，并且小于一，则索引太小，因此我们返回 Nothing (这种情况严格来说是没有必要的)。如果i大于一，那么我们称nth (i-1) xs .最后，如果我们到达列表的末尾(或者列表一开始是空的)，我们返回 Nothing以及)。

现在为了测试这一点，我们需要重写这三种情况:

describe "nth" $ do
    it "for valid indexes it behaves like (!!)" $
        property $ \n xs -> n <= 0 || n > length (xs :: [Integer]) || Lists.nth n xs == Just (xs !! (n-1))
    it "for negative indexes it returns Nothing" $
        property $ \n xs -> n > 0 || Lists.nth n (xs :: [Integer]) == Nothing
    it "for too large indexes it returns Nothing" $
        property $ \n xs -> n <= length xs || Lists.nth n (xs :: [Integer]) == Nothing

因此第一个排除了 n <= 0 (负数或零索引)以及 n > length xs从而检查该值是否为 Just (xs !! (n-1)) .

在第二种情况下排除大于零的值，并检查所有剩余索引是否映射到 Nothing .

最后一个属性检查是否存在高于 length xs 的值, 我们也一无所获。

注意这里是nth使用基于一个的索引。我把它留作练习，让它从零开始。