Why doesn't Data.Sequence have `insert' or `insertBy', and how do I efficiently implement them?

Question

I was confused by the lack of these functions in the interface for the Sequence type, since Data.List provides these functions. Is there an efficiency problem here, or is it just a lack of demand for these functions?

And since they're not part of Data.Sequence, how can I efficiently implement them for my purposes?

Answer 1

Here's what I came up with:

> let insertBy cmp x seq = let (s1,s2) = partition (\y -> cmp x y == GT) seq in (s1 |> x) >< s2
> let s = fromList [1,2,3,4,5]
> insertBy compare 2 s
fromList [1,2,2,3,4,5]

Or you can just ape the version for lists:

{-# LANGUAGE ViewPatterns #-}

module Main
    where

import Data.Sequence

insertBy :: (a -> a -> Ordering) -> a -> Seq a -> Seq a
insertBy _   x (viewl -> EmptyL) = singleton x
insertBy cmp x ys@(viewl -> (y:<ys'))
 = case cmp x y of
     GT -> y <| insertBy cmp x ys'
     _  -> x <| ys