Встраиваемое свойства для функции, которая сортирует список строк


Я читаю Хаскелл дорога к логике, математике и программированию, и для каждого решения упражнений я пишу некоторые свойства научиться Встраиваемое. Одно из упражнений-написать функцию, которая сортирует список строк (srtStr). Интересно, если мои свойства права. Кроме того, есть что-то отсутствует?

propIdempotent ∷ [String] → Bool
propIdempotent xs = srtStr xs == srtStr (srtStr xs)

propLength ∷ [String] → Bool
propLength str = length str == length (srtStr str)

propOrder ∷ [String] → Bool
propOrder xs = process (srtStr xs) True where
    process ∷ [String] → Bool → Bool
    process (x : y : xs) state = process xs (if state then x <= y else False)
    process _            state = state

check ∷ IO ()
check = do
    quickCheck propIdempotent
    quickCheck propLength
    quickCheck propOrder


262
8
задан 5 апреля 2018 в 08:04 Источник Поделиться
Комментарии
3 ответа

Правильность алгоритм сортировки состоит из показывает, что полученный список в порядке которой ваши propOrder заботится о, и что результирующий список-это перестановка из другого списка. Ваш propLength не последним частично. Это предотвращает добавление или удаление элемента из воздуха, но не мешает вам заменить одно с другим.

Вы можете написать чекер перестановку следующим образом:

Сначала определить subbag отношения, что каждый элемент первого списка появляется во второй.

isSubBag :: Eq a => [ a ] -> [ a ] -> Bool
isSubBag [] ys = True
isSubBag (x:xs) ys = x `elem` ys && isSubBag xs (delete x ys)

Затем вы можете написать чекер перестановки, применяя его в обе стороны.

isPerm :: Eq a => [ a ] -> [ a ] -> Bool
isPerm xs ys = isSubBag xs ys && isSubBag ys xs

Ваше имущество выходит как:

propPerm :: [ String ] -> Bool
propPerm xs = isPerm xs (srtStr xs)

В целом, вы можете улучшить свои функции за счет устранения аккумулятор и с помощью встроенного в сочетании. Также название получше будет isInOrder

process :: [String] -> Bool
process (x : y : xs) = x <= y && process (y : xs)
process _ = True

4
ответ дан 5 апреля 2018 в 08:04 Источник Поделиться

Одно свойство, которое приходит на ум, заключается в том, что применяя любые перестановки перед srtStr не меняет результата. Но что такое перестановка? Я бы сказал, что это функция, которая не эксплуатирует свойства типа элемента, имеет левый обратный и сохраняет длину. (Первая гарантирует, что используются только элементы ввода. Второй гарантирует, что элементы не могут быть отброшены. Третий гарантирует, что нет места для дублированных элементов.)

propPermutationInvariant
:: (forall a. [a] -> [a]) -> (forall a. [a] -> [a]) -> [String] -> Bool
propPermutationInvariant permutation inverse xs
= length (permutation xs) /= length xs
|| inverse (permutation xs) /= xs
|| srtStr xs == srtStr (permutation xs)

Например, это означает srtStr xs == strStr (reverse xs)через propPermutationInvariant reverse reverse xs.

2
ответ дан 5 апреля 2018 в 09:04 Источник Поделиться

Помимо других ответов, я бы хотел обратить внимание на несколько деталей.

Во-первых, в вашем process функция пропустить слишком далеко, нужно пройти через элементы по одному. Код применяется к [4, 5, 2, 3, 0, 1] проходит. А вам нужно, чтобы соответствовать шаблону, как это:

... process (x : xs@(y : _)) state = process xs (if state then x <= y else False)

Далее, как указал в комментарии, это лучше короткого замыкания, если имущество не удастся. Это более эффективный, а также более идиоматические в Haskell. Используйте аккумулятор только если вам это нужно. Что-то вроде этого:

prop_order :: [String] -> Bool
prop_order (x : xs@(y : _)) = (x <= y) && prop_order xs
prop_order _ = property ()

Также обратите внимание, что (if state then x <= y else False) может быть упрощен до state && (x <= y).

Наконец, я предлагаю вам выразить свое имущество таким образом, что вы получаете более подробную информацию о том, что случилось в непройденного теста. Это может быть достигнуто с помощью Property вместо Bool в результате тип и используя комбинаторы в тест.Встраиваемое.Собственность:

import Test.QuickCheck
import Test.QuickCheck.Property

-- | Tests if left is less or equal than right.
(<?=) :: (Ord a, Show a) => a -> a -> Property
x <?= y = counterexample (show x ++ " must be less than " ++ show y) (x <= y)

prop_order :: [String] -> Property
prop_order (x : xs@(y : _)) = (x <?= y) .&&. prop_order xs
prop_order _ = property ()

Обратите внимание, что операторы (.&.) и (.&&.) очень разные!

Я бы предпочел еще один вариант использования conjoin, который избавляет вас от явной рекурсии. Сжать список с хвостом, мы вам все последовательные пары, и тогда мы просто высказываем, что каждая из таких пар должны удовлетворять <?=.

prop_order2 :: [String] -> Property
prop_order2 xs = conjoin $ zipWith (<?=) xs (tail xs)

1
ответ дан 8 апреля 2018 в 09:04 Источник Поделиться