Instance Ord a => Ord (Pattern a)

Dear Lounge, I was reading the source

instance Ord a => Ord (Pattern a) where
  min = liftA2 min
  max = liftA2 max
  compare = noOv "compare"
  (<=) = noOv "(<=)"

and I thought - why allow min and max, but not compare? I think I have an explanation, and an application for that. (Well, you decide whether it's useful at that.)


it's the types (of course it is). We have min :: Ord a => a -> a -> a, and when we instantiate a with Pattern a, we get min @(Pattern _) :: Ord w => Pattern w -> Pattern w -> Pattern w. How does it work? Same way we multiply or add: combine each value from the left with each value from the right (for overlapping events).

min (3 - run 3) (run 4)

Why does this not work for compare? The type is compare :: Ord a => a -> a -> Ordering, after instantiation: compare @(Pattern _) :: Ord w => Pattern w -> Pattern w -> Ordering (and not: ... -> Pattern Ordering), and that has no sensible semantics (how would you define one pattern to be smaller than another).


sorting a list of patterns (if their elements are orderable, e.g., numbers (for notes)). The catch is that we cannot use Data.List.sort (mergesort): it's statically correct (the types match) but dynamic semantics (value) is "throws an exception".

tidal> import Data.List (sort)
tidal> sort @(Pattern Int) [pure 1, pure 2]
*** Exception: compare: not supported for patterns

because the implementation will call compare, which we did not implement.

And now the nice thing is that we can still sort - using min and max only! We write a data-oblivious program (control flow does not depend on input data). Such sorting algorithms exists, and they are "sorting networks", consisting of compare-and-swap gates: input (x,y) gives output (min x y, max x y). A simple realisation is odd-even transposition sort (Odd-even transposition sort).

In the following example, I make a random sequence (of notes) as input to the network, and we hear each layer in turn (in fact, two times, so we have a chance to adapt). Last layer is sorted (from lowest to highest note). For example, on input [4,3,2,1,0], we get these layers:
[[4,2,3,1,0],[2,4,1,3,0],[2,1,4,0,3],[1,2,0,4,3],[1,0,2,3,4],[0,1,2,3,4]]. (source code tidal/code/sorting.tidal · master · waldmann / computer-mu · GitLab , audio tidal/code/sorting.ogg · master · waldmann / computer-mu · GitLab )

Challenge question: in my code, change [0 .. 5] to [0 .. 7] (or similar), observe the glitches (skips), and explain.

Related work

This was, of course, inspired by Earth-to-Abigail's work on sonification of sorting ( How To Create An Audio Representation Of Bubble Sort With Ruby And Sonic Pi — Earth to Abigail ) - and I only found out recently that they seem use this prominently in Passarinho Azul (The Forest | Earth to Abigail ). Well, that's pure beauty - which I avoided by using the chromatic scale, to get a more brutalist effect.

1 Like

Great post, thanks!

I don't have a working ghci to test it at the moment, but I imagine that min x y and max x y may not be either x or y, but something else. It's not in base but Pattern looks like a lattice.

min x y and max x y may not be either x or y, but something else.

Yes. For instance, with my program,

mmsort [2 * run 2, 2 - run 3]

[[(0>½)|0 (½>1)|2                ,(0>⅓)|2 (⅓>⅔)|1 (⅔>1)|0        ]
,[(0>⅓)|0 (⅓>½)|0 (½>⅔)|1 (⅔>1)|0,(0>⅓)|2 (⅓>½)|1 (½>⅔)|2 (⅔>1)|2]

I should explore this musically (structure of arguments of mmsort gets merged, thus, more complicated, possibly more interesting).

Pattern looks like a lattice

Yes, I'd say instance Lattice a => Lattice (Pattern a).