1 {-# LANGUAGE TypeInType, TypeOperators, TypeFamilies,

2 UndecidableInstances, ConstraintKinds #-}

11 -- We define a very simplistic O notation, with sufficient expressiveness

12 -- to capture the complexity of a few simple sorting algorithms

15 -- Synonyms for common terms

20 -- Just to be able to write it nicely

44 -- Stable sorts must be stable, but unstable can be, but don't need to.

46 -- We encode in the return type of the sorting function its average complexity,

47 -- memory use and stability.

49 -- this algorithm satisfies.

51 -- algorithm satisfies.

53 a -- What was being sorted.

56 -- Merge sort is O(N*Log(N)) on average in complexity, so that's the

57 -- minimum complexity we promise to satisfy. Same goes with memory, which is

58 -- O(N), and as we all know, mergesort is a stable sorting algoritm.

67 -- Note that we don't actually check the complexity (as evidenced by them all

68 -- being implemented with sort, a smooth applicative merge sort). With more

69 -- dependent types however, some of these properties might be verifiable.

76 -- Here we say that sorted can use at most operational complexity O(N^2), space

77 -- complexity of at most (O(N)) and that it should be stable.