Ticket #7421: insertBy.hs

File insertBy.hs, 774 bytes (added by Bart Massey, 2 years ago)

implementation of insertBy that is maximally lazy and agrees with existing docs

Line 
1-- Copyright © 2012 Bart Massey
2
3import Data.List (span, foldr)
4
5-- This version of InsertBy actually follows the contract
6-- from the documentation (inasmuch as that contract can be
7-- read to specify anything sensible.) This version is
8-- maximally productive. It is non-recursive. It is ugly and
9-- kludgy.
10insertBy :: (a -> a -> Ordering) -> a -> [a] -> [a]
11insertBy c t xs0 =
12  let (xs1, xs2) = span (\x -> t `c` x /= LT) xs0 in
13  let xs2' =
14        case foldr f (Left []) xs2 of
15          Left xs -> t : xs
16          Right xs -> xs in
17  xs1 ++ xs2'
18  where
19    f x (Left []) = Left [x]
20    f x (Left [x']) | t `c` x' /= LT = Right [x, x', t]
21    f x (Left xs) | t `c` x /= LT = Right (x : t : xs)
22    f x (Left xs) = Left (x : xs)
23    f x (Right xs) = Right (x : xs)