Prelude extensions

Sorted lists

The following are versions of standard prelude functions, but intended for sorted lists. The advantage is that they frequently reduce execution time by an O(n). The disadvantage is that the elements have to be members of Ord, and the lists have to be already sorted.

-- Eliminates duplicate entries from the list, where duplication is defined
-- by the 'eq' function.  The last value is kept.
sortedNubBy :: (a -> a -> Bool) -> [a] -> [a]
sortedNubBy eq (x1 : xs@(x2 : _)) =
   if eq x1 x2 then sortedNubBy eq xs else x1 : sortedNubBy eq xs
sortedNubBy _ xs = xs

sortedNub :: (Eq a) => [a] -> [a]
sortedNub = sortedNubBy (==)

-- Merge two sorted lists into a new sorted list.  Where elements are equal
-- the element from the first list is taken first.
mergeBy :: (a -> a -> Ordering) -> [a] -> [a] -> [a]
mergeBy cmp xs@(x1:xs1) ys@(y1:ys1) =
   if cmp x1 y1 == GT
      then y1 : mergeBy cmp xs ys1
      else x1 : mergeBy cmp xs1 ys
mergeBy _ [] ys = ys
mergeBy _ xs [] = xs

merge :: (Ord a) => [a] -> [a] -> [a]
merge = mergeBy compare