Contravariant version of Divide and Conquer algorithm

Cosort.hs

#! /usr/bin/env cabal
{- cabal:
build-depends:
    , base ^>= 4.12
    , contravariant ^>= 1.5
-}

{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE TypeApplications    #-}

module Main where

import Data.Functor.Contravariant (Op (..))
import Data.Functor.Contravariant.Divisible (Decidable (..), Divisible (..))
import Data.List (partition)


-- | Very general definition of the Divide and Conquer algorithm.
divideAndConquer
    :: forall f trivial nonTrivial . Decidable f
    => f trivial
    -- ^ Solve trivial problem
    -> (nonTrivial -> Either trivial nonTrivial)
    -- ^ Decide whether problem trivial or not?
    -> (nonTrivial -> (nonTrivial, nonTrivial))
    -- ^ Split nonTrivial problem into two (hopefully smaller) non trivial problems
    -> f nonTrivial
    -- ^ Solution for the nonTrivial problem
divideAndConquer solveTrivial isTrivial split = dc
  where
    dc :: f nonTrivial
    dc = choose isTrivial solveTrivial (divide split dc dc)

type Sort a = Op [a] [a]

quickSort :: Ord a => Sort a
quickSort = divideAndConquer trivialSort decide quickSortSplit

decide :: [a] -> Either [a] [a]
decide []  = Left []
decide [x] = Left [x]
decide l   = Right l

trivialSort :: Sort a
trivialSort = Op id

quickSortSplit :: Ord a => [a] -> ([a], [a])
quickSortSplit [] = ([], [])
quickSortSplit (x:xs) = let ys = partition (<x) xs in case ys of
    ([], [])        -> ([], [x])
    ([], greater)   -> ([x], greater)
    (less, [])      -> (less, [x])
    (less, greater) -> (less, x:greater)

main :: IO ()
main = do
    print $ getOp quickSort [2,1,3,0,5,2]
    print $ getOp quickSort [1,2,1,2,0,4]