all sorts of permutations (insertion sort)

all_sorts_of_permutations_insertion_sort.hs

--
--  http://informatik.uni-kiel.de/~sad/icfp2016-preprint.pdf
--

import Control.Monad.Identity
--
-- pure insertion sort
--
 
insert :: (a -> a -> Bool) -> a -> [a] -> [a]
insert _ x [] = [x]
insert p x yys@(y:ys) = if (p x y) then x:yys else y:insert p x ys

-- *Main> insert (<=) 3 [1,2,4,5]
-- [1,2,3,4,5]

insertSort :: (a-> a-> Bool) -> [a] -> [a]
insertSort _ [] = []
insertSort p (x:xs) = insert p x (insertSort p xs)

-- *Main> insertSort (<) [5,4,3,2,1]
-- [1,2,3,4,5]

type Comp a m = a -> a -> m Bool

--
-- Monadic
--

insertM :: Monad m => (Comp a m) -> a -> [a] -> m [a]
insertM _ x [] = return [x]
insertM p x yys@(y:ys) = p x y >>= \b -> if b then return (x:yys) else fmap (y:) (insertM p x ys)


insertSortM :: Monad m => (Comp a m) -> [a] -> m [a]
insertSortM _ [] = return []
insertSortM p (x:xs) = insertSortM p xs >>= \ys -> insertM p x ys

cmpid :: Comp Int Identity
cmpid x y = return (x <= y)

-- > runIdentity (insertSortM cmpid (reverse [1,2,3,4,5]))
-- [1,2,3,4,5]
--
-- > insertSortM (\x y -> [True, False]) [1,2,3]
-- [[1,2,3],[2,1,3],[2,3,1],[1,3,2],[3,1,2],[3,2,1]]