为什么Data.Sequence没有`insert'或`insertBy',我该如何有效地实现它们呢？

Question

由于Data.List提供了这些函数,我对Sequence类型的接口中缺少这些函数感到困惑.这里是否存在效率问题,或者仅仅缺乏对这些功能的需求？

由于它们不属于Data.Sequence,我如何才能有效地实现它们？

Answer 1

这是我想出的：

> 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]

或者你可以模仿列表的版本：

{-# 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