Проблема с большим индексом при тестировании моего кода

Question

Я пытаюсь выучить Хаскель, я хочу написать рекурсивную функцию и не использовать библиотечные функции. Функция

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 является хвостом списка, проверка не является правильной, поскольку при определенных обстоятельствах она никогда не учитывает последний элемент. Действительно:

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 использует индексацию по одному. Я оставляю это как упражнение, чтобы сделать его нулевым.