-- Copyright © 2012 Bart Massey
import Data.List (span, foldr)
-- This version of InsertBy actually follows the contract
-- from the documentation (inasmuch as that contract can be
-- read to specify anything sensible.) This version is
-- maximally productive. It is non-recursive. It is ugly and
-- kludgy.
insertBy :: (a -> a -> Ordering) -> a -> [a] -> [a]
insertBy c t xs0 =
let (xs1, xs2) = span (\x -> t `c` x /= LT) xs0 in
let xs2' =
case foldr f (Left []) xs2 of
Left xs -> t : xs
Right xs -> xs in
xs1 ++ xs2'
where
f x (Left []) = Left [x]
f x (Left [x']) | t `c` x' /= LT = Right [x, x', t]
f x (Left xs) | t `c` x /= LT = Right (x : t : xs)
f x (Left xs) = Left (x : xs)
f x (Right xs) = Right (x : xs)