-- |
-- Module      : MonusWeightedSearch.Examples.Sort
-- Copyright   : (c) Donnacha Oisín Kidney 2021
-- Maintainer  : mail@doisinkidney.com
-- Stability   : experimental
-- Portability : non-portable
--
-- Sorting using the 'Heap' monad.
--
-- The 'Heap' monad can function like a normal heap (although it does need a
-- 'Monus' instead of just any ordered key), and as such it can implement a
-- normal sorting algorithm.

module MonusWeightedSearch.Examples.Sort where

import Data.Monus.Max
import Control.Monad.Heap

-- $setup
-- >>> default (Word)

-- | /O(n log n)/. Heapsort.
--
-- >>> monusSort [5,1,2,3,1,6,3,2,5,7]
-- [1,1,2,2,3,3,5,5,6,7]
monusSort :: Ord a => [a] -> [a]
monusSort :: forall a. Ord a => [a] -> [a]
monusSort = ((a, Max a) -> a) -> [(a, Max a)] -> [a]
forall a b. (a -> b) -> [a] -> [b]
map (a, Max a) -> a
forall a b. (a, b) -> a
fst ([(a, Max a)] -> [a]) -> ([a] -> [(a, Max a)]) -> [a] -> [a]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Heap (Max a) a -> [(a, Max a)]
forall w a. Monus w => Heap w a -> [(a, w)]
search (Heap (Max a) a -> [(a, Max a)])
-> ([a] -> Heap (Max a) a) -> [a] -> [(a, Max a)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [(a, Max a)] -> Heap (Max a) a
forall (m :: Type -> Type) a w.
Applicative m =>
[(a, w)] -> HeapT w m a
fromList ([(a, Max a)] -> Heap (Max a) a)
-> ([a] -> [(a, Max a)]) -> [a] -> Heap (Max a) a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> (a, Max a)) -> [a] -> [(a, Max a)]
forall a b. (a -> b) -> [a] -> [b]
map (\a
x -> (a
x, a -> Max a
forall a. a -> Max a
In a
x)) 
{-# INLINE monusSort #-}