330 - PurelyFunctional.tv - Newsletter - https://purelyfunctional.tv/issues/purelyfunctional-tv-newsletter-330-tool-figwheel/

00 Properties of sort.md

properties of sort

When we are testing a function with property-based testing, we want to make sure our tests are not re-implementing the function we are testing. On the contrary, we want the test to be simpler and more obviously correct.

It's often challenging to come up with properties, especially if you do know how the function works. This week, we will face that challenge head on.

The challenge this week is to come up with at least three properties we would like to assert on the sort function. You can write them however you like. You can write them in English, or if you want, as test.check properties. What's important is the thought process behind it.

Alan Thompson.md

Properties of sort:

1. Length before = after (easy)
2. multiset of before = after (harder unless have a native multiset type)
3. item(i) <= item(j) (easy)
4. Optional: stability of sort for "equal" items (requires a non-sorted field to verify, like SSN if sort by name) (hardest to test)

Magnus Kvalevag.clj

(defspec sort-keeps-same-number-of-elements 100
  (prop/for-all [l (gen/vector gen/int)]
    (= (count l)
       (count (sort l)))))

(defspec each-element-in-original-list-exists-in-sorted-list 100
  (prop/for-all [l (gen/vector gen/int)]
    (let [sorted-list (sort l)]
      (every?
        (fn [el] (some #(= el %) sorted-list))
        l))))

(defspec each-element-is-smaller-or-equal-to-the-next 100
  (prop/for-all [l (gen/vector gen/int)]
    (->> (sort l)
         (partition 2 1)
         (every? #(apply <= %)))))

;; I think those three should cover sort. Here's some other ones that I could think of:

(defspec sort-is-idempotent 100
  (prop/for-all [l (gen/vector gen/int)]
    (let [sorted (sort l)]
      (= sorted (sort sorted)))))

(defspec each-element-in-sorted-list-exists-in-original-list 100
  (prop/for-all [l (gen/vector gen/int)]
    (every?
      (fn [el] (some #(= el %) l))
      (sort l))))

(defspec sort-first-element-is-the-smallest 100
  (prop/for-all [l (gen/vector gen/int)]
    (if (seq l)
      (= (apply min l)
         (first (sort l)))
      true)))

;; ...and then there's this monster which recursively checks that the first number in the sorted list is the same as the smallest number in the original list, removing those numbers for each iteration until both lists are empty:

(defn- find-smallest-with-index
  [l]
  (->> l
       (map-indexed
         (fn [i e]
           {:index   i
            :element e}))
       (apply min-key :element)))

(defn- remove-nth
  [l n]
  (concat (subvec (vec l) 0 n)
          (subvec (vec l) (inc n) (count l))))

(defn- sort-first-element-is-the-smallest-advanced-helper
  "Return a tuple of tuples like this:
   [[ the-smallest-number-in-unsorted-list,   rest-of-unsorted-list ]
    [ the-first-number-in-sorted-list,        rest-of-sorted-list   ]]"
  [unsorted sorted]
  (let [{:keys [index element]} (find-smallest-with-index unsorted)]
    [[element
      (remove-nth unsorted index)]
     [(first sorted)
      (rest sorted)]]))

(defspec sort-first-element-is-the-smallest-advanced 100
  (prop/for-all [l (gen/vector gen/int)]
    (loop [unsorted l
           sorted   (sort l)]
      (if (empty? unsorted)
        (empty? sorted)
        (let [[[unsorted-min unsorted-rest]
               [sorted-first sorted-rest]] (sort-first-element-is-the-smallest-advanced-helper unsorted sorted)]
          (when (= unsorted-min sorted-first)
            (recur unsorted-rest sorted-rest)))))))

Mark Champine.clj

(ns sortprop.core
  (:require [clojure.math.combinatorics :as combo]
            [clojure.test.check :as tc]
            [clojure.test.check.generators :as gen]
            [clojure.test.check.properties :as prop]))


;;;; Property 1. sorting a sorted is sorted ;;;;
(def sort-sort-is-sort
  (prop/for-all [v (gen/vector gen/int)]
    (= (sort v) (sort (sort v)))))

(tc/quick-check 100 sort-sort-is-sort)
;; {:result true, :num-tests 100, :seed 1560357962512}

(def sort-sort-is-sort-str
  (prop/for-all [v (gen/not-empty gen/string)]
    (= (sort v) (sort (sort v)))))

(tc/quick-check 100 sort-sort-is-sort-str)
;; {:result true, :num-tests 100, :seed 1560435933339}

;;;; Property 2. sort uses compare by default ;;;;
(def sort-uses-compare-def
  (prop/for-all [v (gen/vector gen/int)]
    (= (sort v) (sort compare v))))

(tc/quick-check 100 sort-uses-compare-def)
;; {:result true, :num-tests 100, :seed 1560357979976}

(def sort-uses-compare-def-str
  (prop/for-all [v (gen/not-empty gen/string)]
    (= (sort v) (sort compare v))))

(tc/quick-check 100 sort-uses-compare-def-str)
;; {:result true, :num-tests 100, :seed 1560436022901}


;;;; Property 3. Sorting preserves length ;;;;
(def sort-length-invariant
  (prop/for-all [v (gen/vector gen/int)]
    (= (count v) (count (sort v)))))

(tc/quick-check 100 sort-length-invariant)
;; {:result true, :num-tests 100, :seed 1560357999327}

(def sort-length-invariant-str
  (prop/for-all [v (gen/not-empty gen/string)]
    (= (count v) (count (sort v)))))

(tc/quick-check 100 sort-length-invariant-str)
;; {:result true, :num-tests 100, :seed 1560436128572}


;;;; Property 4. Sort order applies between every 2 successive elements ;;;;
(def sort-applies-pairwise
  (prop/for-all [v (gen/vector gen/int)]
    (->> (sort v)
         (partition 2 1)
         (map (fn [[a b]] (compare a b)))
         (every? (complement pos?)))))

(tc/quick-check 100 sort-applies-pairwise)
;; {:result true, :num-tests 100, :seed 1560358019543}

(def sort-applies-pairwise-str
  (prop/for-all [v (gen/not-empty gen/string)]
    (->> (sort v)
         (partition 2 1)
         (map (fn [[a b]] (compare a b)))
         (every? (complement pos?)))))

(tc/quick-check 100 sort-applies-pairwise-str)
;; {:result true, :num-tests 100, :seed 1560436247579}


;;;; Property 5. Sort doesn't rearrange equivalent values. ;;;;

;; This is a generalized function that tests if order is preserved when
;; sort is called with a comparator that returns equal (zero) for
;; multiple values. See writeup for explanation.
(defn eq-order-preserved? [s pred]
  (let [comparator (fn [a b] (compare (pred a) (pred b)))
        sorted (sort comparator s)
        grouped-s (map second (sort (group-by pred s)))
        partitioned-sorted-s (partition-by pred sorted)]
    (every? true? (map = grouped-s partitioned-sorted-s))))


;;;;;; Property 5 example 1 - compare values mod 10 ;;;;;;
;; sorted output partition-by mod 10
;; -------------------
;; ((60 10 90 30)
;;  (21 91 41 1)
;;  (42 2 52)
;;  (23 3 33)
;;  (65 65 95 55)
;;  (46 66 16)
;;  (77 57)
;;  (38 38 48)
;;  (9 79 29 89))

;; original input grouped-by mod 10
;; -----------------
;; ([60 10 90 30]
;;  [21 91 41 1]
;;  [42 2 52]
;;  [23 3 33]
;;  [65 65 95 55]
;;  [46 66 16]
;;  [77 57]
;;  [38 38 48]
;;  [9 79 29 89])

;; As you can see, if the mod 10 sort didn't preserve order then the 'chunks'
;; in the sorted-then-partitioned values above wouldn't be in the same order as
;; in the grouping of unsorted input.
;; Note that this depends on group-by preserving order!

;;;;;; Property 5 Example 2. Compare chars with isUpperCase. ;;;;;;

(def sort-eq-order-preserved-isupper
  (prop/for-all [v (gen/not-empty gen/string)]
    (eq-order-preserved? v #(Character/isUpperCase %))))

(tc/quick-check 100 sort-eq-order-preserved-isupper)
;; {:result true, :num-tests 100, :seed 1560358046843}

;; How it works
;; starting with unsorted input:  "hMiESddSSeAGnE"
;; sorted with isUpperCase: (\h \i \d \d \e \n \M \E \S \S \S \A \G \E)

;; partitioned by Character/isUpperCase:
;; ((\h \i \d \d \e \n) (\M \E \S \S \S \A \G \E))

;; original (unsorted) input grouped-by Character/isUpperCase:
;; ([\h \i \d \d \e \n] [\M \E \S \S \S \A \G \E])

;; The preservation of order for equivalent values is shown by the fact that
;; partitioning the sorted sequence gives the same result as grouping the
;; original unsorted sequence.


;;;; Property 6. First is min, last is max. ;;;;
(def sort-first-min-last-max
  (prop/for-all [v (gen/not-empty (gen/vector gen/int))]
     (and (= (apply min v) (first (sort v)))
          (= (apply max v) (last (sort v))))))

(tc/quick-check 100 sort-first-min-last-max)
;; {:result true, :num-tests 100, :seed 1560434601500}


;;;; Property 7. First is <= last ;;;;
(def sort-first-le-last
  (prop/for-all [v (gen/not-empty (gen/vector gen/int))]
    (<= (first (sort v)) (last (sort v)))))

(tc/quick-check 100 sort-first-le-last)
;; {:result true, :num-tests 100, :seed 1560434676200}

(def sort-first-le-last-str
  (prop/for-all [v (gen/not-empty gen/string)]
    ((complement pos?) (compare (first (sort v)) (last (sort v))))))

(tc/quick-check 100 sort-first-le-last-str)
;; {:result true, :num-tests 100, :seed 1560437999911}