Why doesn't Data.Sequence have “insert” or “insertBy” and how can I implement them effectively?

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 a performance issue here, or is it just a lack of demand for these features?

And since they are not part of Data.Sequence, how can I effectively implement them for my purposes?

Answer 1

Here is what I came up with:

> let insertBy cmp x seq = let (s1,s2) = partition (\y -> cmp xy == 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 use 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 xy of GT -> y <| insertBy cmp x ys' _ -> x <| ys