QuickCheck properties for function that sorts a list of strings I'm reading The Haskell Road to Logic, Math and Programming and for each exercise solution I write some properties to learn QuickCheck. One of the exercises is to write a function that sorts a list of strings (srtStr). I wonder if my properties are right. Also, is there something missing?

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 &lt;= y else False)
    process _            state = state

check ∷ IO ()
check = do
    quickCheck propIdempotent
    quickCheck propLength
    quickCheck propOrder
Correctness of a sorting algorithm consists of showing that the resulting list is in order which your propOrder takes care of and that the resulting list is a permutation of the other list. Your propLength does the latter partially. It prevents you from adding or removing an element out of thin air but doesn't prevent you to replace one with another.

You can write a permutation checker as follows:

First define a subbag relation that is every element of the first list appears in the second.

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


Then you can write a permutation checker by applying it both ways.

isPerm :: Eq a =&gt; [ a ] -&gt; [ a ] -&gt; Bool
isPerm xs ys = isSubBag xs ys &amp;&amp; isSubBag ys xs


Your property comes out as:

propPerm :: [ String ] -&gt; Bool
propPerm xs = isPerm xs (srtStr xs)


Overall, you can improve your process function by eliminating accumulator and using the built-in conjunction. Also a better name for it would be isInOrder

process :: [String] -&gt; Bool
process (x : y : xs) = x &lt;= y &amp;&amp; process (y : xs)
process _ = True