{-
Haskell code accompanying the draft "A greedy algorithm for dropping digits",
by Richard Bird and Shin-Cheng Mu, submitted to Journal of Functional Programming.
-}
type Set a = [a]
type List a = [a]
type Nat = Int
-- Specification
drops :: List a -> Set (List a)
drops [x] = [[]]
drops (x:xs) = xs : map (x:) (drops xs)
solve1 :: Ord a => Nat -> List a -> List a
solve1 k = maximum . apply k step . wrap
step :: Set (List a) -> Set (List a)
step = concat . map drops
apply :: Nat -> (a -> a) -> a -> a
apply 0 f = id
apply k f = apply (k-1) f . f
wrap :: a -> List a
wrap x = [x]
-- The greedy step
gstep1 :: Ord a => List a -> List a
gstep1 = maximum . drops
gstep :: Ord a => List a -> List a
gstep [x] = []
gstep (x:y:xs) = if x < y then y:xs else x:gstep (y:xs)
-- The algorithm
solve :: Ord a => Nat -> List a -> List a
solve k xs = gsolve k [] xs
gsolve :: Ord a => Nat -> List a -> List a -> List a
gsolve 0 xs ys = reverse xs ++ ys
gsolve k xs [] = reverse (drop k xs)
gsolve k xs (y:ys)
| null xs || head xs >= y = gsolve k (y:xs) ys
| otherwise = gsolve (k-1) (tail xs) (y:ys)